Και τα δύο αποθηκεύουν ακολουθίες, αλλά έχουν αντίθετα προφίλ κόστους. Ένας πίνακας είναι συνεχόμενη μνήμη με ευρετηρίαση O(1)· μια συνδεδεμένη λίστα είναι δισπειρωμένοι κόμβοι που συνδέονται με δείκτες, με O(1) εισαγωγή/διαγραφή στα άκρα αλλά χωρίς ευρετηρίαση.
Παρά παρά
| Λειτουργία | Πίνακας (δυναμικός) | Συνδεδεμένη λίστα |
|---|---|---|
| Πρόσβαση ανά ευρετήριο | O(1) | O(n) |
| Αναζήτηση | O(n) | O(n) |
| Εισαγωγή/διαγραφή στην κεφαλή | O(n) | O(1) |
| Εισαγωγή/διαγραφή στην ουρά | O(1) amortized | O(1) με tail ptr |
| Εισαγωγή/διαγραφή στη μέση | O(n) | O(n) αναζήτηση + O(1) splice |
| Κοστος μνήμης | χαμηλό | υψηλό (δείκτης ανά κόμβο) |
| Τοπικότητα κρυφής μνήμης | εξαιρετική | κακή |
Εικόνα
text
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Πότε να διαλέξετε ποια
- Πίνακας όταν χρειάζεστε τυχαία πρόσβαση, επαναλαμβάνετε συχνά, ή θέλετε επιδόσεις ευνοϊκές της κρυφής μνήμης (η συνηθισμένη προεπιλογή).
- Συνδεδεμένη λίστα όταν συχνά εισάγετε/διαγράφετε στο μπροστά ή συνδέετε κόμβους στους οποίους ήδη έχετε αναφορά, και σπάνια ευρετηρίαση.
Γιατί έχει σημασία
Στην πράξη οι πίνακες κερδίζουν τις περισσότερες φορές επειδή η τοπικότητα κρυφής μνήμης υπερισχύει των διαφορών Big-O για τυπικά μεγέθη.
Η γνώση και των δύο σας επιτρέπει να δικαιολογήσετε την επιλογή σας σε συνεντεύξεις αντί να υποθέτετε τυφλά — και να εξηγήσετε γιατί η "O(1) εισαγωγή" σπάνια νικά έναν συνεχόμενο πίνακα.