Kaksoislinkitetty lista: C++, Python (Koodiesimerkki)
Sarah Chen
Mikä on kaksoislinkitetty luettelo?
Kaksoislinkitetyssä luettelossa jokaisella solmulla on linkit sekä edelliseen että seuraavaan solmuun. Jokainen solmu koostuu kolmesta elementistä: yksi sisältää tiedot ja kaksi toiset ovat seuraavan ja edellisen solmun osoittimia. Nämä kaksi osoitinta auttavat meitä siirtymään eteenpäin tai taaksepäin tietystä solmusta.
Tässä on kaksoislinkitetyn luettelon perusrakenne.
Jokaisella linkitetyllä luettelolla on pää- ja häntäsolmu. Pääsolmulla ei ole "edellinen" (edellinen osoitin) solmua, eikä häntäsolmulla ole "seuraavaa" solmua.
Tässä on joitain tärkeitä termejä kaksoislinkitetylle luettelolle:
- 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 tietojen tallentamiseen solmuun. "Data" voi sisältää muuta Tietorakenteet sen sisällä. Esimerkiksi merkkijono, sanakirja, joukko, hashmappi jne. voidaan tallentaa "Dataan".
Tässä on yksittäisen solmun perusrakenne kaksoislinkitetyssä luettelossa:
Operakaksoislinkitettyjen luetteloiden
Kaksinkertaisesti linkitetyn luettelon toimintoihin kuuluvat solmujen lisääminen ja poistaminen, solmujen lisääminen ja poistaminen sekä linkitetyn luettelon läpikulku ylhäältä alas.
Tässä on luettelo toiminnoista, jotka voimme toteuttaa käyttämällä kaksoislinkitettyä luetteloa:
- 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äemme kaikkien yllä olevien toimintojen toteutuksen ja pseudokoodin.
Lisäys kaksoislinkitettyjen luettelon eteen
Eteen lisäys tarkoittaa, että meidän on luotava linkitettyyn luetteloon solmu ja asetettava se linkitetyn luettelon alkuun.
Esimerkiksi siellä on annettu solmu "15". Meidän on lisättävä tämä pääsolmuun.
Tässä on kaksi tärkeää ehtoa tätä toimintoa suoritettaessa:
- Uusi solmu on pääsolmu, jos kaksoislinkitetyssä luettelossa ei ole solmua.
- Jos pääsolmu on jo olemassa, edellinen pää korvataan uudella solmulla.
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 kaksoislinkitettyjen luettelon loppuun
"Lisäys lopussa" tarkoittaa, että luomme solmun linkitettyyn luetteloon ja sijoitamme sen loppuun.
Tämän suorittamiseksi voimme käyttää kahta tapaa:
- Menetelmä 1: Aloita liikkuminen kaksoislinkitetyn luettelon päästä, kunnes "seuraava" muuttuu tyhjäksi. Yhdistä sitten uusi solmu "seuraavaan".
- Menetelmä 2: Ota kaksinkertaisesti linkitettyjen luettelon viimeinen solmu. Sitten viimeisen solmun "seuraava" solmu linkittyy uuteen solmuun. Nyt uusi solmu on häntäsolmu.
Tässä on pseudokoodi häntäsolmuun lisäämistä varten:
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
Lisäys solmun jälkeen
Oletetaan, että meillä on olemassa oleva kaksoislinkitetty luettelo, kuten seuraava:
Haluamme lisätä tietyn solmun, joka linkitetään solmun jälkeen, jonka arvo on "12".
Tässä on tämän vaiheet:
Vaihe 1) Kulje päästä viimeiseen solmuun. Tarkista, minkä solmun arvo on "12".
Vaihe 2) Luo uusi solmu ja määritä se solmun "12" seuraavaksi osoittimeksi. Uuden solmun "seuraava" solmu on 15.
Tässä on pseudokoodi solmun lisäämiseksi solmun perään kaksoislinkitetyssä luettelossa:
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
Lisäys ennen solmua
Tämä toiminto on enemmän samanlainen kuin "lisäys solmun jälkeen". Meidän on etsittävä tietyn solmun arvoa suorittaaksemme tämän. Sitten luomme uuden solmun ja lisäämme sen ennen haettua solmua.
Oletetaan, että haluamme lisätä tietyn solmun "15" ennen solmua "12". Sitten tässä on vaiheet sen tekemiseen:
Vaihe 1) Kulje linkitetty luettelo pääsolmusta loppusolmuun.
Vaihe 2) Tarkista, onko nykyisen solmun seuraavan osoittimen arvo "12" vai ei.
Vaihe 3) Lisää uusi solmu nykyisen solmun "seuraavaksi" solmuksi.
Tässä on pseudokoodi solmun lisäämiseksi ennen solmua kaksoislinkitetyssä luettelossa:
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
Poista kaksoislinkitetyn luettelon pää
Pääsolmu kaksoislinkitetyssä luettelossa, jolla ei ole aiempaa solmua. Joten seuraava osoitin on uusi pääsolmu, jos haluamme poistaa pääsolmun. Meidän on myös vapautettava solmun varaama muisti solmun poistamisen aikana.
Tässä on vaiheet pääsolmun poistamiseksi:
Vaihe 1) Määritä muuttuja nykyiseen pääsolmuun.
Vaihe 2) Vieraile nykyisen pääsolmun "seuraavassa" solmussa ja tee "edellinen" (edellinen osoitin) -solmuksi "NULL". Tämä tarkoittaa, että irrotamme toisen solmun ensimmäisestä solmusta.
Vaihe 3) Vapauta edellisen pääsolmun varaama muisti.
Tässä on pseudokoodi pään poistamiseksi kaksoislinkitetystä luettelosta:
function deleteHead(ListHead): PrevHead = ListHead ListHead = ListHead.next ListHead.prev = NULL PrevHead.next = NULL free memory(PrevHead) return ListHead
On tarpeen poistaa varattu muisti minkä tahansa poistotoimenpiteen suorittamisen jälkeen. Muussa tapauksessa poistetun lohkon muisti pysyy varattuna koko ohjelman ajon ajan. Mikään muu sovellus ei voi käyttää tätä muistisegmenttiä.
Poista kaksoislinkitetyn luettelon loppuosa.
Tämä toimenpide on tavallaan sama kuin pään poistaminen. Täällä pään sijasta meidän on poistettava häntä. Tunnistellaksemme solmun häntäsolmuksi, meidän tulee tarkistaa, onko seuraava osoitin tai seuraava solmu tyhjä vai ei. Hännän poistamisen jälkeen meidän on vapautettava muisti.
Tätä toimintoa kutsutaan myös "poistoksi takaa".
Tässä on ohjeet tämän tekemiseen:
Vaihe 1) Kulje kaksinkertaisesti linkitetyn luettelon loppusolmuun asti.
Vaihe 2) Määritä muuttuja tai osoitin häntäsolmuun.
Vaihe 3) Tee "seuraava" solmu NULL:ksi ja vapauta loppusolmun 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.next ListHead.next = NULL free memory( Tail ) return head
Etsi ja poista solmu kaksoislinkitetystä luettelosta
Tämän toiminnon avulla voimme etsiä tietyn solmun tiedot ja poistaa kyseisen solmun. Meidän on suoritettava lineaarinen haku, koska linkitetty luettelo on lineaarinen tietorakenne. Poistamisen jälkeen meidän on myös vapautettava muisti.
Seuraavassa on vaiheet solmun etsimiseen ja poistamiseen kaksoislinkitetystä luettelosta:
Vaihe 1) Kulje linkitettyä luetteloa päästä, kunnes solmun arvo on yhtä suuri kuin hakukohde.
Vaihe 2) Määritä muuttuja "deleteNode" vastaavalle solmulle.
Vaihe 3) Määritä "deleteNoden" edellinen solmu seuraavaan solmuun.
Vaihe 4) Vapauta "deleteNoden" muisti
Tässä on pseudokoodi solmun etsimiseen ja poistamiseen linkitetystä luettelosta:
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
Selaa kaksoislinkitetty luettelo eteenpäin
Siirtääksesi pääsolmusta ja iteroidaksesi seuraavan solmun yli, kunnes löydämme "NULL". Kun kuljemme jokaisen solmun läpi, voimme tulostaa solmun arvon. Tässä ovat vaiheet ajamiseen edestä (eteenpäin):
Vaihe 1) Määritä osoitin tai muuttuja nykyiseen pääsolmuun.
Vaihe 2) Iteroi pään seuraavaan solmuun, kunnes saat "NULL"
Vaihe 3) Tulosta solmun tiedot jokaisessa iteraatiossa.
Vaihe 4) Palauta pääsolmu.
Tässä on pseudokoodi kaksoislinkitetyn luettelon läpikulkuun edestä:
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
Täällä palautus ei ole pakollista. Mutta on hyvä käytäntö palauttaa pääsolmu toimintojen jälkeen.
Selaa kaksoislinkitetty luettelo taaksepäin
Tämä operaatio on käänteinen liikeradalle edestä. Lähestymistapa on sama pienellä erolla. Meidän täytyy kulkea loppusolmuun ja sitten kulkea loppusolmusta etusolmuun.
Tässä on vaiheet kaksoislinkitetyn luettelon läpikulkuun takaapäin:
Vaihe 1) Kulje, kunnes saavutamme häntäsolmun.
Vaihe 2) Häntäsolmusta kuljemme, kunnes saamme edellisen solmun muodossa "NULL". "edellinen" (edellinen osoitin) on tyhjä pääsolmun kohdalla
Vaihe 3) Jokaisessa iteraatiossa tulostamme solmutiedot.
Tässä on pseudokoodi takaa kulkemiseen:
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
Ero yksittäis- ja kaksinkertaisesti linkitetyn luettelon välillä
Suurin ero yksittäisten ja kaksoislinkitettyjen luetteloiden välillä on linkkien määrä.
Tässä on ero yksitellen linkitetyn luettelon solmujen ja kaksoislinkitetyn luettelon solmurakenteen välillä:
| Kenttä | Yksittäin linkitetty luettelo | Kaksoislinkitetty lista |
|---|---|---|
| Tuote mallit | Yksittäin linkitetty luettelo on yksi tietokenttä ja yksi linkki seuraavaan solmuun. | Kaksinkertaisesti linkitetyssä luettelossa on yksi tietokenttä ja kaksi linkkiä. Yksi edelliselle solmulle ja toinen seuraavalle solmulle. |
| traversal | Se voi kulkea vain päästä häntään. | Se voi kulkea sekä eteen- että taaksepäin. |
| Muisti | Vie vähemmän muistia. | Se vie enemmän muistia kuin yksittäin linkitetty luettelo. |
| Käytettävyys: | Yksittäin linkitetyt luettelot ovat vähemmän tehokkaita, koska ne käyttävät vain yhtä linkkiä seuraavaan solmuun. Edelliseen solmuun ei ole linkkiä. | Kaksinkertaisesti linkitetyt luettelot ovat tehokkaampia kuin yksittäiset linkitetyt luettelot. |
Kaksoislinkitetty luettelo 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);
}
ulostulo
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
Kaksoislinkitetty luettelo 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()
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
Yleensä aika monimutkaisuus jaetaan kolmeen tyyppiin.
Ne ovat:
- Paras tapaus
- Keskimääräinen kotelo
- Pahimmassa tapauksessa
Ajan monimutkaisuus parhaassa tapauksessa kaksoislinkitetylle listalle:
- Asennus päähän tai häntään maksaa O(1). Koska meidän ei tarvitse kulkea linkitetyn luettelon sisällä. Pää- ja hännänosoitin voivat antaa meille pääsyn pää- ja hännänsolmuun O(1)-aikakompleksisuudella.
- Pään tai hännän poistaminen maksaa O(1).
- Solmun haun aikamonimutkaisuus on O(1). Koska kohdesolmu voi olla pääsolmu.
Ajan monimutkaisuus kaksinkertaisesti linkitetyn luettelon keskimääräisessä tapauksessa:
- Päähän tai hännän kohdalle asettamisella on kustannusten O(1) aikamonimutkaisuus.
- Poistolla pään tai hännän kohdalta on kustannusten O(1) aikamonimutkaisuus.
- Solmun haun aikamonimutkaisuus on O(n). Koska hakukohde voi sijaita missä tahansa linkitetyn luettelon välissä. Tässä "n" on linkitetyssä luettelossa oleva kokonaissolmu.
Kaksinkertaisesti linkitetyn luettelon pahimman tapauksen aika monimutkaisuus on sama kuin keskimääräinen tapaus.
Kaksinkertaisesti linkitetyn luettelon muistin monimutkaisuus
Muistin monimutkaisuus on O(n), jossa "n" on solmujen kokonaismäärä. Kun toteutamme linkitettyä luetteloa, meidän on vapautettava käyttämämme muisti. Muussa tapauksessa suurempi linkitetty luettelo aiheuttaa muistivuotoja.
Yhteenveto
- Linkitetty lista on eräänlainen lineaarinen tietorakenne, lineaarisesti esitetty kokoelma dataa.
- Kaksoislinkitetty luettelo on linkitetty luettelo, jossa solmulla on linkkejä sekä edelliseen että seuraavaan solmuun.
- Kaksinkertaisesti linkitetty luettelo sisältää kaikki toiminnot, kuten solmun lisäämisen, solmun poistamisen, solmun lisäämisen toisen solmun jälkeen tai ennen ja linkitetyn luettelon läpikulkua päästä hätään.
- Kaksinkertaisesti linkitetyssä luettelossa on yksi tietokenttä ja kaksi linkkiä. Yksi edelliselle solmulle ja toinen seuraavalle solmulle.
- Kaksinkertaisesti linkitetyn luettelon monimutkaisuus paras tapaus, keskimääräinen tapaus
- Ja pahimmassa tapauksessa.
