Что такое связанный список и чем он отличается от массива?

Что такое связанный список?

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

Основные отличия от массива

• Память: Массив требует непрерывного блока памяти, список использует фрагментированную память.
• Доступ по индексу: В массиве — O(1), в списке — O(n) из-за необходимости последовательного обхода.
• Вставка/удаление: В массиве — O(n) из-за сдвига элементов, в списке — O(1) при наличии ссылки на узел.
• Размер: Массив статичен (фиксированный размер), список динамичен.

Пример кода на JavaScript

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

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(data) {
    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;
  }

  print() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }
}

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.print(); // 1 2 3

Когда применять

Связанные списки полезны, когда требуется часто вставлять или удалять элементы в середине списка, а также когда размер данных заранее неизвестен. Однако для задач с частым доступом по индексу лучше использовать массивы.

Вывод: Связанный список — гибкая структура для динамических данных с частыми изменениями, но уступает массиву в скорости произвольного доступа.