вступление
В прошлый раз , мы добавили последний метод, Удалить Анкет
Я надеюсь, что вы узнали кое -что о концепции отдельного списка и старались изо всех сил внедрить его самостоятельно. Если вы хотите получить уведомление о новых вещах, подписаться 🙂
Большую часть времени это углубляет мои знания, если я снова займусь этим. И опять.
Окончательная реализация (короткая версия)
В нашем отдельном списке есть эти методы:
- Получить определенный узел
- Обновить определенный узел
- Добавить узел к концу
- удалить узел с конца
- Добавить узел в начало
- удалить узел с самого начала
- Добавить узел в определенном индексе
- удалить узел при определенном индексе
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
// get a specific node
get(index) {
if (index < 0 || index >= this.length) {
return null;
} else {
let currentNode = this.head;
let count = 0;
while (count < index) {
currentNode = currentNode.next;
count += 1;
}
return currentNode;
}
}
// update a specific node
set(index, value) {
const currentNode = this.get(index);
if (currentNode) {
currentNode.value = value;
return currentNode;
} else {
return null;
}
}
// add to the end
push(value) {
const newNode = new Node(value);
if (!this.length) {
this.head = newNode;
} else {
this.tail.next = newNode;
}
this.tail = newNode;
this.length += 1;
return newNode;
}
// remove from the end
pop() {
if (!this.length) {
return null;
} else {
let nodeToRemove = this.head;
let secondToLastNode = this.head;
while (nodeToRemove.next) {
secondToLastNode = nodeToRemove;
nodeToRemove = nodeToRemove.next;
}
secondToLastNode.next = null;
this.tail = secondToLastNode;
this.length -= 1;
if (!this.length) {
this.head = null;
this.tail = null;
}
return nodeToRemove;
}
}
// add to the beginning
unshift(value) {
const newNode = new Node(value);
if (!this.length) {
this.tail = newNode;
} else {
newNode.next = this.head;
}
this.head = newNode;
this.length += 1;
return newNode;
}
// remove from the beginning
shift() {
if (!this.length) {
return null;
} else {
const nodeToRemove = this.head;
this.head = this.head.next;
this.length -= 1;
if (!this.length) {
this.tail = null;
}
return nodeToRemove;
}
}
// add at a specific index
insert(index, value) {
if (index < 0 || index > this.length) {
return null;
} else if (index === 0) {
return this.unshift(value);
} else if (index === this.length) {
return this.push(value);
} else {
const preNewNode = this.get(index - 1);
const newNode = new Node(value);
newNode.next = preNewNode.next;
preNewNode.next = newNode;
this.length += 1;
return newNode;
}
}
// remove from a specific index
remove(index) {
if (index < 0 || index >= this.length) {
return null;
} else if (index === 0) {
return this.shift();
} else if (index === this.length - 1) {
return this.pop();
} else {
const preNodeToRemove = this.get(index - 1);
const nodeToRemove = preNodeToRemove.next;
preNodeToRemove.next = nodeToRemove.next;
this.length -= 1;
return nodeToRemove;
}
}
}
Вопросы
- Вам нравится этот подход “крошечные шаги”?
- Вы заинтересованы в других структурах данных, например, Список вдвойне связанный, стек, очередь?
Оригинал: “https://dev.to/miku86/javascript-data-structures-singly-linked-list-reca-210b”