Односвязные списки

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

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

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

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

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

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

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

```python class Node:

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

```

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

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

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

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

class LinkedList:

   def __init__(self):
       self.head = None

   def insert_at_beginning(self, data):
       new_node = Node(data)
       new_node.next = self.head
       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

   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
       prev_node.next = new_node

   def delete_node(self, key):
       temp = self.head
       if (temp is not None):
           if (temp.data == key):
               self.head = temp.next
               temp = None
               return

       while(temp is not None):
           if temp.data == key:
               break
           prev = temp
           temp = temp.next

       if(temp == None):
           return

       prev.next = 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 = LinkedList() # Создание пустого односвязного списка
   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(n)$ (в худшем случае требуется проход по всему списку для нахождения удаляемого элемента)
5. Поиск элемента: $O(n)$ (в худшем случае требуется проход по всему списку)
6. Обход списка: $O(n)$
7. Определение длины списка: $O(n)$ (требуется проход по всему списку)

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

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

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

Недостатки:

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

Применение

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

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

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