Θεωρία: Συνδεδεμένες Λίστες
Η έννοια της λίστας συναντάται πολύ συχνά στην καθημερινότητά μας. Σκεφτείτε πόσες φορές έχετε φτιάξει:
- Μια λίστα με τα αγαπημένα σας τραγούδια στο κινητό.
- Μια λίστα με τις επαφές σας.
- Μια λίστα με τα ψώνια του σούπερ μάρκετ.
- Μια λίστα με επιθυμίες και όνειρα (bucket list).
Η λίστα στην πληροφορική δεν είναι τίποτα άλλο παρά μια συλλογή από αντικείμενα (δεδομένα) του ίδιου τύπου, οργανωμένα σε μια σειρά.
1. Τι είναι η Συνδεδεμένη Λίστα;
Η συνδεδεμένη λίστα είναι μια δυναμική δομή δεδομένων. Σε αντίθεση με τους πίνακες, όπου τα στοιχεία πρέπει να βρίσκονται σε συνεχόμενες θέσεις μνήμης (σαν σπίτια σε έναν δρόμο), στη λίστα τα στοιχεία (που ονομάζονται κόμβοι) μπορεί να είναι διασκορπισμένα οπουδήποτε στη μνήμη.
Κάθε κόμβος αποτελείται από δύο μέρη:
- Δεδομένα: Η πληροφορία που θέλουμε να αποθηκεύσουμε (π.χ. αριθμός, όνομα).
- Δείκτης (Pointer): Η διεύθυνση του επόμενου κόμβου στη σειρά. Έτσι ξέρουμε πού να πάμε μετά.
Η λίστα συνοδεύεται πάντα από έναν ειδικό δείκτη, την Κεφαλή (Head), που μας λέει πού βρίσκεται ο πρώτος κόμβος. Ο τελευταίος κόμβος δείχνει στο NULL (κενό), που σημαίνει "τέλος της λίστας".
2. Κατηγορίες Λιστών
Α. Απλά Συνδεδεμένη Λίστα
Είναι η πιο απλή μορφή. Κάθε κόμβος συνδέεται μόνο με τον επόμενό του. Μπορούμε να τη διασχίσουμε μόνο προς μία κατεύθυνση (από την αρχή προς το τέλος), όπως σε έναν αγώνα σκυταλοδρομίας.
Β. Διπλά Συνδεδεμένη Λίστα
Εδώ, κάθε κόμβος έχει δύο δείκτες: έναν για τον επόμενο και έναν για τον προηγούμενο κόμβο. Αυτό μας επιτρέπει να κινούμαστε και προς τις δύο κατευθύνσεις.
3. Βασικές Πράξεις Λιστών
Σε μια λίστα μπορούμε να κάνουμε τις εξής βασικές λειτουργίες:
- Εισαγωγή: Προσθήκη νέου κόμβου (στην αρχή, στο τέλος ή ενδιάμεσα).
- Διαγραφή: Αφαίρεση ενός κόμβου.
- Έλεγχος Κενού: Να δούμε αν η λίστα είναι άδεια (αν η Κεφαλή είναι NULL).
- Αναζήτηση: Να ψάξουμε αν υπάρχει ένα στοιχείο στη λίστα.
- Διάσχιση: Να περάσουμε από όλους τους κόμβους (π.χ. για να τους τυπώσουμε).
4. Πώς γίνεται η Εισαγωγή και η Διαγραφή;
Η Λειτουργία της Εισαγωγής
Ας υποθέσουμε ότι σχεδιάζουμε ένα ταξίδι: Αθήνα → Λαμία → Λάρισα. Ξαφνικά, αποφασίζουμε να επισκεφθούμε τον Βόλο μετά τη Λαμία και πριν τη Λάρισα. Για να το κάνουμε αυτό στη λίστα, δεν χρειάζεται να μετακινήσουμε τίποτα. Απλώς αλλάζουμε τους δείκτες:
- Ο δείκτης της Λαμίας (που έδειχνε Λάρισα) τώρα θα δείχνει τον Βόλο.
- Ο δείκτης του Βόλου θα δείχνει τη Λάρισα.
Η Λειτουργία της Διαγραφής
Αν τελικά αποφασίσουμε να μην πάμε στη Λαμία (Αθήνα → Λαμία → Λάρισα), πρέπει να τη διαγράψουμε. Τότε, αλλάζουμε τον δείκτη της Αθήνας (προηγούμενος κόμβος) ώστε να δείχνει κατευθείαν στη Λάρισα, παρακάμπτοντας τη Λαμία. Η Λαμία αποσυνδέεται από τη λίστα.
5. Σύγκριση: Πίνακες vs Λίστες
| Χαρακτηριστικό | Πίνακας (Στατική Δομή) | Λίστα (Δυναμική Δομή) |
|---|---|---|
| Μνήμη | Συνεχόμενες θέσεις (σαν σπίτια στη σειρά) | Μη συνεχόμενες (διάσπαρτες) |
| Μέγεθος | Σταθερό (το δηλώνουμε στην αρχή) | Μεταβλητό (αυξομειώνεται δυναμικά) |
| Προσπέλαση | Τυχαία / Άμεση (μπορώ να πάω κατευθείαν στο 5ο στοιχείο) | Σειριακή (πρέπει να περάσω από όλα τα προηγούμενα) |
6. Πλεονεκτήματα & Μειονεκτήματα
- Δυναμικό μέγεθος: Δεν δεσμεύουμε περιττή μνήμη και δεν μας "τελειώνει" ο χώρος.
- Εύκολη εισαγωγή/διαγραφή: Αλλάζουμε απλώς τους δείκτες, χωρίς να χρειάζεται να μετακινήσουμε όλα τα άλλα στοιχεία (όπως θα κάναμε σε έναν πίνακα).
- Αργή προσπέλαση: Δεν μπορούμε να πάμε κατευθείαν στο 100ο στοιχείο. Πρέπει να περάσουμε από τα 99 προηγούμενα.
- Δεν γίνεται Δυαδική Αναζήτηση: Λόγω της σειριακής προσπέλασης.
- Επιπλέον Μνήμη: Κάθε κόμβος απαιτεί έξτρα χώρο για να αποθηκεύει τον δείκτη.