Και τα δύο αποθηκεύουν ακολουθίες, αλλά έχουν αντίθετα προφίλ κόστους. Ένας πίνακας είναι συνεχόμενη μνήμη με ευρετηρίαση 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 |
| Κοστος μνήμης | χαμηλό | υψηλό (δείκτης ανά κόμβο) |
| Τοπικότητα κρυφής μνήμης | εξαιρετική | κακή |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Στην πράξη οι πίνακες κερδίζουν τις περισσότερες φορές επειδή η τοπικότητα κρυφής μνήμης υπερισχύει των διαφορών Big-O για τυπικά μεγέθη.
Η γνώση και των δύο σας επιτρέπει να δικαιολογήσετε την επιλογή σας σε συνεντεύξεις αντί να υποθέτετε τυφλά — και να εξηγήσετε γιατί η "O(1) εισαγωγή" σπάνια νικά έναν συνεχόμενο πίνακα.
Μια βιβλιοθήκη ερωτήσεων συνέντευξης IT με αναλυτικές απαντήσεις — από Junior έως Senior.
Δωρεά