Egyedül linkelt lista az adatstruktúrákban
Mi az az egyedileg linkelt lista?
A Singly Linked List egy lineáris és egyirányú adatstruktúra, ahol az adatok a csomópontokon kerülnek mentésre, és minden csomópont egy hivatkozáson keresztül kapcsolódik a következő csomóponthoz. Minden csomópont tartalmaz egy adatmezőt és egy hivatkozást a következő csomópontra. Az egyszeresen linkelt listák csak egy irányban, míg a Duplán linkelt listákon mindkét irányban bejárhatók.
Íme az egyszeresen linkelt lista csomóponti struktúrája:

Miért használjunk linkelt listát tömbön keresztül?
Számos eset van, amikor jobb a linkelt listát használni, nem pedig a Sor. Íme néhány forgatókönyv:
- Ismeretlen számú elem: Ha nem tudja, hány elemet kell tárolnia a program futása során, használhatja a Hivatkozási listát. A memóriafoglalás dinamikusan történik, amikor elemeket ad hozzá a hivatkozott listákhoz.
- Véletlenszerű hozzáférés: Egy olyan forgatókönyvben, ahol nem kell véletlenszerű hozzáférést használnia az elemekből, használhatja a csatolt listát.
- Beillesztés középen: A tömb közepébe történő beillesztés összetett feladat. Mert más elemeket jobbra kell tolni. A csatolt lista azonban lehetővé teszi, hogy tetszőleges pozícióhoz hozzáadjon egy elemet.
Operaaz egyedileg összekapcsolt lista
Az Singly Linked List alkalmas a memória dinamikus lefoglalására. Ez biztosítja a linkelt lista összes alapvető műveletét, azaz beszúrást, törlést, keresést, frissítést, két linkelt lista összevonását, bejárást stb.
Itt a hivatkozott lista következő műveletét tárgyaljuk:
- Beillesztés a fejnél
- Beillesztés a faroknál
- Beszúrás egy csomópont után
- Beszúrás egy csomópont elé
- Törölje a fejcsomópontot
- Törölje a farok csomópontot
- Csomópont keresése és törlése
- A linkelt lista bejárása
Íme egy példa egy négy csomópontot tartalmazó linkelt listára.
Beszúrás az egyszeresen linkelt lista élére
Ez egy egyszerű művelet. Általánosságban elmondható, hogy ez egy külön linkelt lista leküldése. Létre kell hoznia egy új csomópontot, és el kell helyeznie a hivatkozott lista élére.
A művelet végrehajtásához két fontos feltételt kell betartanunk. Ők
- Ha a lista üres, akkor az újonnan létrehozott csomópont lesz a fejcsomópont, a következő csomópont pedig „NULL”.
- Ha a lista nem üres, az új csomópont lesz a fő csomópont, a következő pedig az előző főcsomópontra mutat.
Íme a pszeudokód egy csomópont beszúrásához egy linkelt lista élére:
function insertAtHead( head, value ): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
Beszúrás az egyszeri hivatkozású lista végére
Egy csomópont beszúrása a hivatkozott lista végére némi hasonlóságot mutat a fejben történő beszúrással. Mindössze annyit kell tennie, hogy áthalad a végcsomóponthoz vagy a végcsomóponthoz. Ezután mutasson a végcsomópont „következő” csomópontjára az újonnan létrehozott csomópontra. Ha a fejcsomópont nulla, az új csomópont lesz a fejcsomópont.
Íme a lépések:
Step 1) Haladjon addig, amíg az aktuális csomópont „következő” csomópontja nullává nem válik.
Step 2) Hozzon létre egy új csomópontot a megadott értékkel.
Step 3) Rendelje hozzá az új csomópontot a végcsomópont következő csomópontjaként.
A pszeudokód egy csomópont beszúrásához egy egyedi lista végéhez:
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
Beszúrás egy csomópont után egy egyszeresen linkelt listában
A csomópont utáni beszúrás két részből áll: Keresse meg a csomópontot, és csatolja a keresett csomópont után. Be kell járnunk az összes csomópontot. Minden csomópontnál meg kell egyezni a keresési elemmel. Ha van egyezés, akkor a keresett csomópont után hozzáadjuk az új csomópontot.
Íme a lépések:
Step 1) Haladjon be a következő csomóponton, amíg az aktuális csomópont értéke nem lesz egyenlő a keresési elemmel.
Step 2) Az új csomópont következő mutatója az aktuális csomópont következő mutatója lesz.
Step 3) A jelenlegi csomópont következő csomópontja az új csomópont lesz.
Íme a pszeudokód egy csomópont utáni beszúráshoz:
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
Beszúrás egy csomópont elé egy egyszeresen linkelt listában
Ez a függvény sokban hasonlít a csomópont utáni beszúráshoz. Létre kell hoznunk egy új csomópontot, és végig kell haladnunk a hivatkozott listán, amíg az aktuális csomópont megegyezik a keresési csomóponttal. Ezt követően hozzáadjuk az új csomópontot az aktuális csomópont előző csomópontjaként.
Íme a lépések:
Step 1) Haladjon addig, amíg a következő csomópont értéke megegyezik a keresési elemmel.
Step 2) Hozzon létre egy új csomópontot, és rendelje hozzá a csomópont „következő”-jét az aktuális csomópont következő csomópontjához.
Step 3) Rendelje hozzá az új csomópontot az aktuális csomópont következő csomópontjaként.
Íme a pszeudokód:
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
Törölje az egyszeresen hivatkozott lista fejét
A linkelt lista minden funkciójában a fejmutató paraméterként szerepel. Törölnie kell a fejcsomópontot, és a főcsomópont következő csomópontját kell a hivatkozott lista új fejévé tenni. A törölt csomópont memóriáját is fel kell szabadítanunk. Ellenkező esetben a memória foglaltként lesz megjelölve, amikor egy másik program megpróbál hozzáférni.
A következő lépésekkel törölheti az egyedileg összekapcsolt lista fejlécét:
Step 1) Rendelje hozzá a fejcsomópont következő csomópontját új fejként.
Step 2) Szabadítsa fel az előző fejcsomópont által lefoglalt memóriát.
Step 3) Adja vissza az új fejcsomópontot.
A fejcsomópont törlésének pszeudokódja:
function deleteHead( head ): temp = head head = head.next free( temp ) return head
Törölje az egyedileg hivatkozott lista végét
A végcsomópont törlése jobban ismeri a fejcsomópont törlését. A különbség az, hogy a linkelt lista végére kell lépnünk, és törölnünk kell. Az egyedileg összekapcsolt listában az a csomópont, amelynek a következő csomópontja „NULL”, a végcsomópont.
Íme a linkelt lista végcsomópontjának törlésének lépései:
Step 1) Haladjon át a farokcsomópont előtt. Mentse az aktuális csomópontot.
Step 2) Szabadítsa fel az aktuális csomópont következő csomópontjának memóriáját.
Step 3) Állítsa az aktuális csomópont következő csomópontját NULL-ra.
Íme a pszeudokód a farok csomópont törléséhez:
function deleteTail( head ): while head.next.next is not NULL: head = head.next free( head.next ) head.next = NULL
Csomópont keresése és törlése egyedileg összekapcsolt listából
Ennek a funkciónak két feladata van: keresés és törlés. Az egyszeresen linkelt listák végéig kell keresnünk. Ha találunk hasonló csomópontot, töröljük azt. Ezt követően össze kell vonnunk vagy összekapcsolnunk a törölt csomópont bal és jobb oldali csomópontját. Íme a lépések ehhez:
Step 1) Haladjon végig a hivatkozott lista végéig. Ellenőrizze, hogy az aktuális csomópont megegyezik-e a keresési csomóponttal.
Step 2) Ha valamelyik csomópont egyezik, tárolja a csomópontmutatót az aktuális csomópontra.
Step 3) Az előző csomópont „következője” az aktuális csomópont következő csomópontja lesz.
Step 4) Törölje és szabadítsa fel az aktuális csomópont memóriáját.
Pszeudokód a kereséshez és egy csomópont törléséhez egy egyedileg csatolt listából:
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)
Végezzen végig egy külön linkelt listát
Az egyedileg összekapcsolt listák csak a fejtől a farokig való áthaladáshoz szükséges funkciókkal rendelkeznek. Nincsenek mutatópontok az előző csomópontra; ezért nem tudjuk fordított sorrendben bejárni a Singly Linked List listát. Bejárjuk az egyes csomópontokat, és kinyomtatjuk az aktuális csomópont értékét, amíg nullát nem kapunk.
Íme a lépések:
Step 1) Haladjunk végig minden csomóponton, amíg nullát nem kapunk következő csomópontként.
Step 2) Nyomtassa ki az aktuális csomópont értékét.
Pszeudokód egy egyedileg kapcsolódó lista bejárásához:
function traverse( head ): while head.next is not NULL: print the value of the head head = head.next
Példa az egyedileg linkelt listára 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); }
output:
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
Példa az egyedileg linkelt listára Python Program
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()
output:
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
Az egyedileg összekapcsolt lista összetettsége
Kétféle komplexitás létezik: időbonyolultság és térbonyolultság. A legrosszabb és átlagos eseti idő bonyolultsága megegyezik az Egyszeri linkelt lista esetében.
Időbeli összetettség a legjobb esetben:
- A fejbe való beillesztés az O(1)-ben történhet. Mivel nem kell bejárnunk a linkelt listán belül.
- A keresési és törlési művelet az O(1)-ben végezhető el, ha a keresőelem jelen van a fejcsomópontban.
Az átlagos eset időbeli összetettsége:
- A linkelt listán belüli beszúrás O(n) értéket vesz igénybe, ha „n” elem szerepel az Egyszeri linkelt listában.
- A keresés és a törlés O(n)-t is igénybe vehet, mivel a keresési elem jelen lehet a végcsomópontban. Ebben az esetben a teljes listát be kell járnia.
Az egyedileg összekapcsolt lista térkomplexitása
Az Singly Linked List dinamikusan lefoglalja a memóriát. Ha n elemet akarunk tárolni, akkor n memóriaegységet foglal le. Tehát a tér komplexitása O(n).