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:

Csomópont szerkezete egy linkelt listában
Csomópont szerkezete egy linkelt listában

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.

Példa egy egyedileg linkelt listára
Példa egy egyedileg 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

  1. Ha a lista üres, akkor az újonnan létrehozott csomópont lesz a fejcsomópont, a következő csomópont pedig „NULL”.
  2. 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
Beillesztés a fejnél
Beillesztés a fejnél

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
Beillesztés a faroknál
Beillesztés a faroknál

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
Csomópont beszúrása egy csomópont után az egyszeresen linkelt listában
Csomópont beszúrása egy csomópont után az egyszeri hivatkozások listáján

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
Csomópont beszúrása egy csomópont elé az egyszeresen csatolt listában
Csomópont beszúrása egy csomópont elé az egyszeresen csatolt listában

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
Hivatkozott lista fejének törlése
Hivatkozott lista fejlécének törlése

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
Az Egyedül linkelt lista végének törlése
Az Egyedül linkelt lista végének törlése

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)
Csomópont keresése és törlése az egyszeri hivatkozások listájáról
Csomópont keresése és törlése az egyszeri hivatkozások listájából

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).