Linked list
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this._size = 0;
}
get size() {
return this._size;
}
// Оптимальная вставка в начало — O(1)
insertFirst(value) {
const node = new Node(value);
if (!this.head) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head = node;
}
this._size++;
}
// Оптимальная вставка в конец (благодаря tail) — O(1)
insertLast(value) {
const node = new Node(value);
if (!this.tail) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this._size++;
}
// Поиск узла по индексу — O(n)
getAt(index) {
if (index < 0 || index >= this._size) return null;
let current = this.head; // starting
for (let i = 0; i < index; i++) {
current = current.next;
}
return current;
}
// Вставка по индексу — O(n) из-за поиска, но сама вставка O(1)
insertAt(index, value) {
if (index < 0 || index > this._size) return false;
if (index === 0) return this.insertFirst(value);
if (index === this._size) return this.insertLast(value);
const node = new Node(value);
const previous = this.getAt(index - 1);
node.next = previous.next;
previous.next = node;
this._size++;
return true;
}
// Удаление по индексу — O(n)
removeAt(index) {
if (index < 0 || index >= this._size) return null;
let deletedNode;
if (index === 0) {
deletedNode = this.head;
this.head = this.head.next;
if (this._size === 1) this.tail = null;
} else {
const previous = this.getAt(index - 1);
deletedNode = previous.next;
previous.next = deletedNode.next;
if (index === this._size - 1) this.tail = previous;
}
this._size--;
return deletedNode;
}
// Разворот списка "на месте" без выделения новой памяти — O(n) по времени, O(1) по памяти
reverse() {
let current = this.head;
let previous = null;
let next = null;
this.tail = this.head; // Бывший head станет tail
while (current !== null) {
next = current.next; // Сохраняем ссылку на следующий узел
current.next = previous; // Разворачиваем стрелку ссылки назад
previous = current; // Двигаем previous вперед
current = next; // Двигаем current вперед
}
this.head = previous; // Новый head — это последний обработанный узел
}
clear() {
this.head = null;
this.tail = null;
this._size = 0;
}
}
JavaScript
INFO