Λίστα με διπλή σύνδεση: C++, Python (Code Παράδειγμα)

Τι είναι μια διπλά συνδεδεμένη λίστα;

Σε μια διπλά συνδεδεμένη λίστα, κάθε κόμβος έχει συνδέσμους τόσο προς τον προηγούμενο όσο και προς τον επόμενο κόμβο. Κάθε κόμβος αποτελείται από τρία στοιχεία: το ένα περιέχει τα δεδομένα και τα άλλα δύο είναι δείκτες προς τον επόμενο και τον προηγούμενο κόμβο. Αυτοί οι δύο δείκτες βοηθούν στην μετακίνηση προς τα εμπρός ή προς τα πίσω από έναν συγκεκριμένο κόμβο.

Εδώ είναι η βασική δομή της διπλά συνδεδεμένης λίστας.

Δομή μιας διπλά συνδεδεμένης λίστας

Κάθε συνδεδεμένη λίστα έχει έναν κόμβο κεφαλής και έναν κόμβο ουράς. Ο κόμβος κεφαλής δεν έχει prev (προηγούμενος δείκτης) κόμβος, και ο κόμβος ουράς δεν έχει επόμενη κόμβος.

Ακολουθούν ορισμένοι σημαντικοί όροι για μια διπλά συνδεδεμένη λίστα:

• Προηγούμενο: Κάθε κόμβος συνδέεται με τον προηγούμενο κόμβο του. Χρησιμοποιείται ως δείκτης ή σύνδεσμος.
• επόμενο: Κάθε κόμβος συνδέεται με τον επόμενο κόμβο του. Χρησιμοποιείται ως δείκτης ή σύνδεσμος.
• Δεδομένα: Αυτό χρησιμοποιείται για την αποθήκευση δεδομένων σε έναν κόμβο. Τα δεδομένα μπορούν να περιέχουν και άλλα Δομές δεδομένων μέσα σε αυτό. Για παράδειγμα, συμβολοσειρά, λεξικό, σύνολο, χάρτης κατακερματισμού και άλλες δομές μπορούν να αποθηκευτούν στο πεδίο δεδομένων.

Ακολουθεί η βασική δομή ενός μεμονωμένου κόμβου στη διπλά συνδεδεμένη λίστα:

Δομή ενός κόμβου σε μια διπλά συνδεδεμένη λίστα

Operaθέσεις της Διπλής Συνδεδεμένης Λίστας

Οι λειτουργίες μιας διπλά συνδεδεμένης λίστας περιλαμβάνουν την προσθήκη, τη διαγραφή, την εισαγωγή και την αφαίρεση κόμβων, καθώς και τη μετακίνηση της λίστας από πάνω προς τα κάτω ή από κάτω προς τα πάνω.

Ακολουθεί η λίστα με τις λειτουργίες που μπορούν να υλοποιηθούν σε μια διπλά συνδεδεμένη λίστα:

• Εισαγωγή μπροστά
• Εισαγωγή στην ουρά ή στον τελευταίο κόμβο
• Εισαγωγή μετά από κόμβο
• Εισαγωγή πριν από έναν κόμβο
• Διαγραφή από μπροστά
• Διαγραφή από την ουρά
• Αναζήτηση και διαγραφή ενός κόμβου
• Τραβέρσα από το κεφάλι στην ουρά
• Τραβέρσα από την ουρά με το κεφάλι

Η υλοποίηση και ο ψευδοκώδικας για καθεμία από αυτές τις λειτουργίες ακολουθούν παρακάτω.

Εισαγωγή μπροστά από διπλά συνδεδεμένη λίστα

Η εισαγωγή μπροστά σημαίνει τη δημιουργία ενός κόμβου στη συνδεδεμένη λίστα και την τοποθέτησή του στην αρχή της λίστας.

Για παράδειγμα, υπάρχει ένας δεδομένος κόμβος 15Πρέπει να προστεθεί ως ο κύριος κόμβος.

Δύο σημαντικές προϋποθέσεις ισχύουν κατά την εκτέλεση αυτής της λειτουργίας:

1. Ο νέος κόμβος γίνεται ο κύριος κόμβος εάν η διπλά συνδεδεμένη λίστα είναι κενή.
2. Εάν υπάρχει ήδη ένας κόμβος κεφαλής, η προηγούμενη κεφαλή αντικαθίσταται από τον νέο κόμβο.

Εδώ είναι ο ψευδοκώδικας για αυτήν την λειτουργία:

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

Εισαγωγή στον μπροστινό κόμβο

Εισαγωγή στο τέλος διπλά συνδεδεμένης λίστας

Η εισαγωγή στο τέλος σημαίνει δημιουργία ενός κόμβου στη συνδεδεμένη λίστα και τοποθέτησή του στην ουρά.

Δύο μέθοδοι εκτελούν αυτήν την ενέργεια:

• Μέθοδος 1: Ξεκινήστε να μετακινείστε από την αρχή της διπλά συνδεδεμένης λίστας μέχρι επόμενη γίνεται null. Στη συνέχεια, συνδέστε τον νέο κόμβο με το επόμενη δείκτης.
• Μέθοδος 2: Πάρτε τον τελευταίο κόμβο της διπλά συνδεδεμένης λίστας. Στη συνέχεια, το επόμενη Ο δείκτης του τελευταίου κόμβου δείχνει στον νέο κόμβο. Ο νέος κόμβος γίνεται ο ουραίος κόμβος.

Εδώ είναι ο ψευδοκώδικας για την εισαγωγή στον κόμβο ουράς:

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

Εισαγωγή στο τέλος της συνδεδεμένης λίστας

Εισαγωγή μετά από έναν κόμβο

Σκεφτείτε μια υπάρχουσα διπλά συνδεδεμένη λίστα όπως η ακόλουθη:

Ο στόχος είναι να εισαχθεί ένας δεδομένος κόμβος που θα συνδεθεί μετά τον κόμβο με την τιμή 12.

Βήμα 1) Διασχίστε από την κεφαλή στον τελευταίο κόμβο. Ελέγξτε ποιος κόμβος έχει την τιμή 12.

Βήμα 2) Δημιουργήστε έναν νέο κόμβο και ορίστε τον ως τον επόμενο δείκτη του κόμβου 12. ο επόμενη Ο κόμβος του νέου κόμβου θα είναι 15.

Εδώ είναι ο ψευδοκώδικας για την εισαγωγή ενός κόμβου μετά από έναν κόμβο σε μια διπλά συνδεδεμένη λίστα:

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

Εισαγωγή μετά από κόμβο

Εισαγωγή πριν από έναν κόμβο

Αυτή η λειτουργία είναι παρόμοια με την εισαγωγή μετά από έναν κόμβο. Αναζητείται μια συγκεκριμένη τιμή κόμβου και, στη συνέχεια, δημιουργείται ένας νέος κόμβος και εισάγεται πριν από τον αναζητούμενο κόμβο.

Για να εισαγάγετε έναν δεδομένο κόμβο 15 πριν από τον κόμβο 12, Ακολουθήστε αυτά τα βήματα:

Βήμα 1) Διασχίστε τη συνδεδεμένη λίστα από τον κόμβο κεφαλής στον κόμβο ουράς.

Βήμα 2) Ελέγξτε εάν ο επόμενος δείκτης του τρέχοντος κόμβου έχει την τιμή 12.

Βήμα 3) Εισαγάγετε τον νέο κόμβο ως επόμενη κόμβος του τρέχοντος κόμβου.

Εδώ είναι ο ψευδοκώδικας για την εισαγωγή ενός κόμβου πριν από έναν κόμβο σε μια διπλά συνδεδεμένη λίστα:

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

Εισαγωγή κόμβου πριν από κόμβο

Διαγραφή της κεφαλής της διπλά συνδεδεμένης λίστας

Ο κύριος κόμβος στη διπλά συνδεδεμένη λίστα δεν έχει προηγούμενο κόμβο. Έτσι, ο επόμενη Ο δείκτης γίνεται ο νέος κόμβος κεφαλής όταν αφαιρεθεί η τρέχουσα κεφαλή. Απαιτείται επίσης η απελευθέρωση της μνήμης που καταλαμβάνεται από έναν διαγραμμένο κόμβο.

Ακολουθούν τα βήματα για τη διαγραφή του κόμβου κεφαλής:

Βήμα 1) Αντιστοιχίστε μια μεταβλητή στον τρέχοντα κόμβο κεφαλής.

Βήμα 2) επισκεφτείτε το επόμενη κόμβος του τρέχοντος κύριου κόμβου και κάντε το prev δείκτης NULL. Αυτό αποσυνδέει τον δεύτερο κόμβο από τον πρώτο κόμβο.

Βήμα 3) Απελευθερώστε τη μνήμη που καταλαμβάνεται από τον προηγούμενο κόμβο κεφαλής.

Εδώ είναι ο ψευδοκώδικας για τη διαγραφή της κεφαλίδας από μια διπλά συνδεδεμένη λίστα:

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

Διαγραφή του κόμβου κεφαλής

Απαιτείται η απελευθέρωση της εκχωρημένης μνήμης μετά από οποιαδήποτε διαγραφή. Διαφορετικά, η μνήμη για το διαγραμμένο μπλοκ παραμένει κατειλημμένη για ολόκληρο τον χρόνο εκτέλεσης του προγράμματος και καμία άλλη εφαρμογή δεν μπορεί να χρησιμοποιήσει αυτό το τμήμα μνήμης.

Διαγραφή της ουράς της διπλά συνδεδεμένης λίστας

Αυτή η λειτουργία είναι παρόμοια με τη διαγραφή της κεφαλής. Αντί για την κεφαλή, αφαιρείται η ουρά. Για να αναγνωρίσετε έναν κόμβο ως την ουρά, ελέγξτε αν ο επόμενος δείκτης είναι null. Μετά τη διαγραφή της ουράς, η μνήμη πρέπει να ελευθερωθεί.

Αυτή η λειτουργία είναι επίσης γνωστή ως διαγραφή από πίσω.

Εδώ είναι τα βήματα για να το κάνετε αυτό:

Βήμα 1) Διασχίστε μέχρι τον κόμβο-ουρά της διπλά συνδεδεμένης λίστας.

Βήμα 2) Αντιστοιχίστε μια μεταβλητή ή δείκτη στον ουραίο κόμβο.

Βήμα 3) Ρυθμίστε το επόμενη δείκτη σε NULL και ελευθερώστε τη μνήμη του ουραίου κόμβου.

Εδώ είναι ο ψευδοκώδικας για τη διαγραφή του κόμβου tail:

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

Αναζήτηση και διαγραφή κόμβου από τη διπλά συνδεδεμένη λίστα

Αυτή η λειτουργία αναζητά μια συγκεκριμένη τιμή κόμβου και διαγράφει αυτόν τον κόμβο. Απαιτείται γραμμική αναζήτηση επειδή η συνδεδεμένη λίστα είναι μια γραμμική δομή δεδομένων. Μετά τη διαγραφή, η μνήμη πρέπει να ελευθερωθεί.

Ακολουθούν τα βήματα για την αναζήτηση και τη διαγραφή ενός κόμβου στη διπλά συνδεδεμένη λίστα:

Βήμα 1) Διασχίστε τη συνδεδεμένη λίστα από την κεφαλή μέχρι η τιμή του κόμβου να ισούται με το στοιχείο αναζήτησης.

Βήμα 2) Αντιστοίχιση μεταβλητής διαγραφήΚόμβου στον αντιστοιχισμένο κόμβο.

Βήμα 3) Συνδέστε τον προηγούμενο κόμβο του διαγραφήΚόμβου στον επόμενο κόμβο του και ορίστε τον κόμβο του επόμενου κόμβου prev δείκτη στον προηγούμενο κόμβο.

Βήμα 4) Απελευθερώστε τη μνήμη του διαγραφήΚόμβου.

Εδώ είναι ο ψευδοκώδικας για την αναζήτηση και τη διαγραφή ενός κόμβου από μια συνδεδεμένη λίστα:

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

Λειτουργία αναζήτησης και διαγραφής

Διασχίστε μια διπλά συνδεδεμένη λίστα από εμπρός

Η μετάβαση από τον κύριο κόμβο επαναλαμβάνεται στον επόμενο κόμβο μέχρι να βρεθεί η τιμή NULL. Κατά τη μετάβαση σε κάθε κόμβο, η τιμή μπορεί να εκτυπωθεί. Ακολουθούν τα βήματα για τη μετάβαση προς τα εμπρός:

Βήμα 1) Αντιστοιχίστε έναν δείκτη ή μια μεταβλητή στον τρέχοντα κόμβο κεφαλής.

Βήμα 2) Επαναλάβετε στον επόμενο κόμβο της κεφαλής μέχρι να λάβετε NULL.

Βήμα 3) Εκτυπώστε τα δεδομένα κόμβου σε κάθε επανάληψη.

Βήμα 4) Επιστρέψτε τον κόμβο κεφαλής.

Εδώ είναι ο ψευδοκώδικας για τη διέλευση από μια διπλά συνδεδεμένη λίστα από μπροστά:

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

Η επιστροφή δεν είναι υποχρεωτική. Ωστόσο, η επιστροφή του κύριου κόμβου μετά από λειτουργίες είναι καλή πρακτική.

Διασχίστε μια διπλά συνδεδεμένη λίστα από πίσω

Αυτή η λειτουργία είναι το αντίστροφο της όδευσης από μπροστά. Η προσέγγιση είναι η ίδια με μια μικρή διαφορά: φτάστε πρώτα στον τελικό κόμβο και, στη συνέχεια, περπατήστε προς τα πίσω στην κορυφή χρησιμοποιώντας το prev δείκτης.

Ακολουθούν τα βήματα για τη διέλευση από μια διπλά συνδεδεμένη λίστα από το πίσω μέρος:

Βήμα 1) Διασχίστε μέχρι να φτάσετε στον κόμβο της ουράς.

Βήμα 2) Από τον κόμβο ουράς, διασχίστε χρησιμοποιώντας prev μέχρι ο προηγούμενος κόμβος να γίνει NULL. prev Ο δείκτης είναι null για τον κύριο κόμβο.

Βήμα 3) Σε κάθε επανάληψη, εκτυπώστε τα δεδομένα του κόμβου.

Εδώ είναι ο ψευδοκώδικας για την μετάβαση από πίσω:

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

Διαφορά μεταξύ απλής και διπλά συνδεδεμένης λίστας

Η κύρια διαφορά μεταξύ μιας λίστας με μία μόνο σύνδεση και μιας λίστας με δύο συνδέσμους είναι ο αριθμός των συνδέσμων που περιέχει κάθε κόμβος.

Εδώ είναι η διαφορά μεταξύ των κόμβων μιας Μονά Συνδεδεμένης Λίστας και μιας Διπλά Συνδεδεμένης Λίστας:

Διπλή συνδεδεμένη λίστα σε C++

Παρακάτω είναι ένα πλήρες 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);
    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);
}

Παραγωγή

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

Διπλή συνδεδεμένη λίστα σε Python

Παρακάτω είναι ένα πλήρες 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.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()

Παραγωγή

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

Πολυπλοκότητα της λίστας διπλής σύνδεσης

Η χρονική πολυπλοκότητα γενικά χωρίζεται σε τρεις τύπους: την καλύτερη περίπτωση, τη μέση περίπτωση και τη χειρότερη περίπτωση.

Χρονική πολυπλοκότητα στην καλύτερη περίπτωση για τη λίστα διπλής σύνδεσης:

1. Η εισαγωγή στην κεφαλή ή την ουρά κοστίζει O(1) επειδή δεν απαιτείται διέλευση μέσα στη συνδεδεμένη λίστα. Οι δείκτες κεφαλής και ουράς παρέχουν άμεση πρόσβαση στους κόμβους κεφαλής και ουράς.
2. Η διαγραφή στην αρχή ή την ουρά κοστίζει O(1).
3. Η αναζήτηση σε έναν κόμβο κοστίζει O(1) όταν ο κόμβος-στόχος είναι ο κύριος κόμβος.

Χρονική πολυπλοκότητα στη μέση περίπτωση για τη λίστα διπλής σύνδεσης:

1. Η εισαγωγή στην αρχή ή την ουρά κοστίζει O(1).
2. Η διαγραφή στην αρχή ή την ουρά κοστίζει O(1).
3. Η αναζήτηση σε έναν κόμβο κοστίζει O(n), επειδή ο στόχος μπορεί να βρίσκεται οπουδήποτε στη λίστα. Εδώ, n είναι ο συνολικός αριθμός κόμβων.

Η χειρότερη χρονική πολυπλοκότητα της Διπλά Συνδεδεμένης Λίστας είναι η ίδια με τη μέση περίπτωση.

Πολυπλοκότητα μνήμης της λίστας διπλής σύνδεσης

Η πολυπλοκότητα μνήμης είναι O(n), όπου n είναι ο συνολικός αριθμός κόμβων. Κατά την υλοποίηση της συνδεδεμένης λίστας, η μνήμη πρέπει να ελευθερωθεί. Διαφορετικά, μεγαλύτερες συνδεδεμένες λίστες προκαλούν διαρροές μνήμης.

Εφαρμογές διπλά συνδεδεμένης λίστας

Οι διπλά συνδεδεμένες λίστες τροφοδοτούν αρκετές δομές δεδομένων του πραγματικού κόσμου, επειδή η αμφίδρομη διέλευση απλοποιεί πολλές συνηθισμένες λειτουργίες.

• Μνήμη cache LRU: Οι λιγότερο πρόσφατα χρησιμοποιημένες προσωρινές μνήμες χρησιμοποιούν μια διπλά συνδεδεμένη λίστα με έναν χάρτη κατακερματισμού για μετακίνηση προς τα εμπρός και απομάκρυνση O(1).
• Ιστορικό προγράμματος περιήγησης: Η πλοήγηση προς τα πίσω και προς τα εμπρός οδηγεί τη συνδεδεμένη λίστα προς οποιαδήποτε κατεύθυνση.
• Αναίρεση και επανάληψη στοίβων: Επεξεργαστές και IDE track εκδόσεις εγγράφων με δείκτες προηγούμενου και επόμενου.
• Ντεκέ: DoubleΟι ουρές με τερματισμό (-ended) ωθούν και εμφανίζονται και από τα δύο άκρα σε χρόνο O(1).
• Λίστες αναπαραγωγής μουσικής: Προηγούμενο και επόμενο tracΤα κουμπιά k βασίζονται σε δείκτες προς τα πίσω και προς τα εμπρός.

Συχνές Ερωτήσεις