Πώς είναι δομημένοι οι πίνακες στον προγραμματισμό;

Οι πίνακες είναι διατεταγμένες συλλογές στοιχείων του ίδιου τύπου, αποθηκευμένα σε γειτονικά (διαδοχικά) κυττάρα μνήμης.

Βασικά χαρακτηριστικά:

• Δεικτοδότηση: Η πρόσβαση στα στοιχεία γίνεται μέσω δείκτη που ξεκινά από το 0. Ο δείκτης δείχνει την απόκλιση από την αρχή του πίνακα.
• Μέγεθος: Το μέγεθος του πίνακα (αριθμός στοιχείων) είναι σταθερό κατά τη δημιουργία του σε γλώσσες με στατικό τύπο ή μπορεί να αλλάξει δυναμικά σε γλώσσες με δυναμικό τύπο (π.χ., Swift Array).
• Τύπος δεδομένων: Όλα τα στοιχεία του πίνακα πρέπει να έχουν τον ίδιο τύπο δεδομένων.
• Συγκεκριμένη διαδοχή: Η αποθήκευση των στοιχείων σε γειτονικά κυττάρα μνήμης εξασφαλίζει γρήγορη πρόσβαση σε οποιοδήποτε στοιχείο μέσω του δείκτη του.

Λειτουργίες:

• Πρόσβαση μέσω δείκτη: O(1) - σταθερός χρόνος.
• Προσθήκη/διαγραφή στο τέλος: O(1) κατά μέσο όρο για δυναμικούς πίνακες (Swift Array).
• Προσθήκη/διαγραφή στην αρχή ή στη μέση: O(n) - γραμμικός χρόνος, καθώς μπορεί να χρειαστεί μετατόπιση των στοιχείων.

Παράδειγμα σε Swift:

// Δημιουργία πίνακα συμβολοσειρών
var names: [String] = ["Alice", "Bob", "Charlie"]

// Πρόσβαση σε στοιχείο μέσω δείκτη
let first_name = names[0] // "Alice"

// Προσθήκη στοιχείου
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Διαγραφή στοιχείου
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Επανάληψη στον πίνακα
for name in names {
    print(name)
}

Εσωτερική δομή (για δυναμικούς πίνακες τύπου Swift Array):

Οι δυναμικοί πίνακες υλοποιούνται συνήθως πάνω σε στατικά εκχωρημένο buffer μνήμης. Όταν η χωρητικότητα του buffer φτάσει, εκχωρείται ένας νέος μεγαλύτερος buffer και αντιγράφονται τα παλιά στοιχεία (reallocation). Αυτό εξασφαλίζει μια αποσβεσμένη πολυπλοκότητα O(1) για την προσθήκη στο τέλος.