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