Структура данных - связный список (Linked List)

Основы Linked List (связного списка)

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

Связанный список является второй наиболее используемой структурой данных после массива. Ниже приведены важные термины для понимания концепции связанного списка.

Node - элемент связного списка, этот элемент содержит в себе два значения, которые и являются основой LinkedList: ссылка на следующий элмент и значение.
Next - ссылка на следующий элемент, то есть на следующую Node
Value - значение самой Node, который мы хотим хранить

Типы связных списков (Linked List)

  1. Простой связный список - навигация данного списка только вперед. То есть добавляются новые элементы только в конец списка и никак по другому. Содержит только одну ссылку next.

  2. Двусвязный список - эти списки, которые позволяют нам ходить по ним в обоих направлениях. Соответственно и добавлять также элементы, как в начало, так и в конец. А также стоит упомянуть, что кроме ссылки next у них есть ссылки prev.

  3. Круговой связный список - последний элемент данного списка содердит ссылку на первый элемент данного списка. А первый элемент будет иметь ссылку на последний элемент. То есть, можно сказать что это тоже двусвязный список, но закольцованный.

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

  1. Вставка - добавит элемент в начало списка(конец списка в зависимости от реализации (к примеру если есть ссылки head и tail мы можем добавлять в обоих направлениях)

  2. Удаление - удаляет элемент в начале списка (или его в конце, если ссылка tail, кроме head)

  3. Отображение - отображает полный список (реализован через цикл).

  4. Поиск - поиск элемента по заданному списку (реализован через цикл)

  5. Удаление по ключу - находит элемент по ключу, после удаляет его (также через цикл)

Достоинства использования

  1. Эффективное (за константное время) добавление и удаление элементов

  2. Размер ограничен только объёмом памяти компьютера и его разрядностью

  3. Динамическое добавление и удаление элементов

Недостатки использования

  1. Сложность прямого доступа к элементу, а именно определения физического адреса по его

  2. На указатели расходуется дополнительная память, так как их надо хранить

  3. Некоторые операции медленее, так как нельзя получить по индексу элемент и надо проходиться по всему списку

  4. Труднее использовать при параллельных вычислениях

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