Ένας πίνακας (array) είναι ένα συνεχόμενο μπλοκ μνήμης που περιέχει στοιχεία του ίδιου τύπου, ευρετηριασμένα από το 0. Επειδή τα στοιχεία βρίσκονται το ένα δίπλα στο άλλο, η διεύθυνση του στοιχείου i υπολογίζεται απευθείας ως base + i * elementSize, παρέχοντας .
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| Λειτουργία | Χρόνος |
|---|---|
| Πρόσβαση κατά δείκτη | O(1) |
| Αναζήτηση (ταξινόμητη) | O(n) |
| Προσθήκη (δυναμική) | O(1)摊销 |
| Εισαγωγή/διαγραφή στην αρχή/μέση | O(n) |
Οι πίνακες είναι το θεμέλιο κάτω από τις περισσότερες άλλες δομές — οι συμβολοσειρές, οι πίνακες κατακερματισμού, οι σωροί και οι δυναμικές λίστες είναι όλες χτισμένες πάνω τους.
Η τοπικότητα της cache τους συχνά κάνει ένα "πιο αργό" Big-O πίνακα να νικά μια "πιο γρήγορη" δομή βασισμένη σε δείκτες σε πραγματικές συγκρίσεις.