Kaksoislinkitetty lista: C++, Python (Code esimerkki)

Mikä on kaksinkertaisesti linkitetty lista?

Kaksinkertaisesti linkitetyssä listassa jokaisella solmulla on linkit sekä edelliseen että seuraavaan solmuun. Jokainen solmu koostuu kolmesta elementistä: yksi sisältää datan ja kaksi muuta ovat osoittimia seuraavaan ja edelliseen solmuun. Nämä kaksi osoitinta auttavat liikkumaan eteen- tai taaksepäin tietystä solmusta.

Tässä on kaksinkertaisesti linkitetyn listan perusrakenne.

Kaksinkertaisesti linkitetyn luettelon rakenne

Jokaisella linkitetyllä listalla on pääsolmu ja häntäsolmu. Pääsolmulla ei ole prev (edellinen osoitin) -solmu, ja häntäsolmulla ei ole seuraava solmu.

Tässä on joitakin tärkeitä termejä kaksinkertaisesti linkitetylle listalle:

• Edellinen: Jokainen solmu on linkitetty edelliseen solmuun. Sitä käytetään osoittimena tai linkkinä.
• Seuraava: Jokainen solmu on linkitetty seuraavaan solmuun. Sitä käytetään osoittimena tai linkkinä.
• Tiedot: Tätä käytetään datan tallentamiseen solmuun. Data voi sisältää muita Tietorakenteet sen sisällä. Esimerkiksi merkkijono, sanakirja, joukko, hashmap ja muita rakenteita voidaan tallentaa datakenttään.

Tässä on yksittäisen solmun perusrakenne kaksinkertaisesti linkitetyssä listassa:

Solmun rakenne kaksoislinkitetyssä luettelossa

Operakaksoislinkitettyjen luetteloiden

Kaksinkertaisesti linkitetyn listan toimintoihin kuuluvat solmujen lisääminen, poistaminen, lisääminen ja poistaminen sekä listan läpikäyminen ylhäältä alas tai alhaalta ylös.

Tässä on luettelo operaatioista, jotka voidaan toteuttaa kaksinkertaisesti linkitetyllä listalla:

• Lisäys edessä
• Lisäys häntään tai viimeiseen solmuun
• Lisäys solmun jälkeen
• Lisäys ennen solmua
• Poisto edestä
• Poisto hännästä
• Etsi ja poista solmu
• Kulje päästä häntään
• Siirrä häntä päähän

Näiden operaatioiden toteutus ja pseudokoodi seuraavat alla.

Lisäys kaksinkertaisesti linkitetyn listan eteen

Lisäys eteen tarkoittaa solmun luomista linkitettyyn listaan ​​ja sen sijoittamista listan alkuun.

Esimerkiksi on olemassa tietty solmu 15Se on lisättävä pääsolmuksi.

Tämän operaation suorittamiseen sovelletaan kahta tärkeää ehtoa:

1. Uudesta solmusta tulee pääsolmu, jos kaksinkertaisesti linkitetty lista on tyhjä.
2. Jos pääsolmu on jo olemassa, uusi solmu korvaa edellisen pääsolmun.

Tässä on tämän operaation pseudokoodi:

function insertAtFront(ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = newNode
  newNode.next = ListHead
  newNode.prev = NULL
  return ListHead

Lisäys etusolmuun

Lisäys kaksinkertaisesti linkitetyn listan loppuun

Lisäys loppuun tarkoittaa solmun luomista linkitettyyn listaan ​​ja sen sijoittamista listan häntään.

Kaksi menetelmää suorittaa tämän toiminnon:

• Menetelmä 1: Aloita läpikulku kaksinkertaisesti linkitetyn listan alusta, kunnes seuraava tulee tyhjäksi. Linkitä sitten uusi solmu seuraava osoitin.
• Menetelmä 2: Otetaan kaksinkertaisesti linkitetyn listan viimeinen solmu. Sitten seuraava Viimeisen solmun osoitin osoittaa uuteen solmuun. Uudesta solmusta tulee häntäsolmu.

Tässä on pseudokoodi lisäykselle häntäsolmuun:

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Lisäys linkitetyn luettelon loppuun

Lisäys solmun jälkeen

Tarkastellaan olemassa olevaa kaksinkertaisesti linkitettyä listaa, kuten seuraavaa:

Tavoitteena on lisätä tietty solmu, joka linkitetään arvoa käyttävän solmun jälkeen 12.

Vaihe 1) Siirry alusta viimeiseen solmuun. Tarkista, millä solmulla on arvo 12.

Vaihe 2) Luo uusi solmu ja aseta se solmun seuraavaksi osoittimeksi 12. seuraava Uuden solmun solmu on 15.

Tässä on pseudokoodi solmun lisäämiseksi solmun jälkeen kaksinkertaisesti linkitettyyn listaan:

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Lisäys solmun jälkeen

Lisäys ennen solmua

Tämä operaatio on samanlainen kuin lisäys solmun jälkeen. Tietyn solmun arvon perusteella etsitään, minkä jälkeen luodaan uusi solmu ja lisätään etsityn solmun edelle.

Annetun solmun lisääminen 15 ennen solmua 12, toimi seuraavasti:

Vaihe 1) Kulje linkitetty luettelo pääsolmusta loppusolmuun.

Vaihe 2) Tarkista, onko nykyisen solmun seuraavalla osoittimella arvo 12.

Vaihe 3) Lisää uusi solmu nimellä seuraava nykyisen solmun solmu.

Tässä on pseudokoodi solmun lisäämiseksi ennen solmua kaksinkertaisesti linkitettyyn listaan:

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.next.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Solmun lisääminen ennen solmua

Poista kaksinkertaisesti linkitetyn listan pää

Kaksinkertaisesti linkitetyn listan pääsolmulla ei ole aiempaa solmua. Joten seuraava osoittimesta tulee uusi pääsolmu, kun nykyinen pääsolmu poistetaan. Poistetun solmun käyttämän muistin vapauttaminen on myös tarpeen.

Tässä ovat pääsolmun poistamisen vaiheet:

Vaihe 1) Määritä muuttuja nykyiseen pääsolmuun.

Vaihe 2) Käy seuraava nykyisen pääsolmun solmu ja tee prev osoitin NULL. Tämä katkaisee toisen solmun yhteyden ensimmäiseen solmuun.

Vaihe 3) Vapauta edellisen pääsolmun käyttämä muisti.

Tässä on pseudokoodi otsikon poistamiseksi kaksinkertaisesti linkitetystä listasta:

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Pääsolmun poistaminen

Varatun muistin vapauttaminen minkä tahansa poiston jälkeen on tarpeen. Muussa tapauksessa poistetun lohkon muisti pysyy varattuna koko ohjelman suorituksen ajan, eikä mikään muu sovellus voi käyttää kyseistä muistisegmenttiä.

Poista kaksinkertaisesti linkitetyn listan häntä

Tämä operaatio on samanlainen kuin luvun "pää" poistaminen. luvun "pää" sijaan poistetaan luvun "häntä". Solmun tunnistamiseksi luvun "häntäksi" tarkistetaan, onko seuraava osoitin tyhjä (null). Luvun "häntä" poistamisen jälkeen muisti on vapautettava.

Tämä operaatio tunnetaan myös nimellä poisto takaa.

Voit tehdä tämän seuraavasti:

Vaihe 1) Käydään läpi kaksinkertaisesti linkitetyn listan häntäsolmuun asti.

Vaihe 2) Määritä muuttuja tai osoitin häntäsolmuun.

Vaihe 3) - asettaa seuraava osoitin arvoon NULL ja vapauta häntäsolmun muisti.

Tässä on pseudokoodi häntäsolmun poistamiseen:

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

Solmun etsiminen ja poistaminen kaksinkertaisesti linkitetystä listasta

Tämä operaatio etsii tiettyä solmun arvoa ja poistaa kyseisen solmun. Lineaarinen haku on tarpeen, koska linkitetty lista on lineaarinen tietorakenne. Poiston jälkeen muisti on vapautettava.

Tässä ovat vaiheet solmun etsimiseen ja poistamiseen kaksinkertaisesti linkitetyssä listassa:

Vaihe 1) Käy linkitettyä listaa läpi otsikosta, kunnes solmun arvo on yhtä suuri kuin etsittävä alkio.

Vaihe 2) Määritä muuttuja poistaNode vastaavaan solmuun.

Vaihe 3) Linkitä edellinen solmu poistaNode seuraavaan solmuunsa ja aseta seuraavan solmun prev osoitin edelliseen solmuun.

Vaihe 4) Vapauta muisto siitä, poistaNode.

Tässä on pseudokoodi solmun etsimiseen ja poistamiseen linkitetystä listasta:

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

Etsi ja poista toiminto

Kaksinkertaisesti linkitetyn listan läpikäyminen eteenpäin

Pääsolmusta lähtien iteroidaan seuraavan solmun läpi, kunnes löydetään NULL. Kunkin solmun läpikulun aikana arvo voidaan tulostaa. Tässä ovat vaiheet eteenpäin siirtymiseen:

Vaihe 1) Määritä osoitin tai muuttuja nykyiseen pääsolmuun.

Vaihe 2) Iteroi seuraavaan pääosan solmuun, kunnes saat NULL-arvon.

Vaihe 3) Tulosta solmun tiedot jokaisessa iteraatiossa.

Vaihe 4) Palauta pääsolmu.

Tässä on pseudokoodi kaksinkertaisesti linkitetyn listan läpikäymiseen edestäpäin:

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

Palautus ei ole pakollinen. Pääsolmun palauttaminen toimintojen jälkeen on kuitenkin hyvä käytäntö.

Kaksinkertaisesti linkitetty listan läpikäyminen takaperin

Tämä operaatio on käänteinen edestäpäin tapahtuvalle jonolle. Lähestymistapa on sama yhdellä pienellä erolla: saavuta ensin päätesolmu ja kävele sitten taaksepäin päähän käyttäen prev osoitin.

Tässä ovat vaiheet kaksinkertaisesti linkitetyn listan läpikäymiseksi takaapäin:

Vaihe 1) Liiku, kunnes häntäsolmu on saavutettu.

Vaihe 2) Häntäsolmusta lähtien siirrytään käyttämällä prev kunnes edellinen solmu on NULL. prev osoitin on null pääsolmulle.

Vaihe 3) Tulosta solmun tiedot jokaisella iteraatiolla.

Tässä on pseudokoodi takaapäin kulkemiseen:

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

Ero yksittäin ja kaksinkertaisesti linkitetyn listan välillä

Yksinkertaisesti linkitetyn listan ja kaksinkertaisesti linkitetyn listan tärkein ero on kunkin solmun linkkien lukumäärä.

Tässä on ero yksinkertaisesti linkitetyn listan ja kaksinkertaisesti linkitetyn listan solmujen välillä:

Kaksoislinkitetty luettelo C++

Alla on täydellinen C++ Kaksinkertaisesti linkitetyn listan toteutus lisäys-, poisto-, haku- ja läpikulkuoperaatioilla.

#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);
    return;
  }
  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 = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\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 = (*listHead);
  while(head != 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;
}
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);
}

ulostulo

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
Traversal from head:    7  6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Kaksoislinkitetty luettelo Python

Alla on täydellinen Python Kaksinkertaisesti linkitetyn listan toteutus käyttämällä luokkia solmuille ja itse listalle.

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.head = newNode
      print("Added {} at the end".format(val))
      return
    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 is not None:
      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 != 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 != 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 is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == 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))
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()

ulostulo

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

Kaksinkertaisesti linkitetyn luettelon monimutkaisuus

Aikakompleksisuus jaetaan yleensä kolmeen tyyppiin: paras tapaus, keskimääräinen tapaus ja huonoin tapaus.

Ajan monimutkaisuus parhaassa tapauksessa kaksoislinkitetylle listalle:

1. Lisäys alkuun tai häntään maksaa O(1), koska linkitetyn listan sisällä ei tarvitse kulkea. Alku- ja loppuosoittimista pääsee suoraan alku- ja loppusolmuihin.
2. Poisto alku- tai loppupäässä maksaa O(1).
3. Solmun etsiminen maksaa O(1), kun kohdesolmu on pääsolmu.

Ajan monimutkaisuus kaksinkertaisesti linkitetyn luettelon keskimääräisessä tapauksessa:

1. Lisäys kärkeen tai häntään maksaa O(1).
2. Poisto alku- tai loppupäässä maksaa O(1).
3. Solmun etsiminen maksaa O(n), koska kohde voi sijaita missä tahansa listan kohdassa. Tässä tapauksessa n on solmujen kokonaismäärä.

Kaksinkertaisesti linkitetyn listan pahimman tapauksen aikakompleksisuus on sama kuin keskimääräisen tapauksen.

Kaksinkertaisesti linkitetyn luettelon muistin monimutkaisuus

Muistin monimutkaisuus on O(n), missä n on solmujen kokonaismäärä. Linkitetyn listan toteuttamisen aikana muistia on vapautettava. Muuten suuremmat linkitetyt listat aiheuttavat muistivuotoja.

Kaksinkertaisesti linkitettyjen listojen sovellukset

Kaksinkertaisesti linkitetyt listat tukevat useita reaalimaailman tietorakenteita, koska kaksisuuntainen läpikulku yksinkertaistaa monia yleisiä toimintoja.

• LRU-välimuisti: Vähiten käytetyt välimuistit käyttävät kaksinkertaisesti linkitettyä listaa, jossa on hajautuskartta O(1)-siirtoa eteen ja häätöä varten.
• Selaimen historia: Eteen- ja taaksepäin navigointi selaa linkitettyä listaa kumpaankin suuntaan.
• Kumoa ja tee uudelleen pinot: Editorit ja IDE:t track dokumenttiversiota, joissa on edelliset ja seuraavat osoittimet.
• Deque: Double-päätteiset jonot työntyvät ja poistuvat molemmista päistä ajassa O(1).
• Musiikkisoittolistat: Edellinen ja seuraava track-painikkeet käyttävät eteen- ja taaksepäin osoittavia osoittimia.

UKK