Ποια είναι η διαφορά μεταξύ πίνακα και λίστας;

Ο πίνακας έχει σταθερό μέγεθος, που καθορίζεται κατά τη δημιουργία του. Η λίστα αλλάζει δυναμικά το μέγεθός της κατά την προσθήκη ή διαγραφή στοιχείων.

Η πρόσβαση σε στοιχεία πίνακα γίνεται με δείκτη σε χρόνο O(1). Η πρόσβαση σε στοιχεία λίστας μπορεί να διαφέρει, π.χ., μια απλή συνδεδεμένη λίστα έχει πρόσβαση με δείκτη σε O(n), ενώ το ArrayList κατά μέσο όρο σε O(1).

Σε έναν πίνακα, τα στοιχεία αποθηκεύονται σε συνεχόμενες περιοχές μνήμης, κάτι που εξασφαλίζει καλύτερη απόδοση cache. Στη λίστα, τα στοιχεία μπορεί να είναι διασκορπισμένα στη μνήμη, συνδεδεμένα με δείκτες.

Οι λειτουργίες εισαγωγής και διαγραφής στο μέσο του πίνακα απαιτούν μετατόπιση όλων των επόμενων στοιχείων, κάτι που μπορεί να είναι δαπανηρό (O(n)). Στις λίστες, αυτές οι λειτουργίες μπορεί να είναι πιο αποδοτικές (π.χ., σε συνδεδεμένες λίστες O(1) αν υπάρχει δείκτης στο στοιχείο, αλλιώς O(n) για αναζήτηση), αλλά απαιτούν ενημέρωση των δεικτών.

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

// Παράδειγμα πίνακα
int[] array = new int[5];
array[0] = 10; // Πρόσβαση O(1)

// Παράδειγμα ArrayList (λίστα στη Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Προσθήκη O(1) κατά μέσο όρο
list.get(0); // Πρόσβαση O(1) κατά μέσο όρο

# Παράδειγμα πίνακα (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Σταθερό μέγεθος

# Παράδειγμα λίστας
data_list = [1, 2, 3]
data_list.append(4) # Δυναμικό μέγεθος

data_list[0] # Πρόσβαση O(1)

Σύγκριση:

Χαρακτηριστικό	Πίνακας	Λίστα
Μέγεθος	Σταθερό	Δυναμικό
Πρόσβαση με δείκτη	O(1)	Μεταβλητό (συχνά O(1) ή O(n))
Μνήμη	Συνεχής	Μπορεί να είναι διασκορπισμένη
Εισαγωγή/Διαγραφή	O(n) στο μέσο	Μεταβλητό (μπορεί να είναι O(1))
Τύποι δεδομένων	Πρωταρχικοί και αντικείμενα	Συνήθως αναφορές σε αντικείμενα