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

Что такое односвязный список?

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

Вот структура узлов односвязного списка:

Структура узла в связанном списке

Почему следует использовать связанный список вместо массива?

В ряде сценариев использование связанного списка предпочтительнее. массив:

• Неизвестное количество элементов: Если необходимое количество элементов неизвестно на этапе компиляции, связанный список динамически выделяет память по мере добавления элементов.
• Произвольный доступ: Когда произвольный индексированный доступ не требуется, подходящим выбором является связанный список.
• Вставка посередине: Вставка в середину массива требует сдвига элементов. Связанный список позволяет вставлять элементы в любую позицию, изменяя всего несколько указателей.

Operaции односвязного списка

Односвязный список хорошо подходит для динамического выделения памяти. Он поддерживает стандартные операции связанного списка, такие как вставка, удаление, поиск, обновление, слияние двух списков и обход.

В данной статье рассматриваются следующие операции:

• Вставка в голову
• Вставка в хвост
• Вставка после узла
• Вставка перед узлом
• Удалить головной узел
• Удалить хвостовой узел
• Найти и удалить узел
• Обход связанного списка

Вот пример связанного списка с четырьмя узлами.

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

Вставка в начало односвязного списка

Это простая операция. Обычно она называется добавлением элемента в односвязный список. Создается новый узел, который помещается в начало списка.

Для выполнения этой операции необходимо соблюдать два важных условия:

1. Если список пуст, вновь созданный узел становится головным узлом, и его следующий Указатель равен NULL.
2. Если список не пуст, новый узел становится головным узлом, и его следующий Указатель указывает на предыдущий головной узел.

Вот псевдокод для вставки узла в начало связанного списка:

function insertAtHead(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  else:
    newNode.next = head
    return newNode

Вставка в голову

Вставка в конец односвязного списка

Вставка узла в конец связанного списка аналогична вставке в начало. Пройдите к хвостовому узлу, затем укажите на него путь. следующий Указатель на новый узел. Если head равен NULL, новый узел становится головным.

Шаг 1) Продвигайтесь до следующий Указатель текущего узла становится равным NULL.

Шаг 2) Создайте новый узел с указанным значением.

Шаг 3) Назначьте новый узел следующим узлом хвостового узла.

Псевдокод для вставки в конец списка, состоящего из одного элемента:

function insertAtEnd(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  while head.next is not NULL:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Вставка в хвост

Вставка после узла в односвязном списке

Вставка после узла состоит из двух частей: поиск целевого узла и добавление нового узла после него. Затем выполняется обход списка до тех пор, пока не будет найдено совпадение, после чего новый узел вставляется.

Шаг 1) Перемещайтесь по узлу до тех пор, пока значение текущего узла не сравняется со значением искомого элемента.

Шаг 2) Установите новый узел следующий указатель на текущий узел следующий указатель.

Шаг 3) Укажите текущий узел следующий указатель на новый узел.

Псевдокод:

function insertAfter(head, value, searchItem):
  newNode = Node(value)
  while head.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Вставка узла после узла в односвязном списке

Вставка перед узлом в односвязном списке

Это похоже на вставку после узла. Проходим по узлам до тех пор, пока следующий узел не будет соответствовать искомому значению, затем вставляем новый узел перед ним.

Шаг 1) Перемещайтесь до тех пор, пока значение следующего узла не станет равным искомому элементу.

Шаг 2) Создайте новый узел и задайте его параметры. следующий указатель на текущий узел следующий.

Шаг 3) Укажите текущий узел следующий к новому узлу.

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Вставка узла перед узлом в односвязном списке

Удалить заголовок односвязного списка

Указатель на головной узел передается в качестве параметра. Головной узел удаляется, и следующий узел становится новым головным. Память удаленного узла должна быть освобождена во избежание утечек памяти.

Шаг 1) Назначьте следующий узел головной позиции в качестве новой головной позиции.

Шаг 2) Освободите выделенную память предыдущего головного узла.

Шаг 3) Верните новый головной узел.

function deleteHead(head):
  temp = head
  head = head.next
  free(temp)
  return head

Удаление главы связанного списка

Удалить хвостовую часть односвязного списка

Удаление хвостового узла аналогично удалению головного узла. Разница заключается в том, что требуется обход списка до конца. В односвязном списке узел, чей следующий Если указатель равен NULL, это хвостовой узел.

Шаг 1) Пройдите до точки непосредственно перед хвостовым узлом. Сохраните текущий узел.

Шаг 2) Освободите память следующего узла (хвоста).

Шаг 3) Установите значение NULL для следующего узла текущего узла.

function deleteTail(head):
  while head.next.next is not NULL:
    head = head.next
  free(head.next)
  head.next = NULL

Удаление хвоста односвязного списка

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

Эта функция выполняет две задачи: поиск и удаление. Проходим по списку до конца. Если найден соответствующий узел, удаляем его и восстанавливаем связь с предыдущим узлом. следующий указатель.

Шаг 1) Пройдите по списку до конца. Проверьте, совпадает ли текущий узел с искомым узлом.

Шаг 2) Если найдено совпадение, сохраните указатель на текущий узел.

Шаг 3) следующий Предыдущий узел становится следующим узлом текущего узла.

Шаг 4) Удалите текущий узел и освободите его память.

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

Найдите и удалите узел из односвязного списка.

Обход односвязного списка

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

Шаг 1) Пройдите по каждому узлу, пока не будет достигнуто значение NULL.

Шаг 2) Выведите значение текущего узла.

function traverse(head):
  while head is not NULL:
    print head.value
    head = head.next

Пример односвязного списка в C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head != NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head == NULL){
    insertAtHead(head, value);
    return;
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next != NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = NULL;
  if((*headPtr)->data == searchItem){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  } else {
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
void insertAfter(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->next->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
  Node* tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode != NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head, 5);
  insertAtHead(head, 6);
  insertAtHead(head, 7);
  insertEnd(head, 9);
  traverse(head);
  searchAndDelete(&head, 6);
  traverse(head);
  insertAfter(head, 7, 10);
  insertBefore(head, 9, 11);
  traverse(head);
}

Результат

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Traversal from head:    7 --> 6 --> 5 --> 9
Deleted Node    6
Traversal from head:    7 --> 5 --> 9
Inserted 10 after node  7
Inserted 11 before node 9
Traversal from head:    7 --> 10 --> 5 --> 11 --> 9

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

class Node:
  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None
  def insertAtHead(self, value):
    newNode = Node(data=value)
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')
  def searchAndDelete(self, searchItem):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
singlyLinkedList = SinglyLinkedList()
singlyLinkedList.insertAtHead(5)
singlyLinkedList.insertAtHead(6)
singlyLinkedList.insertAtHead(7)
singlyLinkedList.insertAtEnd(9)
singlyLinkedList.traverse()
singlyLinkedList.searchAndDelete(6)
singlyLinkedList.traverse()
singlyLinkedList.insertAfter(7, 10)
singlyLinkedList.insertBefore(9, 11)
singlyLinkedList.traverse()

Результат

Added 5 at the front.
Added 6 at the front.
Added 7 at the front.
Added 9 at the end.
Traversing from head:   7       6       5       9
Deleted node    6
Traversing from head:   7       5       9
Inserted 10 after node  7
Inserted 11 before node 9
Traversing from head:   7       10      5       11      9

Сложность односвязного списка

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

временная сложность в лучшем случае:

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

Средняя временная сложность:

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

Пространственная сложность односвязного списка

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

Применение односвязных списков

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

• Стеки и очереди: Базовая система хранения данных для стеков LIFO и очередей FIFO, сформированных из узлов.
• Метод цепочек хеш-таблиц: Конфликты разрешаются путем объединения записей в односвязный список для каждого сегмента.
• Списки смежности: В разреженных графах для каждой вершины используется односвязный список соседей.
• Таблицы символов: Компиляторы и интерпретаторы объединяют идентификаторы в односвязный список для каждой области видимости.
• Распределители памяти: Распределители свободного списка track свободных блоков в виде односвязного списка.

Часто задаваемые вопросы (FAQ)