Εισαγωγή στη χρήση συνδεδεμένων λιστών στην Java

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

Αλλά πώς δημιουργείτε μια συνδεδεμένη λίστα στην Java; Ας ΡΙΞΟΥΜΕ μια ΜΑΤΙΑ.

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

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

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

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

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

Σχετίζεται με: Μάθετε πώς να δημιουργείτε τάξεις σε Java

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

Παράδειγμα κλάσης κόμβου

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

κόμβος δημόσιας τάξης {
private int Δεδομένα;
ιδιωτικός κόμβος NextNode;
//constructor
δημόσιος κόμβος () {
Δεδομένα = 0;
NextNode = null;
}
// αποκτήτες και ρυθμιστές
public int getData () {
επιστροφή δεδομένων.
}
public void setData (int data) {
Δεδομένα = δεδομένα.
}
δημόσιος κόμβος getNextNode () {
επιστροφή NextNode.
}
public void setNextNode (Node nextNode) {
NextNode = nextNode;
}
}

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

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

δημόσια τάξη LinkedList {
ιδιωτική κεφαλή κόμβου.
//constructor
δημόσιο LinkedList () {
Head = null;
}
}

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

• Εισάγετε μπροστά.
• Εισάγετε στη μέση.
• Εισάγετε στο πίσω μέρος.

Σχετίζεται με: Πώς να δημιουργήσετε δομές δεδομένων με κλάσεις JavaScript ES6

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

Χρησιμοποιώντας τη μέθοδο εισαγωγής στο μπροστινό μέρος

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

Εισαγωγή στο Παράδειγμα μεθόδου μπροστά

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

 // εισαγωγή κόμβου στην μπροστινή μέθοδο
public void insertAtFront (int key) {
// δημιουργήστε έναν νέο κόμβο χρησιμοποιώντας την κλάση κόμβων
Node Temp = new Node ();
// ελέγξτε εάν ο κόμβος Temp δημιουργήθηκε με επιτυχία
// εκχωρήστε τα δεδομένα που παρείχε ο χρήστης σε αυτό
εάν (Temp! = null) {
Temp.setData (κλειδί);
Temp.setNextNode (null);
// ελέγξτε αν η κεφαλή της συνδεδεμένης λίστας είναι κενή
// αντιστοιχίστε τον κόμβο που μόλις δημιουργήθηκε στη θέση κεφαλής
if (Head == null) {
Head = Temp;
}
// εάν ένας κόμβος βρίσκεται ήδη στη θέση κεφαλής
// προσθέστε τον νέο κόμβο σε αυτόν και ορίστε τον ως κεφαλή
αλλιώς {
Temp.setNextNode (Head);
Head = Temp;
}
}
}

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

Εφαρμογή του Insert στο μπροστινό παράδειγμα

Παρακάτω είναι ένα παράδειγμα του τρόπου με τον οποίο θα εφαρμόζατε το ένθετο στο μπροστινό μέρος.

οδηγός δημόσιας τάξης {
// εκτελεί το πρόγραμμα
public static void main (String [] args) {
// δημιουργήστε μια νέα συνδεδεμένη λίστα που ονομάζεται Λίστα
LinkedList List = νέα LinkedList ();
// προσθέστε κάθε τιμή στο μπροστινό μέρος της συνδεδεμένης λίστας ως νέος κόμβος
List.insertAtFront (10);
List.insertAtFront (8);
List.insertAtFront (6);
List.insertAtFront (4);
List.insertAtFront (2);
}
}

ο Οδηγός class (που είναι το όνομα που συχνά αποδίδεται στην εκτελέσιμη κλάση στη Java), χρησιμοποιεί την κλάση LinkedList για να δημιουργήσει μια συνδεδεμένη λίστα πέντε ζυγών αριθμών. Κοιτάζοντας τον παραπάνω κώδικα, θα πρέπει να είναι εύκολο να διαπιστώσετε ότι ο αριθμός "2" βρίσκεται στην επικεφαλίδα στη συνδεδεμένη λίστα. Πώς μπορείτε όμως να το επιβεβαιώσετε;

Χρήση της μεθόδου εμφάνισης όλων των κόμβων

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

Παράδειγμα μεθόδου εμφάνισης όλων των κόμβων

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

// εμφάνιση όλων των μεθόδων κόμβων
public void displayAllNodes () {
// δημιουργήστε μια νέα κλήση κλήσης Temp και αντιστοιχίστε την στην κεφαλή της συνδεδεμένης λίστας
// αν η κεφαλή έχει μηδενική τιμή, τότε η συνδεδεμένη λίστα είναι κενή
Node Temp = Head;
if (Head == null) {
System.out.println ("Η λίστα είναι κενή.");
ΕΠΙΣΤΡΟΦΗ;
}
System.out.println ("Η λίστα:");
while (Temp! = null) {
// εκτύπωση των δεδομένων σε κάθε κόμβο στην κονσόλα (ξεκινώντας από την κεφαλή)
System.out.print (Temp.getData () + "");
Temp = Temp.getNextNode ();
} 
}

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

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

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

// εκτυπώστε τους κόμβους σε μια συνδεδεμένη λίστα
List.displayAllNodes (); 

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

Η λίστα:

2 4 6 8 10

Χρήση της μεθόδου Εύρεση κόμβου

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

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

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

Εύρεση παραδείγματος μεθόδου κόμβου

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

// αναζήτηση ενός μόνο κόμβου χρησιμοποιώντας ένα κλειδί
δημόσιο boolean findNode (κλειδί int) {
// δημιουργήστε έναν νέο κόμβο και τοποθετήστε τον στο κεφάλι της συνδεδεμένης λίστας
Node Temp = Head;
// ενώ ο τρέχων κόμβος δεν είναι κενός
// ελέγξτε εάν τα δεδομένα του ταιριάζουν με το κλειδί που παρέχει ο χρήστης
while (Temp! = null) {
if (Temp.getData () == κλειδί) {
System.out.println ("Ο κόμβος είναι στη λίστα"); 
επιστροφή αληθινός?
}
// μετακίνηση στον επόμενο κόμβο
Temp = Temp.getNextNode ();
}
// εάν το κλειδί δεν βρέθηκε στη συνδεδεμένη λίστα
System.out.println ("Ο κόμβος δεν είναι στη λίστα"); 
επιστροφή ψευδής?
}

Με την displayAllNodes μέθοδο, επιβεβαιώσατε ότι το LinkedList περιέχει 5 ζυγούς αριθμούς από 2 έως 10. ο findNode Το παραπάνω παράδειγμα μπορεί να επιβεβαιώσει εάν ένας από αυτούς τους άρτιους αριθμούς είναι ο αριθμός 4 καλώντας απλώς τη μέθοδο στην κατηγορία προγραμμάτων οδήγησης και παρέχοντας τον αριθμό ως παράμετρο.

Χρησιμοποιώντας το παράδειγμα της μεθόδου Εύρεση κόμβου

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

// ελέγξτε εάν ένας κόμβος βρίσκεται στη συνδεδεμένη λίστα
List.findNode (4);

Ο παραπάνω κώδικας θα παράγει την ακόλουθη έξοδο στην κονσόλα:

Ο κόμβος βρίσκεται στη λίστα

Χρήση της μεθόδου Διαγραφή κόμβου

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

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

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

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

public void findAndDelete (int key) { 
Node Temp = Head; 
Node prev = null; 
// ελέγξτε αν ο κόμβος κεφαλής περιέχει τα δεδομένα 
// και διαγράψτε το 
if (Temp! = null && Temp.getData () == κλειδί) { 
Head = Temp.getNextNode (); 
ΕΠΙΣΤΡΟΦΗ; 
} 
// αναζήτηση στους άλλους κόμβους της λίστας 
// και διαγράψτε το 
while (Temp! = null) { 
if (Temp.getNextNode (). getData () == κλειδί) { 
prev = Temp.getNextNode (). getNextNode (); 
Temp.setNextNode (προηγούμενο); 
ΕΠΙΣΤΡΟΦΗ; 
} 
Temp = Temp.getNextNode (); 
} 
} 

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

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

// διαγράψτε τον κόμβο που περιέχει τα δεδομένα 4
List.findAndDelete (4);
// εκτύπωση όλων των κόμβων στη συνδεδεμένη λίστα
List.displayAllNodes ();

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

Η λίστα:
2 6 8 10

Αν φτάσατε στο τέλος αυτού του άρθρου, θα έχετε μάθει:

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

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

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

Μαθαίνετε Java; Αφήστε τους πίνακες να χειρίζονται τα δεδομένα σας με ευκολία.

Διαβάστε Επόμενο

Σχετικά με τον Συγγραφέα