Δυναμικός πίνακας
 |
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Στην επιστήμη υπολογιστών, ο Δυναμικός Πίνακας είναι μία δυναμική δομή δεδομένων, η υλοποίηση της οποίας βασίζεται σε πίνακες.
Ένας απλός πίνακας στον προγραμματισμό έχει ένα στατικά ορισμένο μέγεθος και άρα, μία μέγιστη χωρητικότητα. Προκειμένου να διορθωθεί αυτός ο περιορισμός, η βασική ιδέα για την κατασκευή ενός δυναμικού πίνακα, είναι ότι κατά την εκτέλεση της μεθόδου της εισαγωγής ενός στοιχείου, εάν έχει ήδη καλυφθεί το σύνολο των θέσεων του πίνακα και το νέο στοιχείο δεν χωράει, τότε δημιουργούμε έναν νέο πίνακα με μεγαλύτερο μέγεθος και στη συνέχεια αντιγράφουμε όλα τα στοιχεία από τον παλιό πίνακα στον καινούριο, προσθέτοντας στο τέλος και το νέο στοιχείο. Αποδεικνύεται μαθηματικά ότι εφόσον το μέγεθος του νέου πίνακα είναι ακριβώς διπλάσιο του παλαιού, η πολυπλοκότητα (αναπόσβεστη πολυπλοκότητα - amortized complexity) της μεθόδου εισαγωγής ενός στοιχείου παραμένει Ο(1), όπως δηλαδή και στους απλούς πίνακες.
Στην γλώσσα προγραμματισμού Java η κλάση που υλοποιεί τον δυναμικό πίνακα είναι η ArrayList, ενώ μια παλαιότερη υλοποίησή του είναι η κλάση Vector.
Παραπομπές
[Επεξεργασία | επεξεργασία κώδικα]- Cormen, Thomas H.· Leiserson, Charles E.· Rivest, Ronald L.· Stein, Clifford (2009). Introduction to algorithms (3η έκδοση). Cambridge, Mass.: MIT Press. σελίδες 171. ISBN 0-262-03384-4.