Единично свързан списък в структури от данни

Какво е единично свързан списък?

Едносвързаният списък е линейна и еднопосочна структура от данни, където данните се съхраняват във възлите и всеки възел е свързан чрез връзка със следващия си възел. Всеки възел съдържа поле за данни и връзка към следващия възел. Едносвързаните списъци могат да се обхождат само в една посока, докато Двойно свързан списък може да се преминава в двете посоки.

Ето структурата на възлите на едносвързан списък:

Структура на възел в свързан списък

Защо да използваме свързан списък върху масив?

Няколко сценария предпочитат свързан списък пред Array:

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

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

Вмъкване в главата

Вмъкване в края на едносвързан списък

Вмъкването на възел в края на свързан списък е подобно на вмъкването в началото. Преминете към опашния възел, след което насочете неговия до указател към новия възел. Ако началният възел е 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

Вмъкване на възел преди възел в единично свързан списък

Изтриване на заглавието на едносвързания списък

Указателят на „head“ възел се предоставя като параметър. Главният възел се премахва и следващият възел става новият „head“. Паметта на изтрития възел трябва да бъде освободена, за да се избегнат изтичания на памет.

Стъпка 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 свободни блока като еднократно свързан списък.

Въпроси и Отговори