Πίνακες vs Συνδεδεμένες λίστες
Οι πίνακες είναι η πιο συχνά χρησιμοποιούμενη δομή δεδομένων για την αποθήκευση συλλογής στοιχείων. Οι περισσότερες γλώσσες προγραμματισμού παρέχουν μεθόδους για την εύκολη δήλωση πινάκων και πρόσβασης σε στοιχεία στους πίνακες. Η συνδεδεμένη λίστα, πιο συγκεκριμένα η μεμονωμένη λίστα, είναι επίσης μια δομή δεδομένων που μπορεί να χρησιμοποιηθεί για την αποθήκευση συλλογής στοιχείων. Αποτελείται από μια ακολουθία κόμβων και κάθε κόμβος έχει μια αναφορά στον επόμενο κόμβο της ακολουθίας.
Το Εμφανίζεται στο σχήμα 1, είναι ένα κομμάτι κώδικα που χρησιμοποιείται συνήθως για τη δήλωση και την εκχώρηση τιμών σε έναν πίνακα. Το σχήμα 2 απεικονίζει πώς θα φαινόταν ένας πίνακας στη μνήμη.
Ο παραπάνω κώδικας ορίζει έναν πίνακα που μπορεί να αποθηκεύσει 5 ακέραιους αριθμούς και η πρόσβαση σε αυτούς γίνεται χρησιμοποιώντας δείκτες 0 έως 4. Μια σημαντική ιδιότητα ενός πίνακα είναι ότι ολόκληρος ο πίνακας εκχωρείται ως ένα ενιαίο μπλοκ μνήμης και κάθε στοιχείο έχει το δικό του χώρο στη συστοιχία. Μόλις οριστεί ένας πίνακας, το μέγεθός του είναι σταθερό. Επομένως, εάν δεν είστε σίγουροι για το μέγεθος του πίνακα κατά τη στιγμή της μεταγλώττισης, θα πρέπει να ορίσετε έναν αρκετά μεγάλο πίνακα ώστε να βρίσκεται στην ασφαλή πλευρά. Όμως, τις περισσότερες φορές θα χρησιμοποιήσουμε στην πραγματικότητα λιγότερο αριθμό στοιχείων από αυτόν που έχουμε διαθέσει. Έτσι, ένα σημαντικό μέρος της μνήμης σπαταλάται πραγματικά. Από την άλλη πλευρά, εάν ο "αρκετά μεγάλος πίνακας" δεν είναι στην πραγματικότητα αρκετά μεγάλος, το πρόγραμμα θα διακοπεί.
Μια συνδεδεμένη λίστα εκχωρεί μνήμη στα στοιχεία της ξεχωριστά στο δικό της μπλοκ μνήμης και η συνολική δομή προκύπτει συνδέοντας αυτά τα στοιχεία ως συνδέσμους σε μια αλυσίδα. Κάθε στοιχείο σε μια συνδεδεμένη λίστα έχει δύο πεδία όπως φαίνεται στο Σχήμα 3. Το πεδίο δεδομένων περιέχει τα πραγματικά αποθηκευμένα δεδομένα και το επόμενο πεδίο περιέχει την αναφορά στο επόμενο στοιχείο της αλυσίδας. Το πρώτο στοιχείο της συνδεδεμένης λίστας αποθηκεύεται ως η κεφαλή της συνδεδεμένης λίστας.
| data | επόμενο |
Εικόνα 3: Στοιχείο μιας συνδεδεμένης λίστας
Η Εικόνα 4 απεικονίζει μια συνδεδεμένη λίστα με τρία στοιχεία. Κάθε στοιχείο αποθηκεύει τα δεδομένα του και όλα τα στοιχεία εκτός από το τελευταίο αποθηκεύουν μια αναφορά στο επόμενο στοιχείο. Το τελευταίο στοιχείο διατηρεί μια μηδενική τιμή στο επόμενο πεδίο του. Μπορείτε να έχετε πρόσβαση σε οποιοδήποτε στοιχείο της λίστας ξεκινώντας από την αρχή και ακολουθώντας τον επόμενο δείκτη μέχρι να ικανοποιήσετε το απαιτούμενο στοιχείο.
Αν και οι πίνακες και οι συνδεδεμένες λίστες είναι παρόμοιες με την έννοια ότι και οι δύο χρησιμοποιούνται για την αποθήκευση συλλογής στοιχείων, παρουσιάζουν διαφορές λόγω των στρατηγικών που χρησιμοποιούν για να εκχωρήσουν μνήμη στα στοιχεία τους. Οι πίνακες εκχωρούν μνήμη σε όλα τα στοιχεία του ως ένα ενιαίο μπλοκ και το μέγεθος του πίνακα πρέπει να καθοριστεί κατά το χρόνο εκτέλεσης. Αυτό θα έκανε τους πίνακες αναποτελεσματικούς σε περιπτώσεις όπου δεν γνωρίζετε το μέγεθος του πίνακα κατά τη στιγμή της μεταγλώττισης. Δεδομένου ότι μια συνδεδεμένη λίστα εκχωρεί μνήμη στα στοιχεία της ξεχωριστά, θα ήταν πολύ αποτελεσματική σε περιπτώσεις στις οποίες δεν γνωρίζετε το μέγεθος της λίστας τη στιγμή της μεταγλώττισης. Η δήλωση και η πρόσβαση σε στοιχεία σε μια συνδεδεμένη λίστα δεν θα ήταν απλή σε σύγκριση με τον τρόπο με τον οποίο αποκτάτε απευθείας πρόσβαση σε στοιχεία σε έναν πίνακα χρησιμοποιώντας τους δείκτες του.
