Λίστα (αφηρημένος τύπος δεδομένων)
αφηρημένος τύπος δεδομένων / From Wikipedia, the free encyclopedia
Στην Επιστήμη υπολογιστών, μία λίστα ή ακολουθία είναι ένας Αφηρημένος τύπος δεδομένων που υλοποιεί μία διατεταγμένη συλλογή από τιμές, όπου η ίδια τιμή μπορεί να εμφανίζεται περισσότερες από μία φορά. Ένα παράδειγμα λίστας είναι η υπολογιστική αναπαράσταση μιας μαθηματικά ορισμένης, πεπερασμένης ακολουθίας. Κάθε στιγμιότυπο μιας τιμής της λίστας καλείται συνήθως αντικείμενο ή στοιχείο της λίστας; αν η ίδια τιμή εμφανίζεται πολλές φορές, κάθε εμφάνισή της θεωρείται ένα διακριτό αντικείμενο.
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Το όνομα λίστα χρησιμοποιείται επίσης για διάφορες δομές δεδομένων που μπορούν να χρησιμοποιηθούν για την υλοποίηση αφηρημένων λιστών και ειδικότερα για συνδεδεμένες λίστες.
Οι αποκαλούμενες στατικές λίστες δεδομένων επιτρέπουν μόνο τον έλεγχο και ενημέρωση των τιμών της. Μία λίστα που μπορεί να μεταβληθεί ή αλλιώς δυναμική λίστα μπορεί να επιτρέπει την εισαγωγή, αντικατάσταση ή εξαγωγή των αντικειμένων της.
Πολλές γλώσσες προγραμματισμού παρέχουν υποστήριξη για λίστες ως τύπο δεδομένων, και έχουν ειδική σύνταξη και σημασιολογία αλλά και λειτουργίες πάνω σε αυτές. Μια λίστα συχνά κατασκευάζεται γράφοντας τα αντικείμενά της στη σειρά, χωρισμένα με κόμμα, ερωτηματικό ή κενό, ανάμεσα σε ένα ζευγάρι οριοθετών όπως παρενθέσεις '()', αγκύλες, '[]', άγκιστρα '{}' ή γωνιακές αγκύλες '<>'. Ορισμένες γλώσσες μπορεί να επιτρέπουν τύπους λιστών να δεικτοδοτούνται ή να διαχωρίζονται όπως οι πίνακες. Στις γλώσσες αντικειμενοστρεφούς προγραμματισμού, οι λίστες συνήθως παρέχονται ως στιγμιότυπα υποκλάσεων μιας γενικής κλάσης "λίστας". Οι λίστες συνήθως υλοποιούνται χρησιμοποιώντας πίνακες ή συνδεδεμένες λίστες κάποιου είδους, αλλά διαφορετικές δομές δεδομένων μπορεί να είναι καταλληλότερες για ορισμένες εφαρμογές. Σε κάποια περιβάλλοντα, όπως αυτό της γλώσσας προγραμματισμού Lisp, ο όρος λίστα μπορεί να αναφέρεται ειδικά σε συνδεδεμένη λίστα και όχι σε πίνακα.
Στην Θεωρία τύπων και στον συναρτησιακό προγραμματισμό, οι αφηρημένες λίστες ορίζονται συνήθως επαγωγικά με τέσσερις λειτουργίες: κενό (nil) που δημιουργεί την κενή λίστα, προσάρτηση (cons), που προσθέτει ένα στοιχείο στην αρχή της λίστας, κεφαλή (head), που επιστρέφει το πρώτο στοιχείο της λίστας και ουρά (tail) που επιστρέφει τη λίστα χωρίς το πρώτο στοιχείο. Επισήμως, οι φυσικοί Aριθμοί Πεάνο μπορούν να οριστούν ως αφηρημένες λίστες με στοιχεία του μοναδιαίου τύπου.