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.
Megközelíthetősé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.