Что такое Linked List?

Что такое Linked List (Связный список)?

Linked List — это фундаментальная линейная структура данных, которая состоит из последовательности узлов (nodes), где каждый элемент хранит не только собственное значение (value), но также ссылку (или указатель — pointer) на следующий элемент в списке. В отличие от массива (Array), элементы связного списка не хранятся в непрерывном блоке памяти, и их физическое расположение может быть произвольным. Именно эти ссылки "связывают" элементы в цепочку, формируя список.

Основные компоненты Linked List

Каждый узол (node) обычно содержит:

• Данные (Data) — значение, которое хранит узол (например, число, строка, объект).
• Ссылка (Next pointer) — указатель на следующий узол в списке. В языках без прямых указателей (как Swift) это реализуется как ссылка на объект следующего узла.

Первый узол называется головой (head) списка, а последний — хвостом (tail). Узол в хвосте имеет ссылку на nil (или null), указывая на конец списка.

Типы связных списков

1. Односвязный список (Singly Linked List) — каждый узол имеет ссылку только на следующий элемент.

   class ListNode<T> {
       var value: T
       var next: ListNode<T>?
       
       init(value: T, next: ListNode<T>? = nil) {
           self.value = value
           self.next = next
       }
   }
   

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

   class DoublyListNode<T> {
       var value: T
       var next: DoublyListNode<T>?
       var prev: DoublyListNode<T>?
       
       init(value: T, next: DoublyListNode<T>? = nil, prev: DoublyListNode<T>? = nil) {
           self.value = value
           self.next = next
           self.prev = prev
       }
   }
   

3. Кольцевой связный список (Circular Linked List) — "хвостовой" узол ссылается на "голову", образуя замкнутый цикл. Может быть односвязным или двусвязным.

Сравнение с массивом (Array) в контексте iOS (Swift)

• Динамический размер: Linked List может легко расти или сокращаться без необходимости перераспределения памяти, в отличие от массива, который требует копирования при изменении capacity.
• Вставка и удаление: Добавление или удаление элемента в начале или середине списка выполняется за O(1) времени (при наличии ссылки на нужный узол), тогда как в массиве это требует сдвига элементов и может быть O(n).
• Доступ к элементам: В Linked List доступ к элементу по индексу требует последовательного перехода от головы, что дает O(n) время. В массиве доступ по индексу — O(1).
• Использование памяти: Каждый узол хранит дополнительную ссылку, что увеличивает потребление памяти по сравнению с массивом.

Практическое применение в iOS разработке

Linked List может быть полезен в сценариях, где важны частые операции вставки/удаления, и не требуется быстрый произвольный доступ:

• Реализация очереди (Queue) или стека (Stack) (хотя в Swift чаще используют Array).
• История действий для функции Undo.
• Задачи, связанные с управлением памятью или LRU (Least Recently Used) cache, где двусвязный список эффективно перемещает элементы.

В Swift стандартная библиотека не предоставляет готовый Linked List, и чаще используется Array благодаря его высокой оптимизации и удобному API. Однако понимание связных списков важно для решения алгоритмических задач (например, на LeetCode) и для понимания более сложных структур данных, таких как графы и деревья.

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