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

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

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

 τάξη Υπάλληλος {ιδιωτικό int empno; ιδιωτικό όνομα συμβολοσειράς; ιδιωτικός διπλός μισθός · δημόσιος υπάλληλος στη συνέχεια? // Άλλα μέλη. }

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

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

λήψη Λήψη κωδικού Λήψη των τριών παραδειγμάτων εφαρμογών για αυτό το άρθρο. Δημιουργήθηκε από τον Jeff Friesen για το JavaWorld.

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

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

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

Παρακάτω είναι ο ψευδοκώδικας για μια λίστα που συνδέεται μεμονωμένα.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

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

Δημιουργία μιας μοναδικής συνδεδεμένης λίστας στην Java

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

 κορυφή = ΝΕΟΣ κόμβος top.name = "A" top.next = NULL 

Το Σχήμα 2 δείχνει την αρχική μεμονωμένη λίστα που εμφανίζεται από αυτόν τον ψευδοκώδικα.

Αυτή η λειτουργία έχει χρονική πολυπλοκότητα O (1) - σταθερή. Θυμηθείτε ότι το O (1) προφέρεται "Big Oh of 1." (Δείτε το Μέρος 1 για μια υπενθύμιση του τρόπου με τον οποίο χρησιμοποιούνται οι μετρήσεις πολυπλοκότητας χρόνου και χώρου για την αξιολόγηση των δομών δεδομένων.)

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

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

  • Εισαγωγή πριν από τον πρώτο κόμβο.
  • Εισαγωγή μετά τον τελευταίο κόμβο.
  • Εισαγωγή μεταξύ δύο κόμβων.

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

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

 ΔΗΛΩΣΗ Temp κόμβου temp = ΝΕΟ κόμβος temp.name = "B" temp.next = top top = temp 

Οι προκύπτουσες δύοΚόμβος λίστα εμφανίζεται στο σχήμα 3.

Αυτή η λειτουργία έχει χρονική πολυπλοκότητα του O (1).

Εισαγωγή μετά τον τελευταίο κόμβο

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

 temp = NEW Κόμβος temp.name = "C" temp.next = NULL DECLARE Κόμβος temp2 temp2 = top // Υποθέτουμε ότι το top (και το temp2) δεν είναι NULL // λόγω του προηγούμενου ψευδοκώδικα. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 αναφέρεται τώρα στον τελευταίο κόμβο. temp2.next = temp 

Το σχήμα 4 αποκαλύπτει τη λίστα μετά την εισαγωγή του Κόμβος C μετά Κόμβος ΕΝΑ.

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

Εισαγωγή μεταξύ δύο κόμβων

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

 temp = NEW κόμβος temp.name = "D" temp2 = top // Υποθέτουμε ότι ο νεοσύστατος κόμβος εισάγει μετά τον κόμβο // A και ότι υπάρχει ο κόμβος Α. Στον πραγματικό κόσμο, δεν υπάρχει // εγγύηση ότι υπάρχει οποιοσδήποτε κόμβος, οπότε θα πρέπει να ελέγξουμε // για temp2 που περιέχει NULL τόσο στην κεφαλίδα του WHILE loop // και μετά την ολοκλήρωση του βρόχου WHILE. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 τώρα αναφέρεται στον κόμβο A. temp.next = temp2.next temp2.next = temp 

Το σχήμα 5 παρουσιάζει τη λίστα μετά την εισαγωγή του Κόμβος Δ μεταξύ Κόμβοςs Α και Γ.

Αυτή η λειτουργία έχει χρονική πολυπλοκότητα του O (ν).

Διαγραφή κόμβων από μια λίστα που συνδέεται μεμονωμένα

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

  • Διαγραφή του πρώτου κόμβου.
  • Διαγραφή οποιουδήποτε κόμβου εκτός από τον πρώτο κόμβο.

Διαγραφή του πρώτου κόμβου

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

 ΕΑΝ κορυφή NE NULL THEN top = top.next; // Αναφορά στον δεύτερο κόμβο (ή NULL όταν υπάρχει μόνο ένας κόμβος). ΤΕΛΟΣ ΕΑΝ 

Το Σχήμα 6 παρουσιάζει πριν και μετά από προβολές μιας λίστας όπου η πρώτη Κόμβος έχει διαγραφεί. Κόμβος σι εξαφανίζεται και Κόμβος Α γίνεται το πρώτο Κόμβος.

Αυτή η λειτουργία έχει χρονική πολυπλοκότητα του O (1).

Διαγραφή οποιουδήποτε κόμβου εκτός από τον πρώτο κόμβο

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

 ΕΑΝ κορυφή NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // Υποθέτουμε ότι η θερμοκρασία αναφέρεται στον κόμβο A. temp.next = temp.next.next // Ο κόμβος D δεν υπάρχει πλέον. ΤΕΛΟΣ ΕΑΝ 

Το Σχήμα 7 παρουσιάζει πριν και μετά από προβολές μιας λίστας όπου ένα ενδιάμεσο Κόμβος διαγράφεται. Κόμβος D εξαφανίζεται.

Αυτή η λειτουργία έχει χρονική πολυπλοκότητα του O (ν).

Παράδειγμα # 1: Δημιουργήστε, εισαγάγετε και διαγράψτε σε μια μόνο λίστα

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

Λίστα 1. Επίδειξη εφαρμογής Java για λίστες που συνδέονται μεμονωμένα (SSLDemo.java, έκδοση 1)

 δημόσιο τελικό μάθημα SLLDemo {ιδιωτική στατική τάξη Κόμβος {Όνομα συμβολοσειράς; Επόμενος κόμβος } δημόσιος στατικός κενός κενός (String [] args) {Node top = null; // 1. Η λίστα που συνδέεται μεμονωμένα δεν υπάρχει. κορυφή = νέος κόμβος (); top.name = "A"; top.next = null; χωματερή ("Περίπτωση 1", κορυφή) · // 2. Υπάρχει η μοναδικά συνδεδεμένη λίστα και ο κόμβος πρέπει να εισαχθεί // πριν από τον πρώτο κόμβο. Temp κόμβου; temp = νέος κόμβος (); temp.name = "B"; temp.next = κορυφή; κορυφή = temp; χωματερή ("Περίπτωση 2", κορυφή) · // 3. Η μοναδικά συνδεδεμένη λίστα υπάρχει και ο κόμβος πρέπει να εισαχθεί // μετά τον τελευταίο κόμβο. temp = νέος κόμβος (); temp.name = "C"; temp.next = null; Κόμβος temp2; temp2 = κορυφή; ενώ (temp2.next! = null) temp2 = temp2.next; temp2.next = temp; χωματερή ("Περίπτωση 3", κορυφή) · // 4. Η μοναδικά συνδεδεμένη λίστα υπάρχει και ο κόμβος πρέπει να εισαχθεί // μεταξύ δύο κόμβων. temp = νέος κόμβος (); temp.name = "D"; temp2 = κορυφή; ενώ (temp2.name.equals ("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; χωματερή ("Περίπτωση 4", κορυφή) · // 5. Διαγράψτε τον πρώτο κόμβο. κορυφή = top.next; dump ("Μετά τη διαγραφή του πρώτου κόμβου", κορυφή); // 5.1 Επαναφορά κόμβου B. temp = νέος κόμβος (); temp.name = "B"; temp.next = κορυφή; κορυφή = temp; // 6. Διαγράψτε οποιονδήποτε κόμβο εκτός από τον πρώτο κόμβο. temp = κορυφή; ενώ (temp.name.equals ("A") == false) temp = temp.next; temp.next = temp.next.next; dump ("Μετά τη διαγραφή κόμβου D", κορυφή); } ιδιωτικό στατικό κενό, (String msg, Node topNode) {System.out.print (msg + ""); ενώ (topNode! = null) {System.out.print (topNode.name + ""); topNode = topNode.next; } System.out.println (); }} 

Μεταγλώττιση καταχώρισης 1 ως εξής:

 javac SLLDemo.java 

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

 java SLLDemo 

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

 Περίπτωση 1 A Περίπτωση 2 B A Case 3 B A C Περίπτωση 4 B A D C Μετά τη διαγραφή του πρώτου κόμβου A D C Μετά τη διαγραφή κόμβου D B A C 

Συνδυάζοντας μεμονωμένες συνδεδεμένες λίστες

Ίσως χρειαστεί περιστασιακά να συνενώσετε μια λίστα που συνδέεται με μία μόνο λίστα. Για παράδειγμα, ας υποθέσουμε ότι έχετε μια λίστα λέξεων που ξεκινούν με τα γράμματα A έως M και μια άλλη λίστα λέξεων που ξεκινούν με τα γράμματα N έως Z και θέλετε να συνδυάσετε αυτές τις λίστες σε μία λίστα. Ο ακόλουθος ψευδοκώδικας περιγράφει έναν αλγόριθμο για τη συνένωση μίας μεμονωμένης συνδεδεμένης λίστας με μια άλλη:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Ας υποθέσουμε τον κώδικα που δημιουργεί μια μοναδική συνδεδεμένη λίστα με αναφορές top1. // Ας υποθέσουμε τον κώδικα που δημιουργεί μια λίστα με μοναδικά συνδεδεμένη κορυφή 2. // Συνδυάστε τη λίστα με αναφορές top2 σε λίστα με αναφορές top1. IF top1 EQ NULL top1 = top2 END END IF // Εντοπισμός τελικού κόμβου στη λίστα με αναφορές top1. DECLARE Κόμβος temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Συνδυάστε top2 έως top1. temp.next = top2 ΤΕΛΟΣ 

Στην ασήμαντη περίπτωση, δεν υπάρχει κορυφή1-αναφερόμενη λίστα και ούτω καθεξής κορυφή1 έχει εκχωρηθεί κορυφή2αξία, που θα ήταν ΜΗΔΕΝΙΚΟ αν δεν υπήρχε κορυφή2-αναφερόμενη λίστα.

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

Αντιστροφή μιας συνδεδεμένης λίστας

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

 ΔΗΛΩΣΗ Κόμβος p = top1 // Αρχή της αρχικής λίστας μεμονωμένων συνδέσμων. ΔΗΛΩΣΗ Κόμβος q = NULL // Κορυφή της αντίστροφης λίστας μεμονωμένων συνδέσεων. DECLARE Κόμβος r // Προσωρινή μεταβλητή κόμβου αναφοράς. WHILE p NE NULL // Για κάθε κόμβο στην αρχική μεμονωμένη λίστα ... r = q // Αποθηκεύστε την αναφορά του μελλοντικού διαδόχου. q = p // Αναφορά μελλοντικού προκάτοχου Κόμβος. p = p.next // Αναφορά επόμενος κόμβος στην αρχική λίστα μεμονωμένα συνδεδεμένα. q.next = r // Σύνδεση μελλοντικού προκάτοχου Κόμβος με μελλοντικό διάδοχο Κόμβο. ΤΕΛΟΣ ΠΡΟΣΩΡΙΟΥ1 = q // Πρώτα, κάντε αναφορά στην κορυφή1 Κόμβος στην αντιστρεπτή λίστα που συνδέεται μεμονωμένα ΤΕΛΟΣ 

Αυτή η λειτουργία έχει χρονική πολυπλοκότητα του O (ν).

Παράδειγμα # 2: Συνδυάζοντας και αναστρέφοντας μια λίστα που συνδέεται μεμονωμένα

Έχω δημιουργήσει μια δεύτερη έκδοση του SLLDemo Εφαρμογή Java που εμφανίζει συνένωση και αντιστροφή. Η λίστα 2 παρουσιάζει τον πηγαίο κώδικα αυτής της εφαρμογής.