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

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

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

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

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

Навіщо використовувати пов’язаний список поверх масиву?

Є кілька випадків, коли краще використовувати пов’язаний список, а не масив. Ось кілька сценаріїв:

  • Невідома кількість елементів: Якщо ви не знаєте, скільки елементів потрібно зберегти під час виконання програми, ви можете скористатися зв’язаним списком. Пам’ять розподіляється динамічно, коли ви додаєте елементи до пов’язаних списків.
  • Довільний доступ: У сценарії, де вам не потрібно використовувати довільний доступ з елементів, ви можете використовувати пов’язаний список.
  • Вставка посередині: Вставка в середину масиву є складним завданням. Тому що потрібно штовхати інші елементи вправо. Однак пов’язаний список дозволяє додавати елемент до будь-якої позиції, яку ви хочете.

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
Вставка в голову
Вставка в голову

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

Вставлення вузла в кінець пов’язаного списку має певну схожість із вставленням у заголовок. Все, що вам потрібно зробити, це перейти до кінцевого або хвостового вузла. Потім наведіть «наступний» вузол кінцевого вузла на щойно створений вузол. Якщо головний вузол дорівнює нулю, новий вузол буде головним вузлом.

Ось кроки:

Крок 1) Переходьте, поки «наступний» вузол поточного вузла не стане нульовим.

Крок 2) Створіть новий вузол із вказаним значенням.

Крок 3) Призначте новий вузол як наступний вузол хвостового вузла.

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

function insertAtEnd( head, value ):
	newNode = Node(value)
	if head is NULL:
		head = newNode
		return head
	while head.next is not NULL:
		then head = head.next
	head.next = newNode
	newNode.next = NULL
Вставка біля хвоста
Вставка біля хвоста

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

Вставлення після вузла складається з двох частин: пошук вузла та приєднання після шуканого вузла. Нам потрібно пройти всі вузли. Для кожного вузла нам потрібно зіставити з пошуковим елементом. Якщо знайдеться збіг, ми додамо новий вузол після шуканого вузла.

Ось кроки:

Крок 1) Переходьте до наступного вузла, поки значення поточного вузла не зрівняється з елементом пошуку.

Крок 2) Наступний покажчик нового вузла буде наступним покажчиком поточного вузла.

Крок 3) Наступним вузлом поточного вузла буде новий вузол.

Ось псевдокод для вставки вузла після вузла:

function insertAfter( head, value, searchItem ):
	newNode = Node(value)
	while head.value equals searchItem:
		then head = head.next
	newNode.next = head.next.next
	head.next = newNode
Вставлення вузла після вузла в однозв’язаний список
Вставлення вузла після вузла в однозв’язаному списку

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

Ця функція дуже схожа на вставку після вузла. Ми повинні створити новий вузол і переходити по пов’язаному списку, поки поточний вузол не збігатиметься з пошуковим вузлом. Після цього ми додамо новий вузол як попередній вузол поточного вузла.

Ось кроки:

Крок 1) Переміщайтеся, поки значення наступного вузла не зрівняється з елементом пошуку.

Крок 2) Створіть новий вузол і призначте «наступний» вузлу з наступним за наступним вузлом поточного вузла.

Крок 3) Призначте новий вузол як наступний вузол поточного вузла.

Ось псевдокод:

function insertBefore( head, value, searchItem ):
	newNode = Node(value)
	while head.next.value equals searchItem:
		then head = head.next
	newNode.next = head.next.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 is not equals searchItem :
		head = head.next
	head.next = head.next.next
	delete(head.next)
Пошук і видалення вузла з однозв’язаного списку
Пошук і видалення вузла з однозв’язаного списку

Огляд однозв’язаного списку

Однозв’язаний список має лише функціональні можливості для проходження голови до хвоста. Немає вказівників на попередній вузол; ось чому ми не можемо пройти через однозв’язаний список у зворотному порядку. Ми будемо проходити кожен вузол і друкувати значення поточного вузла, доки не отримаємо значення null.

Ось кроки:

Крок 1) Переходьте по кожному вузлу, доки наступним вузлом не буде значення null.

Крок 2) Вивести значення поточного вузла.

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

function traverse( head ):
		while head.next is not NULL:
			print the value of the head
			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);
  }
  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 = new Node();
  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);
      }else{
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
}
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 = new 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.')
    return  
  def insertAtEnd(self,value):
    if self.head is None:
      self.insertAtHead(value)
    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):
    temp = Node()
    if self.head is searchItem:
      temp = self.head
      self.head = self.head.next
    else:
      currentNode = self.head
      while currentNode.next is not None:
        if currentNode.next.data is searchItem:
          temp = currentNode.next
          currentNode.next = currentNode.next.next
        else:
          currentNode = currentNode.next
    print(f'Deleted node\t{searchItem}')
    return
  def insertAfter(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
    return 
  def insertbefore(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
    return
  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).