Двусвязные списки

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

Основные понятия

1. Узел (Node): Основной элемент двусвязного списка, содержащий данные, ссылку на следующий узел и ссылку на предыдущий узел.
2. Данные (Data): Информация, хранящаяся в узле.
3. Ссылка на следующий узел (Next): Указатель на следующий узел в списке.
4. Ссылка на предыдущий узел (Prev/Previous): Указатель на предыдущий узел в списке.
5. Голова (Head): Первый узел в списке. У головы ссылка на предыдущий узел равна `NULL` или `None`.
6. Хвост (Tail): Последний узел в списке. У хвоста ссылка на следующий узел равна `NULL` или `None`.

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

Узел двусвязного списка состоит из трех частей:

1. Данные (Data): Информация, хранящаяся в узле. Тип данных может быть любым.
2. Ссылка на следующий узел (Next): Указатель на следующий узел в списке. Если узел является последним в списке, то ссылка равна `NULL` или `None`.
3. Ссылка на предыдущий узел (Prev/Previous): Указатель на предыдущий узел в списке. Если узел является первым в списке, то ссылка равна `NULL` или `None`.

Пример структуры узла на Python:

```python class Node:

   def __init__(self, data):
       self.data = data
       self.next = None
       self.prev = None

```

Свойства двусвязных списков

1. Динамический размер: Размер двусвязного списка может изменяться во время выполнения программы.
2. Непоследовательное хранение в памяти: Узлы двусвязного списка не обязательно хранятся в памяти последовательно.
3. Двунаправленный обход: Возможность перемещения по списку в обоих направлениях (от головы к хвосту и от хвоста к голове).
4. Простота вставки и удаления элементов: Вставка и удаление элементов может быть выполнена за константное время ($O(1)$), если известен указатель на узел, перед которым или после которого нужно вставить или удалить элемент.
5. Дополнительные затраты памяти на хранение двух указателей: Для каждого элемента списка необходимо хранить два указателя (на следующий и предыдущий элементы), что увеличивает потребление памяти по сравнению с односвязными списками.

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

1. Создание списка (Creation): Создание нового двусвязного списка.
2. Вставка элемента (Insertion): Добавление нового узла в список.
3. Удаление элемента (Deletion): Удаление узла из списка.
4. Поиск элемента (Search): Поиск узла с заданным значением в списке.
5. Обход списка (Traversal): Проход по всем узлам списка для выполнения каких-либо действий.
6. Определение длины списка (Length): Вычисление количества узлов в списке.
7. Разворот списка (Reverse): Изменение порядка узлов в списке на обратный.

Реализация двусвязного списка

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

```python class Node:

   def __init__(self, data):
       self.data = data
       self.next = None
       self.prev = None

class DoublyLinkedList:

   def __init__(self):
       self.head = None

   def insert_at_beginning(self, data):
       new_node = Node(data)
       new_node.next = self.head
       if self.head is not None:
           self.head.prev = new_node
       self.head = new_node

   def insert_at_end(self, data):
       new_node = Node(data)
       if self.head is None:
           self.head = new_node
           return
       last = self.head
       while (last.next):
           last = last.next
       last.next = new_node
       new_node.prev = last

   def insert_after(self, prev_node, data):
       if prev_node is None:
           print("Previous node must be in the list")
           return

       new_node = Node(data)
       new_node.next = prev_node.next
       if prev_node.next is not None:
           prev_node.next.prev = new_node
       prev_node.next = new_node
       new_node.prev = prev_node

   def delete_node(self, key):
       temp = self.head

       if (temp is not None and temp.data == key):
           self.head = temp.next
           if (self.head is not None):
               self.head.prev = None
           temp = None
           return

       while (temp is not None and temp.data != key):
           temp = temp.next

       if (temp == None):
           return

       if (temp.next is not None):
           temp.next.prev = temp.prev

       if (temp.prev is not None):
           temp.prev.next = temp.next
       else:
           self.head = temp.next

       temp = None

   def search(self, x):
       current = self.head
       while (current != None):
           if current.data == x:
               return True
           current = current.next
       return False

   def print_list(self):
       temp = self.head
       while (temp):
           print(temp.data, end=" ")
           temp = temp.next
       print()

```

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

1. Создание списка:

1. 1. ```python
   2. linked_list = DoublyLinkedList() # Создание пустого двусвязного списка
   3. ```
2. Вставка элемента в начало списка:

1. 1. ```python
   2. linked_list.insert_at_beginning(10) # Вставка элемента 10 в начало списка
   3. ```
2. Вставка элемента в конец списка:

1. 1. ```python
   2. linked_list.insert_at_end(20) # Вставка элемента 20 в конец списка
   3. ```
2. Вставка элемента после заданного узла:

1. 1. ```python
   2. node = linked_list.head # Получение головы списка
   3. linked_list.insert_after(node, 15) # Вставка элемента 15 после головы списка
   4. ```
2. Удаление элемента с заданным значением:

1. 1. ```python
   2. linked_list.delete_node(10) # Удаление элемента 10 из списка
   3. ```
2. Поиск элемента с заданным значением:

1. 1. ```python
   2. found = linked_list.search(20) # Поиск элемента 20 в списке
   3. if found:
   4. print("Element 20 found in the list")
   5. else:
   6. print("Element 20 not found in the list")
   7. ```
2. Обход списка и вывод элементов:

1. 1. ```python
   2. linked_list.print_list() # Вывод всех элементов списка
   3. ```

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

1. Вставка в начало списка: $O(1)$
2. Вставка в конец списка: $O(n)$ (требуется проход по всему списку для нахождения хвоста)
3. Вставка после заданного узла: $O(1)$ (если известен указатель на заданный узел)
4. Удаление элемента: $O(1)$ (если известен указатель на удаляемый элемент)
5. Поиск элемента: $O(n)$ (в худшем случае требуется проход по всему списку)
6. Обход списка: $O(n)$
7. Определение длины списка: $O(n)$ (требуется проход по всему списку)

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

Преимущества:

1. Двунаправленный обход: Возможность перемещения по списку в обоих направлениях.
2. Простота вставки и удаления элементов: Вставка и удаление элементов может быть выполнена за константное время, если известен указатель на узел, перед которым или после которого нужно вставить или удалить элемент.

Недостатки:

1. Дополнительные затраты памяти на хранение двух указателей: Для каждого элемента списка необходимо хранить два указателя, что увеличивает потребление памяти.
2. Более сложная реализация: Реализация двусвязных списков сложнее, чем реализация односвязных списков.

Применение

Двусвязные списки используются в широком спектре приложений, включая:

1. Реализация других структур данных (например, стеков, очередей, деков).
2. Реализация списков воспроизведения в медиаплеерах.
3. Реализация навигации по истории в веб-браузерах.
4. Управление памятью.

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