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

doubly linked list java implementation code examples

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Επιλέξτε Το Λειτουργικό Σύστημα Επιλέξτε Ένα Πρόγραμμα Προβολής (Προαιρετικά)

Περιγράψτε Το Πρόβλημά Σας

Αυτό το σεμινάριο εξηγεί τη λίστα διπλά συνδεδεμένων στη Java μαζί με την εφαρμογή διπλής συνδεδεμένης λίστας, κυκλική λίστα διπλού συνδέσμου κώδικα Java και παραδείγματα:

Η συνδεδεμένη λίστα είναι μια διαδοχική αναπαράσταση των στοιχείων. Κάθε στοιχείο της συνδεδεμένης λίστας ονομάζεται «Κόμβος». Ένας τύπος συνδεδεμένης λίστας ονομάζεται 'Singly Linked list'.

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

=> Ελέγξτε ΟΛΑ τα Εκπαιδευτικά Java εδώ.

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

Τι θα μάθετε:

Διπλά συνδεδεμένη λίστα στην Java
Κυκλική διπλά συνδεδεμένη λίστα στην Ιάβα
- Συχνές Ερωτήσεις
συμπέρασμα
- Συνιστώμενη ανάγνωση

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

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

δωρεάν μετατροπείς βίντεο για windows 10

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

Εδώ, «Προηγούμενο» και «Επόμενο» δείχνουν τα προηγούμενα και τα επόμενα στοιχεία του κόμβου αντίστοιχα. Το «Δεδομένα» είναι το πραγματικό στοιχείο που αποθηκεύεται στον κόμβο.

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

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

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

Πλεονεκτήματα

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

Μειονεκτήματα

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

Υλοποίηση σε Java

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

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

Διπλή εφαρμογή λίστας σε Java

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

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

 class DoublyLinkedList { //A node class for doubly linked list class Node{ int item; Node previous; Node next; public Node(int item) { this.item = item; } } //Initially, heade and tail is set to null Node head, tail = null; //add a node to the list public void addNode(int item) { //Create a new node Node newNode = new Node(item); //if list is empty, head and tail points to newNode if(head == null) { head = tail = newNode; //head's previous will be null head.previous = null; //tail's next will be null tail.next = null; } else { //add newNode to the end of list. tail->next set to newNode tail.next = newNode; //newNode->previous set to tail newNode.previous = tail; //newNode becomes new tail tail = newNode; //tail's next point to null tail.next = null; } } //print all the nodes of doubly linked list public void printNodes() { //Node current will point to head Node current = head; if(head == null) { System.out.println('Doubly linked list is empty'); return; } System.out.println('Nodes of doubly linked list: '); while(current != null) { //Print each node and then go to next. System.out.print(current.item + ' '); current = current.next; } } } class Main{ public static void main(String() args) { //create a DoublyLinkedList object DoublyLinkedList dl_List = new DoublyLinkedList(); //Add nodes to the list dl_List.addNode(10); dl_List.addNode(20); dl_List.addNode(30); dl_List.addNode(40); dl_List.addNode(50); //print the nodes of DoublyLinkedList dl_List.printNodes(); } }

Παραγωγή:

Κόμβοι διπλής σύνδεσης:
10 20 30 40 50

Έξοδος - προσθήκη νέων κόμβων

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

Κυκλική διπλά συνδεδεμένη λίστα στην Ιάβα

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

Το παρακάτω διάγραμμα δείχνει την κυκλική διπλά συνδεδεμένη λίστα.

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

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

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

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

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

Μειονεκτήματα:

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

Το παρακάτω πρόγραμμα Java δείχνει την εφαρμογή της λίστας Circular Doublely Linked.

import java.util.*; class Main{ static Node head; // Doubly linked list node definition static class Node{ int data; Node next; Node prev; }; // Function to insert node in the list static void addNode(int value) { // List is empty so create a single node furst if (head == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; head = new_node; return; } // find last node in the list if list is not empty Node last = (head).prev; //previous of head is the last node // create a new node Node new_node = new Node(); new_node.data = value; // next of new_node will point to head since list is circular new_node.next = head; // similarly previous of head will be new_node (head).prev = new_node; // change new_node=>prev to last new_node.prev = last; // Make new node next of old last last.next = new_node; } static void printNodes() { Node temp = head; //traverse in forward direction starting from head to print the list while (temp.next != head) { System.out.printf('%d ', temp.data); temp = temp.next; } System.out.printf('%d ', temp.data); //traverse in backward direction starting from last node System.out.printf('
Circular doubly linked list travesed backward: 
'); Node last = head.prev; temp = last; while (temp.prev != last) { System.out.printf('%d ', temp.data); temp = temp.prev; } System.out.printf('%d ', temp.data); } public static void main(String() args) { //the empty list Node l_list = null; // add nodes to the list addNode(40); addNode(50); addNode(60); addNode(70); addNode(80); //print the list System.out.printf('Circular doubly linked list: '); printNodes(); } }

Παραγωγή:

Κυκλική διπλά συνδεδεμένη λίστα: 40 50 60 70 80
Η κυκλική διπλά συνδεδεμένη λίστα έχει μετατραπεί προς τα πίσω:
80 70 60 50 40

έξοδος - Κυκλική διπλά συνδεδεμένη λίστα

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

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

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

Ε # 1) Μπορεί η λίστα διπλά συνδεδεμένων να είναι κυκλική;

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

Ε # 2) Πώς δημιουργείτε μια λίστα διπλά κυκλικής σύνδεσης;

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

Ε # 3) Είναι γραμμική ή κυκλική η διπλή συνδεδεμένη λίστα;

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

Q # 4) Ποια είναι η διαφορά μεταξύ της λίστας 'Διπλός σύνδεσμος' και της λίστας 'Κυκλική σύνδεση';

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

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

Q # 5) Ποια είναι τα πλεονεκτήματα μιας λίστας διπλής σύνδεσης;

πού μπορώ να παρακολουθήσω δωρεάν anime online

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

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

συμπέρασμα

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

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

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

Με αυτό, τελειώσαμε με τη συνδεδεμένη λίστα στην Java. Μείνετε συντονισμένοι για πολλά περισσότερα σεμινάρια σχετικά με τις τεχνικές αναζήτησης και ταξινόμησης στην Java.

=> Επισκεφτείτε εδώ για την αποκλειστική σειρά εκπαιδευτικών εκμάθησης Java.

Διπλά συνδεδεμένη λίστα στην Java - Παραδείγματα υλοποίησης και κώδικα