Duplán linkelt lista: C++, Python (Példa a kódra)

By: Sarah Chen Sarah Chen
Hours korszerűsített

Mi az a duplán linkelt lista?

Egy duplán linkelt listában minden csomópont rendelkezik hivatkozással az előző és a következő csomópontra is. Minden csomópont három elemből áll: az egyik az adatokat tartalmazza, a másik kettő pedig a következő és az előző csomópont mutatója. Ez a két mutató segít egy adott csomóponttól előre vagy hátrafelé haladni.

Íme a duplán linkelt lista alapstruktúrája.

Duplán linkelt lista felépítése
Duplán linkelt lista felépítése

Minden csatolt listának van fej- és farokcsomópontja. A fej csomópontnak nincs „előző” (előző mutató) csomópontja, és a farok csomópontnak nincs „következő” csomópontja.

Íme néhány fontos kifejezés egy duplán linkelt listához:

  • Előző: Minden csomópont kapcsolódik az előző csomópontjához. Mutatóként vagy hivatkozásként használják.
  • Következő: Minden csomópont a következő csomóponthoz kapcsolódik. Mutatóként vagy hivatkozásként használják.
  • Adatok: Ez adatok tárolására szolgál egy csomópontban. Az „adatok” mást is tartalmazhatnak Adatstruktúrák benne. Például karakterlánc, szótár, halmaz, hashmap stb. tárolható az „Adatok” között.

Íme egy csomópont alapstruktúrája a duplán linkelt listában:

Csomópont felépítése duplán linkelt listában

Csomópont szerkezete duplán linkelt listában

OperaKettős hivatkozású lista

A duplán linkelt lista műveletei közé tartozik a csomópontok hozzáadása és törlése, csomópontok beszúrása és eltávolítása, valamint a hivatkozott lista bejárása felülről lefelé.

Íme azoknak a műveleteknek a listája, amelyeket a duplán linkelt lista segítségével végrehajthatunk:

  • Beillesztés elöl
  • Beillesztés a farokba vagy az utolsó csomópontba
  • Beillesztés egy csomópont után
  • Beillesztés egy csomópont elé
  • Törlés elölről
  • Törlés a farokból
  • Keressen és töröljön egy csomópontot
  • Fejtől farokig haladva
  • Fordítsd a farkát a fejhez

Látni fogjuk az összes fenti művelet megvalósítását és pszeudokódját.

Beszúrás a Duplán linkelt lista elé

Az elülső beillesztés azt jelenti, hogy létre kell hoznunk egy csomópontot a hivatkozott listában, és el kell helyeznünk a hivatkozott lista elejére.

Például van egy adott „15” csomópont. Ezt hozzá kell adnunk a fejcsomóponthoz.

Íme két fontos feltétel a művelet végrehajtása során:

  1. Az új csomópont a fő csomópont lesz, ha nincs csomópont a Duplán linkelt listában.
  2. Ha már van fejcsomópont, az előző fejet felváltja az új csomópont.

Íme a művelet pszeudokódja:

function insertAtFront (ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = NewNode
  NewNode.next = ListHead
  newNode.prev = NULL
  return ListHead
Beillesztés az elülső csomópontba
Beillesztés az elülső csomópontba

Beszúrás a Duplán linkelt lista végére

A „Beszúrás a végén” azt jelenti, hogy létrehozunk egy csomópontot a hivatkozott listában, és a végére helyezzük.

Ennek végrehajtásához két módszert használhatunk:

  • 1 módszer: Kezdje el a bejárást a Duplán linkelt lista fejétől, amíg a „következő” nullává nem válik. Ezután kapcsolja össze az új csomópontot a „következővel”.
  • 2 módszer: Vegyük a Duplán linkelt lista utolsó csomópontját. Ezután az utolsó csomópont „következő” csomópontja kapcsolódik az új csomóponthoz. Most az új csomópont a végcsomópont lesz.

Íme a pszeudokód a farok csomópontba történő beszúráshoz:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
	then ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead
Beszúrás a linkelt lista végére

Beillesztés a linkelt lista végére

KAPCSOLÓDÓ CIKKEK

Beillesztés egy csomópont után

Tegyük fel, hogy van egy duplán linkelt listánk, például a következő:

Beillesztés egy csomópont után

Egy adott csomópontot szeretnénk beszúrni, amely a „12” értékű csomópont után lesz csatolva.

Íme a lépések ehhez:

Step 1) Haladjon át a fejtől az utolsó csomópontig. Ellenőrizze, hogy melyik csomópont értéke „12”.

Step 2) Hozzon létre egy új csomópontot, és rendelje hozzá a „12” csomópont következő mutatójaként. Az új csomópont „következő” csomópontja a 15.

Íme a pszeudokód egy csomópont beszúrásához egy duplán linkelt listában lévő csomópont után:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.value is not equal searchItem
	then List = ListHead.next
  List = List.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode
Beillesztés egy csomópont után

Beillesztés egy csomópont után

Beillesztés egy csomópont elé

Ez a művelet jobban hasonlít a „csomópont utáni beszúráshoz”. Ehhez meg kell keresnünk egy adott csomópont értékét. Ezután létrehozunk egy új csomópontot, és beillesztjük a keresett csomópont elé.

Tegyük fel, hogy egy adott „15” csomópontot szeretnénk beszúrni a „12” csomópont elé. Akkor íme a lépések ennek végrehajtásához:

Step 1) Haladjon át a hivatkozott listán a fő csomóponttól a végcsomópontig.

Step 2) Ellenőrizze, hogy az aktuális csomópont következő mutatójának értéke „12” vagy sem.

Step 3) Szúrja be az új csomópontot az aktuális csomópont „következő” csomópontjaként.

Íme a pszeudokód egy csomópont beszúrásához egy csomópont elé a duplán linkelt listában:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  NewNode = Node()
  NewNode.value = value
  while List.next.value is not equal searchItem
	then List = ListHead.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode
Csomópont beszúrása csomópont elé

Csomópont beszúrása csomópont elé

Törölje a duplán linkelt lista fejét

A duplán linkelt lista fejcsomópontja, amelyhez nem tartozik korábbi csomópont. Tehát a következő mutató az új fejcsomópont lesz, ha törölni akarjuk a fejcsomópontot. A csomópont törlése közben a csomópont által elfoglalt memóriát is fel kell szabadítanunk.

A fejcsomópont törlésének lépései a következők:

Step 1) Változó hozzárendelése az aktuális fejcsomóponthoz.

Step 2) Látogassa meg az aktuális fejcsomópont „következő” csomópontját, és tegye az „előző” (előző mutató) csomópontot „NULL” értékre. Ez azt jelenti, hogy leválasztjuk a második csomópontot az első csomópontról.

Step 3) Az előző fejcsomópont által lefoglalt memória felszabadítása.

Íme az pszeudokód a fej törléséhez egy duplán linkelt listából:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead
A fejcsomópont törlése

A fejcsomópont törlése

Bármilyen törlési művelet elvégzése után törölni kell a lefoglalt memóriát. Ellenkező esetben a program teljes futási ideje alatt a törölt blokk memóriája foglalt marad. Más alkalmazás nem tudja használni ezt a memóriaszegmenst.

Törölje a duplán linkelt lista végét.

Ez a művelet nagyjából megegyezik a fej törlésével. Itt a fej helyett a farkot kell törölnünk. Ahhoz, hogy egy csomópontot végcsomópontként azonosítsunk, ellenőriznünk kell, hogy a következő mutató vagy a következő csomópont nulla-e vagy sem. A farok törlése után fel kell szabadítanunk a memóriát.

Ezt a műveletet „hátulról való törlésnek” is nevezik.

Íme a lépések ehhez:

Step 1) Haladjon a duplán linkelt lista végcsomópontjáig.

Step 2) Változó vagy mutató hozzárendelése a végcsomóponthoz.

Step 3) Tegye a „következő” csomópontot NULL-ként, és szabadítsa fel a végcsomópont memóriáját.

Íme a pszeudokód a farok csomópont törléséhez:

function DeleteTail( ListHead ):
  head = ListHead
  while ListHead.next is not NULL:
	ListHead = ListHead.next
  Tail = ListHead.next
  ListHead.next = NULL
  free memory( Tail )
  return head

Törölje a Duplán összekapcsolt farkát

Keressen és töröljön egy csomópontot a Duplán linkelt listából

Ez a művelet lehetővé teszi, hogy egy adott csomópont adatait keressük, és töröljük azt. Lineáris keresést kell végrehajtanunk, mivel a linkelt lista egy lineáris adatstruktúra. A törlés után a memóriát is fel kell szabadítanunk.

Íme a lépések egy csomópont kereséséhez és törléséhez a duplán linkelt listában:

Step 1) Haladjon végig a hivatkozott listán a fejtől egészen addig, amíg a csomópont értéke megegyezik a keresési elemmel.

Step 2) Rendeljen egy „deleteNode” változót az illesztett csomóponthoz.

Step 3) Rendelje hozzá a „deleteNode” előző csomópontját a következő csomóponthoz.

Step 4) Szabadítsa fel a „deleteNode” memóriáját

Íme a pszeudokód a linkelt listából egy csomópont kereséséhez és törléséhez:

function SearchAndDelete(ListHead, searchItem):
  head = ListHead
  while ListHead.next.value not equals searchItem:
	head = head.next
  deleteNode = head.next
  head.next = head.next.next
  head.next.prev = head
  deleteNode.next, deleteNode.next = NULL
  free memory(deleteNode)
  return ListHead
Keresés és törlés OperaCIÓ

Keresés és törlés művelet

Bejárás egy duplán linkelt listán elölről

A fejcsomópontból való áthaladáshoz és a következő csomóponton való iterációhoz, amíg meg nem találjuk a „NULL”-t. Az egyes csomópontok bejárása közben kinyomtathatjuk a csomópont értékét. Íme a lépések az elölről való haladáshoz (előre):

Step 1) Rendeljen mutatót vagy változót az aktuális fejcsomóponthoz.

Step 2) Iteráljon a fej következő csomópontjához, amíg a „NULL” értéket nem kapja

Step 3) Nyomtassa ki a csomópont adatait minden iterációban.

Step 4) Vissza a fejcsomópontot.

Íme a pszeudokód a kettős hivatkozású lista elölről történő bejárásához:

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals to NULL:
	print head.data
	head = head.next
  return ListHead

Itt a visszaküldés nem kötelező. De jó gyakorlat a fejcsomópont visszaadása a műveletek után.

Menjen át egy duplán linkelt listán visszafelé

Ez a művelet az elölről történő átmenet fordítottja. A megközelítés ugyanaz, kis eltéréssel. Át kell haladnunk a végcsomópontig, majd a végcsomóponttól az elülső csomópontig.

Íme a lépések a duplán linkelt lista hátulról történő bejárásához:

Step 1) Haladjunk addig, amíg el nem érjük a farok csomópontját.

Step 2) A farok csomóponttól addig haladunk, amíg az előző csomópontot „NULL”-ként nem kapjuk. A „prev” (előző mutató) nulla lesz a fejcsomópontnál

Step 3) Minden iterációnál kinyomtatjuk a csomópont adatait.

Íme a pszeudokód a hátulról történő bejáráshoz:

function traverseFromBack(ListHead):
  head = ListHead
  while head not equals NULL:
	head = head.next
  tail = head
  while tail not equal to NULL:
	print tail.value
	tail = tail.prev
  return ListHead

Különbség az egyszeri és duplán linkelt lista között

A fő különbség az Singly és a Duplán linkelt lista között a hivatkozások száma.

Különbség az egyszeri és duplán linkelt lista között

Íme a különbség az egyszeresen linkelt lista csomópontjai és a duplán linkelt lista csomópontszerkezete között:

Mező Egyedül linkelt lista Duplán linkelt lista
Szerkezet Egyedül linkelt lista egy adatmezővel és egy hivatkozással rendelkezik a következő csomópontra. A Duplán linkelt lista egy adatmezőt és két hivatkozást tartalmaz. Egy az előző csomóponthoz, egy másik a következő csomóponthoz.
A bejárás Csak fejtől farokig képes áthaladni. Előre és hátra is haladhat.
Memory design Kevesebb memóriát foglal el. Több memóriát foglal el, mint egy külön linkelt lista.
Akadálymentesség Az egyszeresen linkelt listák kevésbé hatékonyak, mivel csak egy hivatkozást használnak a következő csomóponthoz. Nincs hivatkozás az előző csomóponthoz. A duplán linkelt listák hatékonyabbak, mint az egyszeresen linkelt listák.

Duplán linkelt lista be C++

#include<iostream>
using namespace std;
  struct node{
  int data;
  struct node *next;
  struct node *prev;
  };
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead!=NULL)
  {
	listHead->prev = newNode;
  	newNode->next = listHead;
  }
  
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
  }
void insertEnd(node * &listHead, int value){
  if(listHead==NULL)
  {
  	insertFront(listHead,value);
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next!=NULL){
  head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
  }
void insertAfter(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;
  node *head = listHead;	
  while(head->next!=NULL &&  head->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
  }
void insertBefore(node * &listHead, int searchValue,int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;	
  newNode->next = NULL;	
  node *head = listHead;	
  while(head->next!=NULL &&  head->next->data!=searchValue){	
  head = head->next;	
  }	
  newNode->next = head->next;	
  head->next = newNode;	
  newNode->prev = head;	
  if(newNode->next !=NULL){	
  newNode->next->prev = newNode;	
  }	
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;	
  }
void traverseFromFront(node *listHead){
  node* head = new node();
  head = listHead;
  cout<<"Traversal from head:\t";	
  while(head!=NULL){	
  cout<<head->data<<"\t ";	
  head = head->next;	
  }	
  cout<<endl;
  }	
void traverseFromEnd(node *listHead){
  node* head = new node();
  head = listHead;	
  cout<<"Traversal from head:\t";	
  while(head->next!=NULL){	
  head = head->next;	
  }	
  node *tail = head;	
  while(tail!=NULL){	
  cout<<tail->data<<"\t";	
  tail = tail->prev;	
  }	
  cout<<endl;	
  }
void searchAndDelete(node **listHead, int searchItem){
  node* head = new node();
  head = (*listHead);
  while(head->next!=NULL &&  head->data!=searchItem){
  head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
  	*listHead = head->next;
  }
  if(head->next != NULL){
  	head->next->prev = head->prev;
  }
  
  if(head->prev != NULL){
  	head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
  }
int main(){
  node *head = NULL;
  insertFront(head,5);
  insertFront(head,6);
  insertFront(head,7);
  insertEnd(head,9);
  insertEnd(head,10);
  insertAfter(head,5,11);
  insertBefore(head,5,20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head,7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

teljesítmény

Added 5 at the front
Added 6 at the front
Added 7 at the front
Aded 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7        6       20      5       11      9       10
Traversal from head:    10      9       11      5       20      6       7
Deleted Node    7
Traversal from head:    6        20      5       11      9       10
Traversal from head:    10      9       11      5       20      6

Duplán linkelt lista be Python

class node:
  def __init__(self,data = None, prev=None, next = None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None

  def insertFront(self, val):
    newNode = node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))

  def insertEnd(self,val):
    newNode = node(data=val)
    if self.head is None:
      self.insertFront(val)
    
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))

  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t",end="")
    while temp:
      print("{}\t".format(temp.data),end="")
      temp = temp.next
    print()

  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from Tail:\t",end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data),end="")
      tail = tail.prev
    print()
  
  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
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value,searchItem))

  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
    newNode.prev = temp

    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value,searchItem))

  def searchAndDelete(self,searchItem):
    temp = self.head

    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    
    if self.head is None or temp is None:
      return

    if self.head.data is temp.data:
      self.head = temp.next

    if temp.next is not None:
      temp.next.prev = temp.prev
    
    if temp.prev is not None:
      temp.prev.next = temp.next
    
    print("Deleted Node\t{}".format(searchItem))
    return

doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

teljesítmény

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7       6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6       7
Deleted Node    7
Traversing from head:   6       20      5       11      9       10
Traversing from Tail:   10      9       11      5       20      6

A duplán linkelt lista összetettsége

Általában az időbonyolultság három típusra osztható.

Ők:

  1. Legjobb eset
  2. Átlagos eset
  3. Legrosszabb esetben

Időbonyolultság a legjobb esetben a Duplán linkelt lista esetén:

  1. A fejbe vagy a farokba való behelyezés O(1)-be kerül. Mert nem kell bejárnunk a linkelt listán belül. A fej és a farokmutató hozzáférést biztosít számunkra a fej és a farok csomópontjához O(1) időbonyolítással.
  2. A fej vagy a farok törlése O(1)-be kerül.
  3. Egy csomópont keresése O(1) időbonyolultságú lesz. Mert a célcsomópont lehet a fejcsomópont.

Időbeli összetettség átlagos esetben a Duplán linkelt lista esetében:

  1. A fejnél vagy a faroknál történő beillesztés az O(1) költség időbonyolításával jár.
  2. A fejnél vagy a végnél történő törlés az O(1) költség időbonyolításával jár.
  3. Egy csomópont keresése O(n) időbonyolultságú lesz. Mivel a keresett elem a hivatkozott lista között bárhol elhelyezkedhet. Itt az „n” a hivatkozott listában található összes csomópont.

A duplán linkelt lista legrosszabb eseti összetettsége megegyezik az átlagos esettel.

A Duplán linkelt lista memória összetettsége

A memória összetettsége O(n), ahol „n” a csomópontok teljes száma. A linkelt lista megvalósítása során fel kell szabadítani a használt memóriát. Ellenkező esetben egy nagyobb linkelt lista esetén memóriaszivárgást okoz.

Összegzésként

  • A linkelt lista egyfajta lineáris adatstruktúra, lineárisan ábrázolt adatok gyűjteménye.
  • A duplán linkelt lista olyan csatolt lista, amelyben egy csomópont az előző és a következő csomóponthoz is kapcsolódik.
  • A duplán csatolt lista tartalmazza az összes műveletet, például csomópont hozzáadása, csomópont törlése, csomópont beszúrása egy másik csomópont mögé vagy elé, és a hivatkozott lista bejárása a fejtől a végig.
  • A Duplán linkelt lista egy adatmezőt és két hivatkozást tartalmaz. Egy az előző csomóponthoz, egy másik a következő csomóponthoz.
  • A Duplán linkelt lista összetettsége Legjobb eset, Átlagos eset
  • És a legrosszabb eset.