Что такое linked list в Node.js?

Linked List (связный список) — это структура данных, состоящая из узлов, где каждый узел содержит данные и ссылку на следующий узел. Это альтернатива массивам с собственными преимуществами и недостатками.

Основная структура

Узел (Node) содержит:

• Данные (value)
• Ссылку на следующий узел (next)

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  // Добавить в конец
  append(data) {
    const node = new Node(data);
    
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    
    this.size++;
  }
  
  // Добавить в начало
  prepend(data) {
    const node = new Node(data);
    
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head = node;
    }
    
    this.size++;
  }
  
  // Удалить по значению
  remove(data) {
    let current = this.head;
    let previous = null;
    
    while (current !== null) {
      if (current.data === data) {
        if (previous === null) {
          this.head = current.next;
        } else {
          previous.next = current.next;
        }
        this.size--;
        return;
      }
      previous = current;
      current = current.next;
    }
  }
  
  // Поиск
  find(data) {
    let current = this.head;
    
    while (current !== null) {
      if (current.data === data) return current;
      current = current.next;
    }
    
    return null;
  }
  
  // Показать все
  print() {
    let current = this.head;
    let result = '';
    
    while (current !== null) {
      result += current.data + ' -> ';
      current = current.next;
    }
    
    result += 'null';
    console.log(result);
  }
}

const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);
list.print(); // 5 -> 10 -> 20 -> 30 -> null

Linked List vs Array

Операция | Linked List | Array

• Вставка в начало: O(1) vs O(n) — быстро vs медленно
• Вставка в конец: O(1) vs O(1) — одинаково
• Удаление: O(n) vs O(n) — одинаково
• Поиск: O(n) vs O(n) — одинаково
• Доступ по индексу: O(n) vs O(1) — медленно vs быстро
• Память: O(n) + n ссылок vs O(n) — больше памяти

Когда использовать Linked List:

• Частые вставки в начало
• Неизвестный размер заранее
• Реализация Queue/Deque

Когда использовать Array:

• Частые поиски и доступ по индексу
• Изменяющийся размер (push/pop в конец)
• Известный размер данных

Двусвязный список (Doubly Linked List)

class DoublyNode {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
  }
  
  append(data) {
    const node = new DoublyNode(data);
    
    if (this.head === null) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) current = current.next;
      current.next = node;
      node.prev = current;
    }
  }
  
  // Может быть легче удалять (знаем предыдущий узел)
  remove(data) {
    if (this.head === null) return;
    
    let current = this.head;
    
    while (current !== null) {
      if (current.data === data) {
        if (current.prev) {
          current.prev.next = current.next;
        } else {
          this.head = current.next;
        }
        
        if (current.next) {
          current.next.prev = current.prev;
        }
        return;
      }
      current = current.next;
    }
  }
}

Реальные примеры в Node.js

1. Реализация LRU Cache (Least Recently Used):

class LRUCache {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.list = new DoublyLinkedList();
    this.map = new Map();
  }
  
  get(key) {
    if (this.map.has(key)) {
      // Переместить в конец
      this.list.moveToEnd(key);
      return this.map.get(key);
    }
    return null;
  }
  
  put(key, value) {
    if (this.map.has(key)) {
      this.map.set(key, value);
      this.list.moveToEnd(key);
    } else {
      if (this.map.size >= this.maxSize) {
        // Удалить самый старый элемент
        const oldest = this.list.removeHead();
        this.map.delete(oldest);
      }
      
      this.list.append(key);
      this.map.set(key, value);
    }
  }
}

2. История действий (для отката):

class ActionHistory {
  constructor() {
    this.history = new LinkedList();
  }
  
  addAction(action) {
    this.history.append(action);
  }
  
  undo() {
    // Удалить последний элемент
    const current = this.history.tail;
    // В обычном LinkedList нет быстрого доступа к предпоследнему
    // Использовать DoublyLinkedList было бы лучше
  }
}

3. Граф (соседи узла):

class GraphNode {
  constructor(value) {
    this.value = value;
    this.adjacents = new LinkedList(); // соседние узлы
  }
  
  addEdge(node) {
    this.adjacents.append(node);
  }
}

const nodeA = new GraphNode('A');
const nodeB = new GraphNode('B');
nodeA.addEdge(nodeB);

4. Очередь (Queue):

class Queue {
  constructor() {
    this.list = new LinkedList();
  }
  
  enqueue(data) {
    this.list.append(data); // O(1)
  }
  
  dequeue() {
    const head = this.list.head.data;
    this.list.remove(head);
    return head; // O(1) для первого элемента
  }
}

Circular Linked List

class CircularLinkedList extends LinkedList {
  append(data) {
    const node = new Node(data);
    
    if (this.head === null) {
      this.head = node;
      this.head.next = this.head; // указывает сам на себя
    } else {
      let current = this.head;
      while (current.next !== this.head) current = current.next;
      current.next = node;
      node.next = this.head;
    }
  }
}

Когда использовать Linked List в Node.js

• LRU Cache — кэширование с вытеснением старых элементов
• Playlist — список песен с быстрым переходом между ними
• Undo/Redo — история действий
• Graph representation — представление графов
• Очереди с частыми вставками в начало
• Музыкальный плеер — список треков

Linked List — это важная структура данных, хотя в современном JavaScript часто используют Array с методами push/shift или Queue. Понимание Linked List критично для собеседований и оптимизации определённых алгоритмов.