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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Για παράδειγμα, υπάρχει ένας δεδομένος κόμβος "15". Πρέπει να το προσθέσουμε στον κόμβο κεφαλής.

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

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

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

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

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

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

Για να το κάνουμε αυτό, μπορούμε να χρησιμοποιήσουμε δύο μεθόδους:

Μέθοδος 1: Ξεκινήστε τη διέλευση από την κορυφή της Λίστας Διπλής Συνδεδεμένης έως ότου το "επόμενο" γίνει μηδενικό. Στη συνέχεια συνδέστε τον νέο κόμβο με τον "επόμενο".
Μέθοδος 2: Πάρτε τον τελευταίο κόμβο της λίστας με διπλή σύνδεση. Στη συνέχεια, ο «επόμενος» κόμβος του τελευταίου κόμβου θα συνδεθεί με τον νέο κόμβο. Τώρα, ο νέος κόμβος θα είναι ο ουραίος κόμβος.

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

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

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

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

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

Θέλουμε να εισαγάγουμε έναν δεδομένο κόμβο που θα συνδεθεί μετά τον κόμβο, ο οποίος έχει την τιμή «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
	then List = ListHead.next
  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
	then List = ListHead.next
  NewNode.next = List.next
  NewNode.prev = List
  List.next = NewNode

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

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

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

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

Βήμα 2) Επισκεφτείτε τον «επόμενο» κόμβο του τρέχοντος κόμβου κεφαλής και κάντε τον κόμβο «προηγούμενο» (προηγούμενος δείκτης) ως «NULL». Αυτό σημαίνει ότι αποσυνδέουμε τον δεύτερο κόμβο από τον πρώτο κόμβο.

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

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

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

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

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

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

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

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

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

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

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

Βήμα 3) Κάντε τον "επόμενο" κόμβο ως NULL και ελευθερώστε τη μνήμη του κόμβου ουράς.

Ακολουθεί ο ψευδοκώδικας για τη διαγραφή του κόμβου της ουράς:

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

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

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

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

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

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

Βήμα 3) Αντιστοιχίστε τον προηγούμενο κόμβο του "deleteNode" στον επόμενο κόμβο.

Βήμα 4) Ελευθερώστε τη μνήμη του "deleteNode"

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

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

Αναζήτηση και Διαγραφή Operaσμού — Λειτουργία αναζήτησης και διαγραφής

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

Για να διασχίσουμε από τον κύριο κόμβο και να επαναλάβουμε τον επόμενο κόμβο μέχρι να βρούμε το "NULL". Καθώς διασχίζουμε κάθε κόμβο, μπορούμε να εκτυπώσουμε την τιμή του κόμβου. Ακολουθούν τα βήματα για τη διέλευση από μπροστά (κατεύθυνση προς τα εμπρός):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ακολουθεί η διαφορά μεταξύ των κόμβων μιας λίστας Singly Linked και της δομής κόμβων της Doubly Linked List:

Πεδίο	Λίστα μεμονωμένα συνδεδεμένα	Διπλή συνδεδεμένη λίστα
Structure	Λίστα μεμονωμένα συνδεδεμένα έχει ένα πεδίο δεδομένων και έναν σύνδεσμο προς τον επόμενο κόμβο.	Η λίστα διπλής σύνδεσης έχει ένα πεδίο δεδομένων και δύο συνδέσμους. Ένα για τον προηγούμενο κόμβο και ένα άλλο για τον επόμενο κόμβο.
Διασχίζοντας	Μπορεί να διασχίσει μόνο από το κεφάλι μέχρι την ουρά.	Μπορεί να διασχίσει τόσο προς τα εμπρός όσο και προς τα πίσω.
Μνήμη	Καταλαμβάνει λιγότερη μνήμη.	Καταλαμβάνει περισσότερη μνήμη από μια λίστα μεμονωμένα συνδεδεμένη.
Προσβασιμότητα	Οι μεμονωμένα συνδεδεμένες λίστες είναι λιγότερο αποτελεσματικές καθώς χρησιμοποιούν μόνο έναν σύνδεσμο προς τον επόμενο κόμβο. Δεν υπάρχει σύνδεσμος για τον προηγούμενο κόμβο.	Οι λίστες με διπλή σύνδεση είναι πιο αποτελεσματικές από τις λίστες μεμονωμένα συνδεδεμένα.

Διπλή συνδεδεμένη λίστα σε 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);
}

Παραγωγή

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

Διπλή συνδεδεμένη λίστα σε 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()

Παραγωγή

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

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

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

Αυτοί είναι:

καλυτερα Case
Μέση περίπτωση
Χειρότερη περίπτωση

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

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

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

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

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

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

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

Σύνοψη

Μια συνδεδεμένη λίστα είναι ένα είδος γραμμικής δομής δεδομένων, μια συλλογή δεδομένων που αναπαρίστανται με γραμμικό τρόπο.
Μια διπλά συνδεδεμένη λίστα είναι ένας τύπος συνδεδεμένης λίστας όπου ένας κόμβος έχει συνδέσμους τόσο με τον προηγούμενο όσο και με τον επόμενο κόμβο.
Η διπλά συνδεδεμένη λίστα περιέχει όλες τις λειτουργίες όπως η προσθήκη ενός κόμβου, η διαγραφή ενός κόμβου, η εισαγωγή ενός κόμβου μετά ή πριν από έναν άλλο κόμβο και η διέλευση της συνδεδεμένης λίστας από το κεφάλι μέχρι το τέλος.
Η λίστα διπλής σύνδεσης έχει ένα πεδίο δεδομένων και δύο συνδέσμους. Ένα για τον προηγούμενο κόμβο και ένα άλλο για τον επόμενο κόμβο.
Πολυπλοκότητα Διπλής Συνδεδεμένης Λίστας Καλύτερα Υπόθεση, Μέση Περίπτωση
Και η χειρότερη περίπτωση.

Μπορεί να σας αρέσει:

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

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

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

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

ΣΧΕΤΙΚΑ ΑΡΘΡΑ

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

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

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

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

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

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

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

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

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

Παραγωγή

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

Παραγωγή

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

Σύνοψη