Λίστα (αφηρημένος τύπος δεδομένων)

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

Υλοποιήσεις

Οι λίστες τυπικά υλοποιούνται είτε ως συνδεδεμένες λίστες (απλά ή διπλά) είτε ως πίνακες (μεταβλητού μήκους ή δυναμικούς).
Ο συνήθης τρόπος υλοποίησης λιστών, που προέρχεται από τη γλώσσα προγραμματισμού Lisp, είναι κάθε στοιχείο της λίστας να περιέχει την τιμή του μαζί με έναν δείκτη προς το επόμενο στοιχείο της λίστας. Αυτό έχει ως αποτέλεσμα τη δημιουργία είτε μίας συνδεδεμένης λίστας είτε ενός δέντρου, ανάλογα με το αν η λίστα έχει ή όχι εμφωλευμένες υπολίστες. Κάποιες παλαιότερες υλοποιήσεις της Lisp (όπως αυτή της Symbolics 3600) υποστηρίζουν επίσης "συμπιεσμένες λίστες" (με χρήση της CDR κωδικοποίησης) η οποία είχε μία ειδική εσωτερική αναπαράσταση (μη ορατή στον χρήστη). Τις λίστες μπορούμε να τις διαχειριστούμε με χρήση επαναληπτικών διαδικασιών ή αναδρομής. Ο πρώτος όρος προτιμάται συχνά σε γλώσσες προστακτικού προγραμματισμού, ενώ ο δεύτερος σε γλώσσες συναρτησιακού προγραμματισμού.
Οι λίστες μπορούν να υλοποιηθούν και ως αυτο-ισορροπημένα δέντρα δυαδικής αναζήτησης κρατώντας ζεύγη τιμών-δεικτών και παρέχοντας πρόσβαση ίσου κόστους σε οποιοδήποτε στοιχείο απαιτώντας λογαριθμικό χρόνο στο μέγεθος της λίστας. Όσο δεν γίνονται συχνές ανανεώσεις στη δομή (π.χ. πράξεις εισαγωγής, διαγραφής) δίνεται η ψευδαίσθηση της τυχαίας πρόσβασης, ενώ οι λειτουργίες ανταλλαγής και προσάρτησης στοιχείων γίνονται επίσης σε λογαριθμικό χρόνο.

Υποστήριξη γλωσσών προγραμματισμού

Σε κάποιες υλοποιήσεις γλωσσών δεν υπάρχει η λίστα ως δομή δεδομένων, αλλά προσφέρεται η δυνατότητα χρήσης συσχετιστικών πινάκων ή κάποιου είδους πίνακα που προσομοιώνει τη λειτουργία της. Για παράδειγμα, η γλώσσα προγραμματισμού Lua παρέχει πίνακες. Παρόλο που η Lua αποθηκεύει λίστες που έχουν αριθμητικές τιμές εσωτερικά ως πίνακες, εξακολουθούν να ορίζονται ως πίνακες κατακερματισμού.
Στην Lisp, οι λίστες είναι θεμελιώδεις δομές δεδομένων που μπορούν να αναπαραστήσουν κώδικα και δεδομένα μαζί. Στις περισσότερες διαλέκτους, η λίστα για τους τρεις πρώτους πρώτους αριθμούς μπορεί να γραφεί ως εξής (list 2 3 5). Σε διάφορες διαλέκτους της Lisp, συμπεριλαμβανομένης της γλώσσας προγραμματισμού Scheme, η λίστα είναι μία συλλογή από ζεύγη, αποτελούμενα από μία τιμή και ένα δείκτη προς το επόμενο ζεύγος (ή την κενή τιμή για το τελευταίο ζεύγος), δημιουργώντας ουσιαστικά μία απλά συνδεδεμένη λίστα.

Εφαρμογές

Όπως φαίνεται και από το όνομα, οι λίστες μπορούν να χρησιμοποιηθούν για την αποθήκευση εγγραφών. Τα στοιχεία μιας λίστας μπορούν να ταξινομηθούν στοχεύοντας σε ταχύτερη αναζήτηση (δυαδική αναζήτηση).
Επειδή στον προγραμματισμό οι λίστες είναι περισσότερο κατανοητές από τα σύνολα, ένα πεπερασμένο σύνολο με τη μαθηματική έννοια μπορεί να υλοποιηθεί σαν μια λίστα με επιπρόσθετους περιορισμούς, όπως για παράδειγμα την απαγόρευση διπλών εγγραφών. Εάν η λίστα είναι ταξινομημένη, επιταχύνεται η απόφαση για το εάν ένα δεδομένο αντικείμενο είναι ήδη στη λίστα αλλά καθώς θέλουμε η διάταξη να διατηρείται, απαιτείται περισσότερος χρόνος για την εισαγωγή ενός νέου αντικείμενου σε αυτήν. Σε αποδοτικές υλοποιήσεις τα σύνολα υλοποιούνται με τη χρήση αυτο-ισορροπημένων δέντρων δυαδικής αναζήτησης ή πινάκων κατακερματισμού, παρά με τη χρήση λιστών.