Η κλάση LinkedList στην Java είναι μια υλοποίηση της δομής δεδομένων συνδεδεμένης λίστας. Μια συνδεδεμένη λίστα αποτελείται από κόμβους που περιέχουν τα δεδομένα και μια αναφορά στον επόμενο κόμβο. Κάθε κόμβος συνδέεται με τον επόμενο κόμβο στην λίστα.
Η κλάση LinkedList παρέχει μια ευέλικτη δομή δεδομένων που επιτρέπει εισαγωγή, διαγραφή και αναζήτηση στοιχείων σε οποιαδήποτε θέση της λίστας. Επιπλέον, μπορεί να χρησιμοποιηθεί για την υλοποίηση άλλων δομών δεδομένων όπως οι στοίβες (stacks) και οι ουρές (queues).
Η χρήση της κλάσης LinkedList μπορεί να είναι χρήσιμη όταν απαιτείται δυναμική αναμόρφωση της λίστας, όπως προσθήκη ή διαγραφή στοιχείων σε οποιαδήποτε θέση. Επίσης, η συνδεδεμένη λίστα είναι χρήσιμη όταν ο αριθμός των στοιχείων που θα αποθηκευτούν δεν είναι γνωστός εκ των προτέρων ή αυξομειώνεται συχνά.
Η κλάση LinkedList χρησιμοποιείται για την αποθήκευση στοιχείων μιας λίστας με τη χρήση κόμβων. Αντίθετα από την ArrayList, η LinkedList δεν χρησιμοποιεί έναν εσωτερικό πίνακα για την αποθήκευση των στοιχείων. Κάθε κόμβος στη λίστα περιλαμβάνει μια τιμή και μια αναφορά (pointer) στον επόμενο κόμβο στη σειρά. Το τέλος της λίστας χαρακτηρίζεται από έναν κόμβο με μηδενική τιμή (null) ως αναφορά, γνωστός και ως “tail” της λίστας.
Η LinkedList είναι μια δομή δεδομένων που παρέχει μια σειρά από μεθόδους για τη διαχείριση των κόμβων της λίστας. Ορισμένες από τις σημαντικότερες μεθόδους που παρέχει είναι οι εξής:
- addFirst(Object element): προσθέτει ένα στοιχείο στην αρχή της λίστας.
- addLast(Object element): προσθέτει ένα στοιχείο στο τέλος της λίστας.
- removeFirst(): αφαιρεί το πρώτο στοιχείο από την αρχή της λίστας.
- removeLast(): αφαιρεί το τελευταίο στοιχείο από το τέλος της λίστας.
- getFirst(): επιστρέφει το πρώτο στοιχείο της λίστας.
- getLast(): επιστρέφει το τελευταίο στοιχείο της λίστας.
Αυτές οι μέθοδοι επιτρέπουν την προσθήκη, την αφαίρεση και την ανάκτηση στοιχείων από την αρχή και το τέλος της LinkedList.
Η κλάση LinkedList είναι ιδιαίτερα χρήσιμη για περιπτώσεις όπου οι λίστες αλλάζουν συχνά μέγεθος ή υποστούν συχνές εισαγωγές και διαγραφές στοιχείων. Η απόδοση της LinkedList δεν επηρεάζεται από το μέγεθος της λίστας, καθώς οι εισαγωγές και οι διαγραφές μπορούν να γίνονται σε σταθερό χρόνο. Αντίθετα, για μεγάλες λίστες με σπάνιες αλλαγές, η ArrayList συνήθως προσφέρει καλύτερη απόδοση, καθώς η πρόσβαση στα στοιχεία γίνεται με βάση τη θέση τους και η ArrayList έχει σταθερό χρόνο πρόσβασης σε οποιοδήποτε στοιχείο.
Για παράδειγμα, μπορούμε να δημιουργήσουμε μια LinkedList με τα ονόματα ανθρώπων και να τα εμφανίσουμε:
LinkedList<String> names = new LinkedList<String>(); // Δημιουργία μιας νέας συνδεδεμένης λίστας με στοιχεία τύπου String names.add("John"); // Προσθήκη του "John" στη λίστα names.add("Mary"); // Προσθήκη του "Mary" στη λίστα names.add("Peter"); // Προσθήκη του "Peter" στη λίστα System.out.println(names); // Εκτύπωση της λίστας στην οθόνη: [John, Mary, Peter]
Ο παραπάνω κώδικας δημιουργεί μια συνδεδεμένη λίστα (LinkedList) με στοιχεία τύπου String. Στη συνέχεια, προσθέτει τρία ονόματα (“John”, “Mary”, “Peter”) στη λίστα χρησιμοποιώντας τη μέθοδο add()
. Τέλος, εκτυπώνει τη λίστα στην οθόνη χρησιμοποιώντας τη μέθοδο println()
του αντικειμένου System.out
. Ο κωδικός θα εμφανίσει στην οθόνη το περιεχόμενο της λίστας, δηλαδή τα ονόματα “John”, “Mary” και “Peter”, τα οποία θα είναι τυπωμένα μέσα σε αγκύλες ([ ]).
Μπορούμε επίσης να προσθέσουμε και να αφαιρέσουμε στοιχεία από την αρχή και το τέλος της λίστας, χρησιμοποιώντας τις παραπάνω μεθόδους:
names.addFirst("George"); // Προσθέτει το "George" στην αρχή της λίστας names.addLast("Anna"); // Προσθέτει το "Anna" στο τέλος της λίστας System.out.println(names); // Εκτυπώνει τη λίστα ονομάτων: [George, John, Mary, Peter, Anna] names.removeFirst(); // Αφαιρεί το πρώτο στοιχείο από τη λίστα names.removeLast(); // Αφαιρεί το τελευταίο στοιχείο από τη λίστα System.out.println(names); // Εκτυπώνει την ενημερωμένη λίστα ονομάτων: [John, Mary, Peter]
Ο κώδικας πραγματοποιεί τις εξής ενέργειες:
- Προσθέτει τη συμβολοσειρά “George” στην αρχή μιας λίστας με όνομα
names
. - Προσθέτει τη συμβολοσειρά “Anna” στο τέλος της λίστας
names
. - Εκτυπώνει την τρέχουσα κατάσταση της λίστας
names
, που περιλαμβάνει τα στοιχεία “George”, “John”, “Mary”, “Peter” και “Anna”. - Αφαιρεί το πρώτο στοιχείο από τη λίστα
names
. - Αφαιρεί το τελευταίο στοιχείο από τη λίστα
names
. - Εκτυπώνει την ενημερωμένη κατάσταση της λίστας
names
, που περιλαμβάνει τα στοιχεία “John”, “Mary” και “Peter”.
Έτσι, ο κώδικας προσθέτει και αφαιρεί ονόματα από μια λίστα και εμφανίζει την ενημερωμένη λίστα στην οθόνη.
Το αποτέλεσμα στην οθόνη θα είναι:
[George, John, Mary, Peter, Anna] [John, Mary, Peter]
Αυτό σημαίνει ότι αρχικά η λίστα names
θα περιέχει τα στοιχεία “George”, “John”, “Mary”, “Peter” και “Anna”. Στη συνέχεια, θα αφαιρεθούν το πρώτο και το τελευταίο στοιχείο από τη λίστα, με αποτέλεσμα η λίστα να περιέχει τα στοιχεία “John”, “Mary” και “Peter”. Τα αποτελέσματα εκτυπώνονται στην οθόνη με χρήση της μεθόδου System.out.println()
.
[adinserter block=”2″]
Η LinkedList παρέχει τη δυνατότητα χρήσης iterators για την επανάληψη των στοιχείων της λίστας ή την τροποποίησή τους κατά τη διάρκεια της επαναληπτικής διαδικασίας.
Για παράδειγμα, μπορούμε να χρησιμοποιήσουμε ένα iterator για να αφαιρέσουμε συγκεκριμένα στοιχεία από μια λίστα:
LinkedList<Integer> numbers = new LinkedList<Integer>(); // Δημιουργία μιας συνδεδεμένης λίστας για ακέραιους αριθμούς numbers.add(10); // Προσθήκη του αριθμού 10 στη λίστα numbers.add(20); // Προσθήκη του αριθμού 20 στη λίστα numbers.add(30); // Προσθήκη του αριθμού 30 στη λίστα Iterator<Integer> iterator = numbers.iterator(); // Δημιουργία ενός επαναληπτή για την πρόσβαση στα στοιχεία της λίστας while (iterator.hasNext()) { Integer number = iterator.next(); // Λήψη του επόμενου στοιχείου από τη λίστα if (number == 20) { iterator.remove(); // Αφαίρεση του στοιχείου 20 από τη λίστα } } System.out.println(numbers); // Εκτύπωση των στοιχείων της λίστας: [10, 30]
Ο κώδικας πραγματοποιεί τις παρακάτω ενέργειες:
- Δημιουργεί μια συνδεδεμένη λίστα με ακέραιους αριθμούς με τη χρήση της κλάσης
LinkedList
. - Προσθέτει τους αριθμούς 10, 20 και 30 στη λίστα με τη μέθοδο
add()
. - Δημιουργεί έναν επαναλαμβανόμενο επαναλήπτη με τη χρήση της κλάσης
Iterator
για να περιηγηθεί στα στοιχεία της λίστας. - Επαναλαμβάνει μέσω του επαναλήπτη και ελέγχει αν υπάρχει επόμενο στοιχείο στη λίστα με τη μέθοδο
hasNext()
. - Εάν το τρέχον στοιχείο της λίστας είναι ίσο με 20, τότε το αφαιρεί από τη λίστα με τη μέθοδο
remove()
. - Στο τέλος, εκτυπώνει τα στοιχεία της λίστας χρησιμοποιώντας τη μέθοδο
println()
της κλάσηςSystem.out
.
Έτσι, ο κώδικας αφαιρεί τον αριθμό 20 από τη λίστα και εκτυπώνει τα υπόλοιπα στοιχεία της λίστας, που είναι τα 10 και 30.
Η LinkedList
στη Java υλοποιεί επίσης τη διεπαφή Queue
, η οποία χρησιμοποιείται για τη δημιουργία δομών στοίβας (stack) και ουράς (queue) για δεδομένα. Αυτό σημαίνει ότι μπορούμε να χρησιμοποιήσουμε τη LinkedList
για να δημιουργήσουμε ένα stack ή μια queue, ανάλογα με τις απαιτήσεις του προγράμματος.
Για παράδειγμα, μπορούμε να χρησιμοποιήσουμε τη LinkedList ως queue ως εξής:
Queue<String> queue = new LinkedList<String>(); // Δημιουργία ενός νέου Queue με χρήση της κλάσης LinkedList queue.add("apple"); // Προσθήκη του στοιχείου "apple" στο τέλος της ουράς queue.add("banana"); // Προσθήκη του στοιχείου "banana" στο τέλος της ουράς queue.add("orange"); // Προσθήκη του στοιχείου "orange" στο τέλος της ουράς System.out.println(queue); // Εκτύπωση της ουράς: [apple, banana, orange] String first = queue.remove(); // Αφαίρεση του πρώτου στοιχείου από την ουρά και αποθήκευσή του στη μεταβλητή "first" System.out.println(first); // Εκτύπωση του πρώτου στοιχείου: apple String second = queue.peek(); // Επιστροφή του πρώτου στοιχείου από την ουρά χωρίς να το αφαιρέσει και αποθήκευσή του στη μεταβλητή "second" System.out.println(second); // Εκτύπωση του πρώτου στοιχείου: banana System.out.println(queue); // Εκτύπωση της ουράς μετά τις αφαιρέσεις: [banana, orange]
Ο κώδικας αυτός δημιουργεί ένα Queue (ουρά) με χρήση της κλάσης LinkedList και πραγματοποιεί τις παρακάτω ενέργειες:
- Προσθήκη των στοιχείων “apple”, “banana” και “orange” στο τέλος της ουράς.
- Εκτύπωση της ουράς, που θα εμφανίσει: [apple, banana, orange].
- Αφαίρεση του πρώτου στοιχείου από την ουρά και αποθήκευσή του στη μεταβλητή “first”. Σε αυτήν την περίπτωση, το πρώτο στοιχείο είναι το “apple”.
- Εκτύπωση του πρώτου στοιχείου, που θα εμφανίσει: apple.
- Επιστροφή του πρώτου στοιχείου από την ουρά χωρίς να το αφαιρέσει και αποθήκευσή του στη μεταβλητή “second”. Σε αυτήν την περίπτωση, το πρώτο στοιχείο είναι το “banana”.
- Εκτύπωση του πρώτου στοιχείου, που θα εμφανίσει: banana.
- Εκτύπωση της ουράς μετά τις αφαιρέσεις, που θα εμφανίσει: [banana, orange].
Ο κώδικας δείχνει πώς μπορεί να χρησιμοποιηθεί ένα Queue για να αποθηκεύσει και να διαχειριστεί δεδομένα με τη σειρά που εισάγονται και αφαιρούνται από αυτό.
Η κλάση LinkedList αποτελεί ένα πολύτιμο εργαλείο για τη δημιουργία λιστών στην Java και μπορεί να χρησιμοποιηθεί ευρέως για τη διαχείριση δεδομένων σε πολλές περιπτώσεις. Με τη χρήση της LinkedList, μπορούμε να προσθέτουμε στοιχεία στο τέλος της λίστας, να τα αφαιρούμε από την αρχή της, να προσπελαύνουμε τα στοιχεία της λίστας και να εκτελούμε άλλες ενέργειες που αφορούν τη διαχείριση των δεδομένων. Επίσης, η LinkedList προσφέρει ευέλικτες δυνατότητες για την αποθήκευση και την αναζήτηση δεδομένων, καθιστώντας την κατάλληλη για πολλές εφαρμογές και περιπτώσεις χρήσης.
Ένα επιπλέον χρήσιμο χαρακτηριστικό της LinkedList είναι η δυνατότητα να εισάγουμε και να αφαιρούμε στοιχεία από τη μέση της λίστας. Αυτό είναι εφικτό λόγω του τρόπου με τον οποίο οι κόμβοι της λίστας υλοποιούνται με αναφορές (pointers) προς τους προηγούμενους και επόμενους κόμβους. Με αυτόν τον τρόπο, μπορούμε να εισάγουμε ή να αφαιρούμε στοιχεία σε οποιαδήποτε θέση της λίστας, χωρίς να απαιτείται η μετακίνηση όλων των υπολοίπων στοιχείων της λίστας.
[adinserter block=”3″]
Για παράδειγμα, αν έχουμε την ακόλουθη λίστα:
LinkedList<String> list = new LinkedList<String>(); // Δημιουργία μιας νέας συνδεδεμένης λίστας με στοιχεία τύπου String list.add("apple"); // Προσθήκη της λέξης "apple" στη λίστα list.add("banana"); // Προσθήκη της λέξης "banana" στη λίστα list.add("orange"); // Προσθήκη της λέξης "orange" στη λίστα
Μπορούμε να εισάγουμε ένα στοιχείο (“grape”) στη δεύτερη θέση της λίστας χρησιμοποιώντας τη μέθοδο add(index, element)
:
list.add(1, "grape"); // Προσθέτει το στοιχείο "grape" στη θέση 1 της λίστας System.out.println(list); // Εκτυπώνει τη λίστα: [apple, grape, banana, orange]
Μπορούμε επίσης να αφαιρέσουμε το δεύτερο στοιχείο της λίστας (“grape”) χρησιμοποιώντας τη μέθοδο remove(index)
:
list.remove(1); // Αφαιρεί το στοιχείο στη θέση 1 από τη λίστα System.out.println(list); // Εκτυπώνει τη λίστα: [apple, orange]
Για παράδειγμα, μπορούμε να προσθέσουμε στοιχεία στην αρχή της λίστας (ως stack) χρησιμοποιώντας τις μεθόδους push()
και pop()
:
LinkedList<String> stack = new LinkedList<String>(); // Δημιουργία ενός κενού στοίβας LinkedList stack.push("apple"); // Προσθήκη του στοιχείου "apple" στην κορυφή του στοίβας stack.push("banana"); // Προσθήκη του στοιχείου "banana" στην κορυφή του στοίβας stack.push("orange"); // Προσθήκη του στοιχείου "orange" στην κορυφή του στοίβας String top = stack.pop(); // Αφαίρεση και επιστροφή του στοιχείου από την κορυφή του στοίβας System.out.println(top); // Εκτύπωση του στοιχείου που αφαιρέθηκε (αναμένεται "orange") System.out.println(stack); // Εκτύπωση του περιεχομένου του στοίβας (αναμένεται "[banana, apple]")
Ο κώδικας παρουσιάζει μια απλή χρήση ενός στοίβας (stack) με χρήση της κλάσης LinkedList στην Java. Οι ενέργειες που πραγματοποιούνται είναι οι εξής:
- Δημιουργία ενός κενού στοίβας LinkedList με όνομα “stack”.
- Προσθήκη των στοιχείων “apple”, “banana” και “orange” στην κορυφή του στοίβας, χρησιμοποιώντας τη μέθοδο “push()”.
- Αφαίρεση του στοιχείου από την κορυφή του στοίβας και αποθήκευσή του στη μεταβλητή “top”, χρησιμοποιώντας τη μέθοδο “pop()”.
- Εκτύπωση της τιμής της μεταβλητής “top”, που είναι το αφαιρεθέν στοιχείο από το στοίβας.
- Εκτύπωση του περιεχομένου του στοίβας με τη χρήση της μεθόδου “println()” της κλάσης “System.out”, που εμφανίζει το στοίβας ως μια λίστα με τα στοιχεία που περιέχει.
Έτσι, ο κώδικας εμφανίζει στην οθόνη τη λέξη “orange” και το περιεχόμενο του στοίβας “[banana, apple]”.
Μπορούμε επίσης να προσθέσουμε στοιχεία στο τέλος της λίστας (ως queue) χρησιμοποιώντας τη μέθοδο add()
:
LinkedList<String> queue = new LinkedList<String>(); // Δημιουργία μιας συνδεδεμένης λίστας (queue) που περιέχει στοιχεία τύπου String queue.add("apple"); // Προσθήκη του στοιχείου "apple" στην ουρά queue.add("banana"); // Προσθήκη του στοιχείου "banana" στην ουρά queue.add("orange"); // Προσθήκη του στοιχείου "orange" στην ουρά String first = queue.remove(); // Αφαίρεση του πρώτου στοιχείου από την ουρά και αποθήκευσή του στη μεταβλητή first System.out.println(first); // Εκτύπωση της μεταβλητής first που περιέχει το πρώτο στοιχείο που αφαιρέθηκε ("apple") System.out.println(queue); // Εκτύπωση της λίστας queue που περιέχει τα υπόλοιπα στοιχεία ("banana", "orange")
Ο παραπάνω κώδικας χρησιμοποιεί μια συνδεδεμένη λίστα (LinkedList) με στοιχεία τύπου String για να δημιουργήσει μια ουρά (queue). Στη συνέχεια, προσθέτει τρία στοιχεία (“apple”, “banana”, “orange”) στην ουρά με τη χρήση της μεθόδου add()
.
Έπειτα, από την ουρά αφαιρείται το πρώτο στοιχείο χρησιμοποιώντας τη μέθοδο remove()
και αποθηκεύεται στη μεταβλητή first
. Τέλος, εκτυπώνεται η τιμή της first
που αντιστοιχεί στο πρώτο στοιχείο που αφαιρέθηκε (“apple”), καθώς και ολόκληρη η ουρά queue
, η οποία περιέχει τα υπόλοιπα στοιχεία (“banana”, “orange”), με τη χρήση της μεθόδου System.out.println()
.
Η LinkedList είναι μια ευέλικτη κλάση στην Java που παρέχει λειτουργίες για τη διαχείριση λιστών και δεδομένων. Η επιλογή ανάμεσα στη LinkedList και στην ArrayList εξαρτάται από τις απαιτήσεις της εφαρμογής και τον τρόπο που οι λίστες θα χρησιμοποιηθούν στο πρόγραμμα.
Η LinkedList προσφέρει ορισμένα πλεονεκτήματα, όπως η δυνατότητα εισαγωγής και διαγραφής στοιχείων σε οποιαδήποτε θέση της λίστας με σχετικά χαμηλό κόστος. Αυτό την καθιστά κατάλληλη για περιπτώσεις όπου οι αλλαγές στη δομή της λίστας είναι συχνές.
Από την άλλη πλευρά, η ArrayList προσφέρει γρήγορη πρόσβαση σε στοιχεία βάσει της θέσης τους στη λίστα. Αν η εφαρμογή απαιτεί συχνές αναγνώσεις των στοιχείων με βάση τη θέση τους, η ArrayList μπορεί να είναι πιο αποδοτική.
Επομένως, η επιλογή μεταξύ LinkedList και ArrayList πρέπει να γίνει με βάση τις απαιτήσεις της εφαρμογής και τις συγκεκριμένες λειτουργίες που απαιτούνται από τις λίστες στο πρόγραμμα.