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

Що таке однозв’язаний список?

Однозв'язний список — це лінійна та односпрямована структура даних, де дані зберігаються на вузлах, і кожен вузол з'єднаний через посилання з наступним вузлом. Кожен вузол містить поле даних та посилання на наступний вузол. Однозв'язні списки можна переглядати лише в одному напрямку, тоді як Двозв’язаний список можна пересуватися в обох напрямках.

Ось структура вузлів однозв'язаного списку:

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

Навіщо використовувати зв'язаний список над масивом?

Кілька сценаріїв надають перевагу зв'язаному списку над масив:

• Невідома кількість елементів: Коли необхідна кількість елементів невідома під час компіляції, зв'язаний список динамічно розподіляє пам'ять під час додавання елементів.
• Довільний доступ: Коли випадковий індексований доступ не потрібен, зв'язаний список є підходящим вибором.
• Вставка посередині: Вставка в середину масиву вимагає зміщення елементів. Зв'язаний список дозволяє вставку в будь-яку позицію, перезаписуючи лише кілька вказівників.

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 вільних блоків у вигляді однозв'язного списку.

Поширені запитання