Προγραμματισμός

Δομές δεδομένων και αλγόριθμοι στην Java, Μέρος 5: Λίστες διπλής σύνδεσης

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

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

Διπλά συνδεδεμένες λίστες

ΕΝΑ διπλή συνδεδεμένη λίστα είναι μια συνδεδεμένη λίστα κόμβων όπου κάθε κόμβος έχει ένα ζεύγος πεδίων συνδέσμων. Το πεδίο ενός συνδέσμου σάς επιτρέπει να διασχίζετε τη λίστα προς τα εμπρός, ενώ ο άλλος κόμβος σάς επιτρέπει να διασχίζετε τη λίστα προς τα πίσω. Για την κατεύθυνση προς τα εμπρός, μια μεταβλητή αναφοράς περιέχει μια αναφορά στον πρώτο κόμβο. Κάθε κόμβος συνδέεται με τον επόμενο κόμβο μέσω του πεδίου συνδέσμου "επόμενο", εκτός από τον τελευταίο κόμβο, του οποίου το πεδίο σύνδεσης "επόμενο" περιέχει την μηδενική αναφορά για να δηλώσει το τέλος της λίστας (προς τα εμπρός). Η κατεύθυνση προς τα πίσω λειτουργεί παρόμοια. Μια μεταβλητή αναφοράς περιέχει μια αναφορά στον τελευταίο κόμβο της μπροστινής κατεύθυνσης, την οποία ερμηνεύετε ως τον πρώτο κόμβο. Κάθε κόμβος συνδέεται με τον προηγούμενο κόμβο μέσω του πεδίου συνδέσμου "προηγούμενος". Το πεδίο "προηγούμενος" συνδέσμου του πρώτου κόμβου περιέχει null για να δηλώσει το τέλος της λίστας.

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

Λειτουργίες CRUD σε λίστες διπλής σύνδεσης

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

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward = ΝΕΟ .name = "C" // Δημιουργία λίστας προς τα εμπρός μεμονωμένη σύνδεση topForward.next = temp temp.next = topBackward topBackward.next = NULL // Δημιουργία λίστας μεμονωμένων συνδέσεων προς τα πίσω = NULL // Διαγραφή κόμβου B. temp.prev.next = temp.next; // Παράκαμψη Κόμβος Β στη λίστα μεμονωμένων συνδέσεων προς τα εμπρός. temp.next.prev = temp.prev; // Παράκαμψη Κόμβος Β στην πίσω μεμονωμένη λίστα. ΤΕΛΟΣ 

Παράδειγμα εφαρμογής: CRUD σε μια λίστα διπλής σύνδεσης

Το παράδειγμα εφαρμογής Java DLLDemo δείχνει τον τρόπο δημιουργίας, εισαγωγής και διαγραφής κόμβων σε μια λίστα διπλής σύνδεσης. Ο πηγαίος κώδικας της εφαρμογής εμφανίζεται στη Λίστα 1.

Λίστα 1. Μια εφαρμογή Java που δείχνει CRUD σε μια λίστα διπλής σύνδεσης

 δημόσια τελική κλάση DLLDemo {ιδιωτική στατική κλάση Κόμβος {Όνομα συμβολοσειράς; Επόμενος κόμβος Κόμβος prev; } public static void main (String [] args) {// Δημιουργήστε μια λίστα διπλής σύνδεσης. Κόμβος topForward = νέος κόμβος (); topForward.name = "A"; Κόμβος temp = νέος κόμβος (); temp.name = "B"; Κόμβος topBackward = νέος κόμβος (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Απορρίψτε τη λίστα με έναν μόνο σύνδεσμο. System.out.print ("Προώθηση μεμονωμένης σύνδεσης:"); temp = topForward; ενώ (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Απορρίψτε τη λίστα μεμονωμένα συνδεδεμένα. System.out.print ("Λίστα προς τα πίσω μεμονωμένη σύνδεση:"); temp = topBackward; ενώ (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Κόμβος αναφοράς B. temp = topForward.next; // Διαγραφή κόμβου B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Απορρίψτε τη λίστα με έναν μόνο σύνδεσμο. System.out.print ("Προώθηση μιας μεμονωμένης λίστας (μετά τη διαγραφή):"); temp = topForward; ενώ (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Απορρίψτε τη λίστα μεμονωμένα συνδεδεμένα. System.out.print ("Λίστα μεμονωμένων συνδέσμων προς τα πίσω (μετά τη διαγραφή):"); temp = topBackward; ενώ (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); }} 

Συγκεντρώστε την καταχώριση 4 ως εξής:

 javac DLLDemo.java 

Εκτελέστε την εφαρμογή που προκύπτει ως εξής:

 java DLLDemo 

Πρέπει να παρατηρήσετε την ακόλουθη έξοδο:

 Προώθηση λίστας μεμονωμένων συνδέσμων: Λίστα μεμονωμένων συνδέσεων ABC προς τα πίσω: CBA Προώθηση λίστας μεμονωμένων συνδέσμων (μετά τη διαγραφή): Λίστα μεμονωμένων συνδέσμων AC Backward (μετά τη διαγραφή): CA 

Ανακάτεμα σε διπλά συνδεδεμένες λίστες

Το Java Συλλογές Πλαίσιο περιλαμβάνει ένα Συλλογές κατηγορία μεθόδων χρησιμότητας, η οποία αποτελεί μέρος του java.util πακέτο. Αυτή η τάξη περιλαμβάνει ένα void shuffle (Λίστα λιστών) μέθοδος που "διαπερνά τυχαία την καθορισμένη λίστα χρησιμοποιώντας μια προεπιλεγμένη πηγή τυχαιότηταςΓια παράδειγμα, μπορείτε να χρησιμοποιήσετε αυτήν τη μέθοδο για να ανακατέψετε μια τράπουλα καρτών που εκφράζεται ως λίστα διπλής σύνδεσης (η java.util.LinkedList η τάξη είναι ένα παράδειγμα). Στον ψευδοκώδικα παρακάτω, μπορείτε να δείτε πώς το Αλγόριθμος ανακατέματος μπορεί να ανακατέψει μια διπλά συνδεδεμένη λίστα:

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap (topForward, i - 1, rnd.nextInt (i)) ΤΕΛΟΣ ΛΕΙΤΟΥΡΓΙΑΣ swap (Node top, int i, int j) DECLARE Κόμβος κόμβος, nodej DECLARE INTEGER k // Εντοπίστε τον κόμβο. Κόμβος nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Εντοπισμός jth κόμβου. Κόμβος nodej = κορυφή FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Εκτελέστε την ανταλλαγή. ΔΗΛΩΣΗ STRING namei = nodei.name ΔΗΛΩΣΗ STRING namej = nodej.name nodej.name = namei nodei.name = namej ΤΕΛΟΣ ΛΕΙΤΟΥΡΓΙΑ ΛΕΙΤΟΥΡΓΙΑΣ 

Ο αλγόριθμος Shuffle λαμβάνει μια πηγή τυχαιότητας και στη συνέχεια διασχίζει τη λίστα προς τα πίσω, από τον τελευταίο κόμβο έως τον δεύτερο. Αλλάζει επανειλημμένα έναν τυχαία επιλεγμένο κόμβο (που είναι στην πραγματικότητα μόνο το πεδίο ονόματος) στην "τρέχουσα θέση". Οι κόμβοι επιλέγονται τυχαία από το τμήμα της λίστας που τρέχει από τον πρώτο κόμβο στην τρέχουσα θέση, συμπεριλαμβανομένων. Σημειώστε ότι αυτός ο αλγόριθμος προέρχεται από περίπου void shuffle (Λίστα λιστών)Ο πηγαίος κώδικας.

Ο αλγόριθμος Shuffle ψευδοκώδικας είναι τεμπέλης επειδή εστιάζει μόνο στη λίστα μεμονωμένων συνδέσεων προς τα εμπρός. Είναι μια λογική απόφαση σχεδιασμού, αλλά πληρώνουμε ένα τίμημα για αυτό στην πολυπλοκότητα του χρόνου. Η πολυπλοκότητα του χρόνου είναι O (ν2). Πρώτα, έχουμε το O (ν) βρόχο που καλεί ανταλαγή(). Δεύτερον, εντός ανταλαγή(), έχουμε τα δύο διαδοχικά O (νβρόχους. Θυμηθείτε τον ακόλουθο κανόνα από το Μέρος 1:

 Αν στ1(ν) = O (σολ(ν)) και στ2(ν) = O (η(ν)) μετά ένα) στ1(ν)+στ2(ν) = μέγιστο (O (σολ(ν)), O (η(ν))) (β) στ1(ν)*στ2(ν) = O (σολ(ν)*η(ν)). 

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

Σημειώστε ότι η πολυπλοκότητα του διαστήματος Shuffle είναι O (1), που προκύπτει από τις βοηθητικές μεταβλητές που δηλώνονται.

Παράδειγμα εφαρμογής: Ανακάτεμα σε μια λίστα διπλής σύνδεσης

ο Ανάμιξη Η εφαρμογή στην Λίστα 2 είναι μια επίδειξη του αλγορίθμου Shuffle.

Λίστα 2. Ο αλγόριθμος Shuffle στην Java

 εισαγωγή java.util.Random; δημόσια τελική τάξη Shuffle {private static class Node {String name; Επόμενος κόμβος Κόμβος prev; } public static void main (String [] args) {// Δημιουργήστε μια λίστα διπλής σύνδεσης. Κόμβος topForward = νέος κόμβος (); topForward.name = "A"; Κόμβος temp = νέος κόμβος (); temp.name = "B"; Κόμβος topBackward = νέος κόμβος (); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Απορρίψτε τη λίστα με έναν μόνο σύνδεσμο. System.out.print ("Προώθηση μεμονωμένης σύνδεσης:"); temp = topForward; ενώ (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Απορρίψτε τη λίστα με μια μόνο σύνδεση. System.out.print ("Λίστα προς τα πίσω μεμονωμένη σύνδεση:"); temp = topBackward; ενώ (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); // Ανακατέψτε τη λίστα. Random rnd = νέο Random (); για (int i = 3; i> 1; i--) swap (topForward, i - 1, rnd.nextInt (i)); // Απορρίψτε τη λίστα με έναν μόνο σύνδεσμο. System.out.print ("Προώθηση μεμονωμένης σύνδεσης:"); temp = topForward; ενώ (temp! = null) {System.out.print (temp.name); temp = temp.next; } System.out.println (); // Απορρίψτε τη λίστα μεμονωμένα συνδεδεμένα. System.out.print ("Λίστα προς τα πίσω μεμονωμένη σύνδεση:"); temp = topBackward; ενώ (temp! = null) {System.out.print (temp.name); temp = temp.prev; } System.out.println (); } δημόσια εναλλαγή στατικού κενού (Node top, int i, int j) {// Εντοπίστε τον κόμβο. Κόμβος nodei = κορυφή; για (int k = 0; k <i; k ++) nodei = nodei.next; // Εντοπίστε τον κόμβο jth. Κόμβος nodej = κορυφή; για (int k = 0; k <j; k ++) nodej = nodej.next; Συμβολοσειρά namei = nodei.name; Συμβολοσειρά namej = nodej.name; nodej.name = namei; nodei.name = namej; }} 

Συγκεντρώστε την καταχώριση 5 ως εξής:

 javac Shuffle.java 

Εκτελέστε την εφαρμογή που προκύπτει ως εξής:

 java Shuffle 

Θα πρέπει να παρατηρήσετε την ακόλουθη έξοδο από μία εκτέλεση:

 Προώθηση λίστας μεμονωμένων συνδέσμων: Λίστα μεμονωμένων συνδέσμων ABC Πίσω προς τα πίσω: CBA Προώθηση μεμονωμένης σύνδεσης: BAC Λίστα μεμονωμένων συνδέσεων προς τα πίσω: CAB 

Κυκλικές συνδεδεμένες λίστες

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

Λίστες κυκλικής σύνδεσης, γνωστές και ως κυκλικά ρυθμιστικά ή κυκλικές ουρές, έχει πολλές χρήσεις. Για παράδειγμα, χρησιμοποιούνται από χειριστές διακοπής του λειτουργικού συστήματος για την προσωρινή αποθήκευση πλήκτρων. Οι εφαρμογές πολυμέσων χρησιμοποιούν λίστες κυκλικής σύνδεσης για να αποθηκεύσουν δεδομένα προσωρινής αποθήκευσης (για παράδειγμα, δεδομένα buffering που γράφονται σε κάρτα ήχου). Αυτή η τεχνική χρησιμοποιείται επίσης από την οικογένεια LZ77 αλγορίθμων συμπίεσης δεδομένων χωρίς απώλειες.

Συνδεδεμένες λίστες σε σχέση με πίνακες

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

Οι συνδεδεμένες λίστες προσφέρουν τα ακόλουθα πλεονεκτήματα έναντι των συστοιχιών:

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

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

  • Τα στοιχεία της σειράς καταλαμβάνουν λιγότερη μνήμη από τους κόμβους, επειδή τα στοιχεία δεν απαιτούν πεδία συνδέσμου.
  • Οι συστοιχίες προσφέρουν ταχύτερη πρόσβαση σε στοιχεία δεδομένων, μέσω ευρετηρίων με ακέραιο αριθμό.
$config[zx-auto] not found$config[zx-overlay] not found