Связный список

Введение в связные списки

Массивы

Говоря про связные списки, нам нужно вернуться еще раз к массивам. Что такое элементы массива? - Это расположенные в памяти друг за другом ячейки памяти определенного размера. Чем хорош в таком случае массив? - Своим доступом к элементам за константное время.

Можно сравнить массивы с покупкой мест в кинотеатре - мы покупаем n мест для себя и своих друзей, но если нас станет n + 1, то нам нужно будет докупить место или сменить ряд, если мест не будет.

Проблема с массивами

Но что делать, когда места уже не купишь - нет свободной последовательности мест такой длины?

И тут на помощь приходит связный список. Он позволяет нам жертвовать последовательностью, распределяя данные в памяти на свободном месте. Он позволяет нам вставлять данные за константное время - мы всегда знаем, где у нас находится конец данного списка, и не зависим от того, сколько элементов в самом списке.

Описание связного списка

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

Двусвязный список

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

Структура узла

В двусвязном списке каждый узел имеет следующую структуру:

• Данные: Значение, которое хранится в узле.
• Ссылка на следующий узел: Указатель на следующий элемент в списке.
• Ссылка на предыдущий узел: Указатель на предыдущий элемент в списке.

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

• Быстрая вставка и удаление: Вставка и удаление элементов могут быть выполнены за константное время, поскольку не требуется сдвиг элементов.
• Двусторонняя навигация: Возможность перемещаться как вперед, так и назад по списку, что упрощает определенные операции.

Пример реализации связного списка

class Node {
  constructor(data) {
    this.data = data; // Инициализация данных узла
    this.next = null; // Инициализация ссылки на следующий узел
  }
}

class LinkedList {
  #head; // Приватное свойство для хранения головного узла списка
  #size; // Приватное свойство для хранения размера списка

  constructor() {
    this.#head = null; // Инициализация головного узла как null
    this.#size = 0; // Инициализация размера списка как 0
  }

  addFirst(data) {
    const newNode = new Node(data); // Создание нового узла с переданными данными
    newNode.next = this.#head; // Установка следующего узла нового узла на текущий головной узел
    this.#head = newNode; // Установка нового узла как головного узла
    this.#size++; // Увеличение размера списка на 1
  }

  removeFirst() {
    if (!this.#head) return null; // Если список пуст, возвращаем null
    const removed = this.#head; // Сохраняем текущий головной узел для последующего возврата данных
    this.#head = this.#head.next; // Перемещаем головной узел на следующий узел
    this.#size--; // Уменьшаем размер списка на 1
    return removed.data; // Возвращаем данные удаленного узла
  }

  printList() {
    let current = this.#head; // Начинаем с головного узла
    while (current) {
      console.log(current.data); // Печатаем данные текущего узла
      current = current.next; // Переходим к следующему узлу
    }
  }
}

const list = new LinkedList(); // Создаем новый экземпляр связного списка
list.addFirst(10); // Добавляем элемент со значением 10 в начало списка
list.addFirst(20); // Добавляем элемент со значением 20 в начало списка
list.printList(); // Печатаем все элементы списка
console.log("Removed:", list.removeFirst()); // Удаляем первый элемент и печатаем его значение
list.printList(); // Печатаем все элементы списка после удаления первого элемента

Какие еще могут быть операции у связного списка?

Основные операции связного списка

Вставка элементов (Insertion)

• В начало списка (AddFirst или PushFront): добавляет новый элемент в начало списка. Обычно это операция с постоянным временем O(1), так как не требует перемещения других элементов.
• В конец списка (AddLast или PushBack): добавляет новый элемент в конец списка. В односвязных списках эта операция может быть затратной (O(n)), если не хранится ссылка на последний элемент. В двусвязных списках или в односвязных списках с ссылкой на последний элемент операция также выполняется за O(1).
• После заданного узла (InsertAfter): вставляет новый элемент непосредственно после указанного узла. Обычно это операция O(1).

Удаление элементов (Deletion)

• Из начала списка (RemoveFirst или PopFront): удаляет первый элемент списка. Это операция O(1).
• Из конца списка (RemoveLast или PopBack): удаляет последний элемент списка. В односвязных списках это может потребовать обхода всего списка (O(n)), если нет отдельной ссылки на предпоследний узел.
• Удаление конкретного элемента (Remove): находит и удаляет элемент, если он присутствует в списке. Эта операция может потребовать обхода всего списка (O(n)).

Поиск элементов (Search)

• Поиск элемента по значению: перебирает элементы, пока не найдет узел с заданным значением или не достигнет конца списка. Обычно это операция O(n).

Обход списка (Traversal)

• Перебор всех элементов списка: используется для выполнения операций или функций над каждым элементом списка.

Получение размера списка (Size)

• Определение количества элементов: может храниться как переменная и обновляться при каждой операции вставки/удаления, или может быть вычислена через полный обход списка (O(n)).

Очистка списка (Clear)

• Удаление всех элементов: очищает список, обычно устанавливая начальный и конечный узлы в null и, возможно, обнуляя счётчик размера.

Реверсирование списка (Reverse)

• Инвертирование порядка элементов: изменяет направление всех ссылок в списке так, чтобы первый элемент стал последним, а последний — первым. Это может быть выполнено за O(n).

Когда нам нужны такие списки?

• Например, когда мы хотим вставить что-то в середину списка. С массивами мы бы создавали новый массив, резервировали память и очищали память от прошлого массива.
• Например, когда мы хотим удалить элемент, нам больше подойдет связный список. Потому что удаление у него займет O(1).

Отсюда мы можем вывести и основные минусы для связанного списка - это чтение за время O(n). Мы должны пройти все элементы от первого или от последнего элемента, чтобы найти какой-то определенный.

Реальные примеры

• Можно сделать очереди или стеки на этих структурах данных.
• Можно сделать свой менеджер задач, куда задачи попадают постепенно.

Вопрос

• В чем разница между связным списком и массивом?