Для чего используется связанный список?

Связные списки (Linked List) и их применение

Связный список — это фундаментальная структура данных, состоящая из узлов, где каждый узел содержит данные и ссылку на следующий узел. Хотя в Node.js редко пишут связные списки вручную, понимание их особенностей критично для интервью и оптимизации алгоритмов.

Структура связного списка

// Узел (Node)
class Node {
  data: any;
  next: Node | null = null;
  
  constructor(data: any) {
    this.data = data;
  }
}

// Простой связный список
class LinkedList {
  head: Node | null = null;
  
  // Добавить в конец
  append(data: any) {
    const newNode = new Node(data);
    
    if (!this.head) {
      this.head = newNode;
      return;
    }
    
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
  
  // Вставить в начало
  prepend(data: any) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
  }
  
  // Удалить элемент
  remove(data: any) {
    if (!this.head) return;
    
    if (this.head.data === data) {
      this.head = this.head.next;
      return;
    }
    
    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }
}

Сравнение со звичайными массивами

//           ARRAY          LINKED LIST
Access      O(1)           O(n)
Insert      O(n)           O(1) *
Delete      O(n)           O(1) *
Space       O(1)           O(n)

// * если уже есть ссылка на узел

Преимущества связных списков

1. Быстрое добавление/удаление в начале

// Массив — нужно сдвигать все элементы O(n)
const arr = [1, 2, 3, 4, 5];
arr.unshift(0);  // [0, 1, 2, 3, 4, 5] — сдвинули всё

// Связный список — просто меняем указатель O(1)
list.prepend(0);  // быстро!

2. Экономия памяти при частых вставках/удалениях

// Массив перевыделяет память при расширении
const arr = new Array(10);  // выделил 10 мест
arr.push(11);  // нужно больше, перевыделяет на 20

// Связный список растет на N элементов
list.append(11);  // добавляет одно звено

3. Динамический размер без переутечек памяти

// Массив может иметь пустые места
const arr = new Array(1000000);  // 1 млн мест, но используем 10

// Список использует ровно столько, сколько нужно
const list = new LinkedList();
for (let i = 0; i < 10; i++) {
  list.append(i);  // 10 узлов, ровно столько сколько надо
}

Недостатки связных списков

1. Нет прямого доступа по индексу O(n)

// Массив — мгновенный доступ
const arr = [1, 2, 3, 4, 5];
const third = arr[2];  // O(1)

// Список — нужно пройти с начала
let current = list.head;
for (let i = 0; i < 2; i++) {
  current = current.next;  // O(n)
}

2. Дополнительная память на указатели

// Каждый узел содержит указатель на следующий
// Если данные маленькие, память на указатели >> памяти на данные
const list = new Node(1);  // 1 число + 8 байт на указатель

Применение в реальных системах

1. Очередь и стек

// Очередь (Queue) — идеально с linked list
class Queue {
  head: Node | null = null;
  tail: Node | null = null;
  
  enqueue(data: any) {
    const newNode = new Node(data);
    if (!this.tail) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
  
  dequeue() {
    if (!this.head) return null;
    const data = this.head.data;
    this.head = this.head.next;
    return data;  // O(1)!
  }
}

// С массивом shift() — O(n)
const queue = [1, 2, 3];
queue.shift();  // медленно, сдвигает всё

2. LRU Cache (используется в браузерах, базах данных)

// LRU Cache использует двусвязный список + HashMap
class LRUCache {
  private capacity: number;
  private cache: Map<number, Node> = new Map();
  private head: Node = new Node(0);
  private tail: Node = new Node(0);
  
  constructor(capacity: number) {
    this.capacity = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  
  // Получить значение и переместить в начало
  get(key: number): number {
    if (!this.cache.has(key)) return -1;
    
    const node = this.cache.get(key)!;
    this.removeNode(node);
    this.addToHead(node);
    return node.value;
  }
}

3. Реализация графов (adjacency list)

// Граф часто представляют как связные списки
class Graph {
  private adj: Map<number, Node> = new Map();
  
  addEdge(u: number, v: number) {
    if (!this.adj.has(u)) {
      this.adj.set(u, new Node(v));
    } else {
      let current = this.adj.get(u)!;
      while (current.next) {
        current = current.next;
      }
      current.next = new Node(v);
    }
  }
}

4. Кэширование с LRU политикой в Node.js

// Redis часто использует связные списки внутри
const cache = new LinkedList();

function cacheData(key: string, value: any) {
  // Удалить старый если есть
  cache.remove(key);
  
  // Добавить новый в начало (самый свежий)
  cache.prepend({ key, value });
  
  // Если превышен размер, удалить с конца
  if (cache.size > MAX_SIZE) {
    cache.removeFromEnd();
  }
}

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

class DoublyNode {
  data: any;
  next: DoublyNode | null = null;
  prev: DoublyNode | null = null;  // указатель на предыдущий
  
  constructor(data: any) {
    this.data = data;
  }
}

// Позволяет просто двигаться в обе стороны
// Используется в LRU Cache для быстрого удаления из середины

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

// ✅ Используй связные списки
- Реализация Queue/Stack (нет операции shift)
- LRU Cache
- Граф (adjacency list)
- Когда нужны частые вставки/удаления в начало

// ❌ Не используй
- Когда нужна индексация (используй Array)
- Когда нужна сортировка (используй Array)
- Когда данные статичные (используй Array)

// В Node.js обычно используешь структуры данных библиотек
import Deque from 'collections/deque';  // очередь
import LRU from 'lru-cache';  // LRU cache

Понимание связных списков — это основа computer science, даже если в production code ты используешь готовые структуры данных. На интервью это часто спрашивают как проверку фундаментальных знаний.