Συνδεδεμένη Λίστα-Εισαγωγή

Η έννοια της λίστας συναντάται αρκετά συχνά στην καθημερινότητά μας.
Πόσες φορές δεν έχουμε καταρτίσει λίστες με
τα αγαπημένα μας τραγούδια,
τις επαφές μας,
τα ψώνια που θέλουμε να κάνουμε ή ακόμα και λίστες με επιθυμίες και όνειρα;
Η λίστα δεν είναι τίποτα άλλο παρά μία
συλλογή από αντικείμενα του ίδιου τύπου.
Μπορούμε να έχουμε δηλαδή λίστες από λέξεις,
από ονόματα αλλά και από αριθμούς.
Πώς όμως θα μπορούσατε να αποθηκεύσετε
έναν συγκεκριμένο αριθμό στοιχείων του ίδιου τύπου,
για παράδειγμα:
τα μέρη που θα θέλατε να επισκεφτείτε;
Μία από τις δομές δεδομένων που έχετε δει μέχρι τώρα
και που θα μπορούσατε να χρησιμοποιήσετε
για να αποθηκεύσετε τα στοιχεία αυτά είναι οι πίνακες.
Πολύ απλά και εύκολα μπορείτε να τους δημιουργήσετε
και να προσπελάστε άμεσα οποιοδήποτε στοιχείο τους.
Το γεγονός, όμως, ότι το μέγεθος ενός πίνακα
παραμένει σταθερό (στατική δομή δεδομένων),
δυσχεραίνει την προσθήκη και τη διαγραφή στοιχείων.
Θεωρείστε την περίπτωση που θέλετε να προσθέσετε στον πίνακα
και άλλα μέρη στα οποία θέλετε να ταξιδέψετε.
Τι θα κάνετε αν ο πίνακας είναι γεμάτος;
Μια πρώτη απάντηση θα ήταν
να δημιουργήσουμε έναν νέο μεγαλύτερο πίνακα και
να αντιγράψουμε
σε αυτόν τα στοιχεία του προηγούμενου πίνακα.
Έτσι, θα είχαμε μεγαλύτερο χώρο
για να προσθέσουμε και νέα στοιχεία.
Θεωρείτε ότι αυτή είναι η ιδανική λύση,
όταν η προσθήκη και η διαγραφή
στοιχείων αποτελεί συχνό φαινόμενο;
Ας μελετήσουμε μία άλλη λύση, δηλαδή μία νέα δυναμική δομή δεδομένων,
τις συνδεδεμένες λίστες, που απαντάει σε αυτές τις προκλήσεις.
Αρχικά, ας θεωρήσουμε το πλέγμα των κελιών
ως τη μνήμη του υπολογιστή.
Σε κάθε κελί αντιστοιχίζεται μία διεύθυνση.
Για να προσπελάσουμε ένα οποιαδήποτε κελί
θα πρέπει να γνωρίζουμε τη διεύθυνσή του.
Στην Εικόνα παρουσιάζεται ο χώρος που καταλαμβάνει ο πίνακας Α με το γαλάζιο χρώμα.
Ο πίνακας αυτός αποτελείται από έξι στοιχεία
τα οποία είναι αποθηκευμένα σε συνεχόμενες θέσεις μνήμης.
Συνήθως όμως, η μνήμη του υπολογιστή δεν είναι τόσο καθαρή και τακτοποιημένη.
Στην Εικόνα φαίνονται τα διάσπαρτα (μη συνεχόμενα)
ελεύθερα κελιά με το κόκκινο χρώμα.
Στην προκειμένη περίπτωση, δεν μπορείτε να «τοποθετήσετε» έναν πίνακα στη μνήμη,
διότι δεν υπάρχουν συνεχόμενες ελεύθερες θέσεις.
Μπορείτε, όμως, να χρησιμοποιήσετε τις διάσπαρτες αυτές ελεύθερες θέσεις
για να αποθηκεύσετε τα δεδομένα σας, αν θεωρήσετε ότι αποτελούν «στοιχεία» μίας συνδεδεμένης λίστας.
Η συνδεδεμένη λίστα αποτελείται από μία σειρά από κόμβους,
που συνήθως βρίσκονται σε απομακρυσμένες θέσεις μνήμης.
Κάθε κόμβος αποτελείται από δύο κύρια τμήματα
Το πρώτο τμήμα περιέχει τα δεδομένα και
το δεύτερο τμήμα φιλοξενεί τη διεύθυνση του επόμενου κόμβου
με τον οποίο συνδέεται ή όπως αλλιώς θα λέγαμε στη γλώσσα των δομών δεδομένων,
το δεύτερο τμήμα περιέχει έναν δείκτη (pointer) που δείχνει στον επόμενο κόμβο.
Το πεδίο Δεδομένα μπορεί να περιέχει μία ή περισσότερες
αλφαριθμητικές ή αριθμητικές πληροφορίες.
Ο δείκτης (pointer) είναι ένας ιδιαίτερος τύπος δεδομένων
που προσφέρεται από τις περισσότερες σύγχρονες γλώσσες προγραμματισμού.
Ο δείκτης δε λαμβάνει αριθμητικές τιμές όπως ακέραιες, πραγματικές κ.ά.,
αλλά οι τιμές του είναι διευθύνσεις στην κύρια μνήμη
και χρησιμοποιείται ακριβώς για τη σύνδεση των διαφόρων στοιχείων μιας δομής,
που είναι αποθηκευμένα σε μη συνεχόμενες θέσεις μνήμης.
Ένα παράδειγμα απλά συνδεδεμένης λίστας με τεσσερις κόμβους, που περιέχουν ακεραίους,
δίνεται στην παρακάτω Εικόνα,
Ο δείκτης του τελευταίου κόμβου της λίστας έχει ως τιμή το NULL (κενό)
και τον αναπαριστούμε συμβολικά με το σύμβολο «•».
Οι δείκτες των υπολοίπων κόμβων περιέχουν τη διεύθυνση του επόμενου κόμβου αντίστοιχα
και τους απεικονίζουμε συμβολικά με ένα βέλος → για να υποδηλώσουμε τη σύνδεση
μεταξύ του προηγούμενου και του επόμενου κόμβου.
Κάθε λίστα συνοδεύεται από έναν δείκτη με το όνομα «Κεφαλή» (head),
που δείχνει στον πρώτο κόμβο της λίστας,
δηλαδή περιέχει τη διεύθυνση του πρώτου κόμβου της λίστας.