Единично свързан списък в структури от данни
Сара Чен
Какво е единично свързан списък?
Единично свързаният списък е линейна и еднопосочна структура от данни, където данните се записват на възлите и всеки възел е свързан чрез връзка към следващия си възел. Всеки възел съдържа поле за данни и връзка към следващия възел. Единично свързаните списъци могат да бъдат обхождани само в една посока, докато двойно свързаните списъци могат да бъдат обхождани и в двете посоки.
Ето структура на възел на единично свързан списък:
Защо да използвате свързан списък върху масив?
Има няколко случая, когато е по-добре да използвате свързания списък, а не Array. Ето някои сценарии:
- Неизвестен брой елементи: Когато не знаете колко елемента трябва да съхраните по време на изпълнение на програмата, можете да използвате свързания списък. Паметта се разпределя динамично, докато добавяте елементи към свързаните списъци.
- Произволен достъп: В сценарий, при който не е необходимо да използвате произволен достъп от елементите, можете да използвате свързания списък.
- Вмъкване в средата: Вмъкването в средата на масив е сложна задача. Защото трябва да натиснете други елементи надясно. Свързаният списък обаче ви позволява да добавите елемент към всяка позиция, която искате.
Operaции на единично свързан списък
Единично свързаният списък е добър за динамично разпределяне на паметта. Той предоставя всички основни операции на свързания списък, т.е. вмъкване, изтриване, търсене, актуализиране, сливане на два свързани списъка, преминаване и т.н.
Тук ще обсъдим следната операция на свързания списък:
- Вмъкване в главата
- Вмъкване на опашката
- Вмъкване след възел
- Вмъкване преди възел
- Изтрийте главния възел
- Изтрийте опашния възел
- Търсене и изтриване на възел
- Обхождане на свързания списък
Ето пример за свързан списък с четири възела.
Вмъкване в началото на единично свързан списък
Това е проста операция. Като цяло, това е известно като натискане на единично свързан списък. Трябва да създадете нов възел и да го поставите в началото на свързания списък.
За да извършим тази операция, трябва да спазим две важни условия. Те са
- Ако списъкът е празен, тогава новосъздаденият възел ще бъде главният възел, а следващият възел на главата ще бъде ”NULL”.
- Ако списъкът не е празен, новият възел ще бъде главният възел, а следващият ще сочи към предишния главен възел.
Ето псевдокода за вмъкване на възел в началото на свързан списък:
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)
Преминаване през единично свързан списък
Единично свързаният списък има само функционалност за преминаване от главата до опашката. Няма указателни точки към предишния възел; ето защо не можем да преминем през единично свързания списък в обратен ред. Ще преминем през всеки възел и ще отпечатаме стойността на текущия възел, докато получим нула.
Ето стъпките:
Стъпка 1) Обхождайте всеки възел, докато не получим нула като следващия възел.
Стъпка 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).
