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

Στην Επιστήμη υπολογιστών, μία λίστα ή ακολουθία είναι ένας Αφηρημένος τύπος δεδομένων που υλοποιεί μία διατεταγμένη συλλογή από τιμές, όπου η ίδια τιμή μπορεί να εμφανίζεται περισσότερες από μία φορά. Ένα παράδειγμα λίστας είναι η υπολογιστική αναπαράσταση μιας μαθηματικά ορισμένης, πεπερασμένης ακολουθίας. Κάθε στιγμιότυπο μιας τιμής της λίστας καλείται συνήθως αντικείμενο ή στοιχείο της λίστας; αν η ίδια τιμή εμφανίζεται πολλές φορές, κάθε εμφάνισή της θεωρείται ένα διακριτό αντικείμενο.

Μία δομή απλά συνδεδεμένης λίστας, που περιέχει 3 ακέραια στοιχεία.

Το όνομα λίστα χρησιμοποιείται επίσης για διάφορες δομές δεδομένων που μπορούν να χρησιμοποιηθούν για την υλοποίηση αφηρημένων λιστών και ειδικότερα για συνδεδεμένες λίστες.

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

Πολλές γλώσσες προγραμματισμού παρέχουν υποστήριξη για λίστες ως τύπο δεδομένων, και έχουν ειδική σύνταξη και σημασιολογία αλλά και λειτουργίες πάνω σε αυτές. Μια λίστα συχνά κατασκευάζεται γράφοντας τα αντικείμενά της στη σειρά, χωρισμένα με κόμμα, ερωτηματικό ή κενό, ανάμεσα σε ένα ζευγάρι οριοθετών όπως παρενθέσεις '()', αγκύλες, '[]', άγκιστρα '{}' ή γωνιακές αγκύλες '<>'. Ορισμένες γλώσσες μπορεί να επιτρέπουν τύπους λιστών να δεικτοδοτούνται ή να διαχωρίζονται όπως οι πίνακες. Στις γλώσσες αντικειμενοστρεφούς προγραμματισμού, οι λίστες συνήθως παρέχονται ως στιγμιότυπα υποκλάσεων μιας γενικής κλάσης "λίστας". Οι λίστες συνήθως υλοποιούνται χρησιμοποιώντας πίνακες ή συνδεδεμένες λίστες κάποιου είδους, αλλά διαφορετικές δομές δεδομένων μπορεί να είναι καταλληλότερες για ορισμένες εφαρμογές. Σε κάποια περιβάλλοντα, όπως αυτό της γλώσσας προγραμματισμού Lisp, ο όρος λίστα μπορεί να αναφέρεται ειδικά σε συνδεδεμένη λίστα και όχι σε πίνακα.

Στην Θεωρία τύπων και στον συναρτησιακό προγραμματισμό, οι αφηρημένες λίστες ορίζονται συνήθως επαγωγικά με τέσσερις λειτουργίες: κενό (nil) που δημιουργεί την κενή λίστα, προσάρτηση (cons), που προσθέτει ένα στοιχείο στην αρχή της λίστας, κεφαλή (head), που επιστρέφει το πρώτο στοιχείο της λίστας και ουρά (tail) που επιστρέφει τη λίστα χωρίς το πρώτο στοιχείο. Επισήμως, οι φυσικοί Aριθμοί Πεάνο μπορούν να οριστούν ως αφηρημένες λίστες με στοιχεία του μοναδιαίου τύπου.

Λειτουργίες

Οι υλοποιήσεις της λίστας ως τύπου δεδομένου μπορούν να παρέχουν ορισμένες από τις ακόλουθες λειτουργίες:

• έναν κατασκευαστή για τη δημιουργία της κενής λίστας
• μία λειτουργία που ελέγχει αν η λίστα είναι κενή ή όχι
• μία λειτουργία που εισάγει στην αρχή της λίστας μία οντότητα
• μία λειτουργία για την προσάρτηση μια οντότητας σε μία λίστα
• μία λειτουργία για την εύρεση του πρώτου στοιχείου ("κεφαλή") της λίστας
• μία λειτουργία για την αναφορά σε μία λίστα που αποτελείται από τα στοιχεία της αρχικής λίστας εκτός από την "κεφαλή" της (αυτό συχνά αποκαλείται "ουρά" της λίστας).

Χαρακτηριστικά

Οι λίστες έχουν τις ακόλουθες ιδιότητες:

• Το μέγεθος της λίστας. Υποδεικνύει πόσα στοιχεία περιέχει η λίστα.
• Ισότητα λιστών:
  • Στα μαθηματικά, κάποιες φορές η ισότητα μεταξύ λιστών ορίζεται απλά σε όρους αντικειμενοστρεφούς ταυτότητας: δύο λίστες είναι ίσες μόνο εάν αναφέρονται στο ίδιο αντικείμενο.
  • Στις μοντέρνες γλώσσες προγραμματισμού, η ισότητα μεταξύ λιστών ορίζεται φυσιολογικά σε όρους κατασκευαστικής ισότητας των αντίστοιχων καταχωρήσεων, εκτός της περίπτωσης όπου οι λίστες έχουν τύπους, οπότε και οι τύποι τους θα πρέπει να σχετίζονται.
• Οι λίστες μπορεί να έχουν τύπο. Αυτό συνεπάγεται ότι τα στοιχεία της λίστας πρέπει να είναι τέτοιου τύπου έτσι ώστε να είναι συμβατά με τον τύπο της λίστας. Είναι συχνό φαινόμενο οι λίστες να έχουν τύπο όταν έχουν υλοποιηθεί με χρήση πινάκων.
• Κάθε στοιχείο της λίστας έχει κάποιο δείκτη. Το πρώτο στοιχείο της λίστας συνήθως έχει δείκτη 0 ή 1 (ή κάποιον προκαθορισμένο ακέραιο). Γειτονικά στοιχεία έχουν δείκτες που είναι κατά 1 μεγαλύτεροι από το προηγούμενό τους στοιχείο. Το τελευταίο στοιχείο έχει δείκτη: <αρχικός δείκτης> + <μέγεθος λιστας> − 1.
  • Είναι εφικτό να ανακτήσεις ένα στοιχείο με συγκεκριμένο δείκτη.
  • Είναι εφικτό να διατρέξεις τη λίστα σε αύξουσα σειρά των δεικτών της.
  • Είναι εφικτό να αλλάξεις την τιμή ενός στοιχείου σε μια συγκεκριμένη θέση, χωρίς να επηρεάσεις τα υπόλοιπα στοιχεία της λίστας.
  • Είναι εφικτό να εισάγεις ένα στοιχείο σε μια συγκεκριμένη θέση. Οι δείκτες των μεγαλύτερων στοιχείων αυξάνονται κατά 1.
  • Είναι εφικτό να διαγράψεις ένα στοιχείο σε μια συγκεκριμένη θέση. Οι δείκτες των μεγαλύτερων στοιχείων μειώνονται κατά 1.

Υλοποιήσεις

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

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

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

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

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

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

Εφαρμογές

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

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

Αφηρημένος Ορισμός

Ο αφηρημένος τύπος λίστας $L$ με στοιχεία ενός τύπου $E$ (μία μονομορφική λίστα) ορίζεται με τις εξής συναρτήσεις,

${\text{nil}}:()\to L$

${\text{cons}}:E\times L\to L$

${\text{first}}:L\to E$

${\text{rest}}:L\to L$

και με τα αξιώματα,

${\text{first}}\,({\text{cons}}\,(e,l))=e$

${\text{rest}}\,({\text{cons}}\,(e,l))=l$

Για οποιοδήποτε στοιχείο $e$ και οποιαδήποτε λίστα $l$, συνεπάγεται ότι:

${\text{cons}}\,(e,l)\neq l$

${\text{cons}}\,(e,l)\neq e$

${\text{cons}}\,(e_{1},l_{1})={\text{cons}}\,(e_{2},l_{2})$ αν $e_{1}=e_{2}$ και $l_{1}=l_{2}$

Να τονίσουμε ότι τα ${\text{first}}\,({\text{nil}}\,())$ και ${\text{rest}}\,({\text{nil}}\,())$ δεν ορίζονται.

Αυτά τα αξιώματα είναι ισοδύναμα με αυτά της αφηρημένης στοίβας ως τύπου δεδομένων.

Στην θεωρία τύπων, ο επάνω ορισμός θεωρείται απλούστερα ως επαγωγικός τύπος δεδομένων ορισμένος σε όρους των κατασκευαστών nil και cons. Σε αλγεβρικούς όρους, μπορεί να αναπαρασταθεί ως ο μετασχηματισμός 1 + E × L → L. Τότε τα first και rest λαμβάνονται με ταίριασμα προτύπων στον κατασκευαστή cons και με ξεχωριστή διαχείριση για την περίπτωση του nil.

Η μονάδα των λιστών

Ο τύπος της λίστας σχηματίζει μία μονάδα με τις ακόλουθες συναρτήσεις (χρησιμοποιείται E^* και όχι το L για την αναπαράσταση μονομορφικών λιστών για στοιχεία τύπου E):

${\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}$

${\text{bind}}\colon A^{*}\to (A\to B^{*})\to B^{*}=l\mapsto f\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f)&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

όπου το append ορίζεται ως εξής:

${\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}&{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2})&{\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}$

Εναλλακτικά, η μονάδα μπορεί να οριστεί σε όρους των λειτουργιών return, fmap και join, με τους εξής ορισμούς:

${\text{fmap}}\colon (A\to B)\to (A^{*}\to B^{*})=f\mapsto l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

${\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

Παρατηρούμε ότι οι fmap, join, append και bind είναι καλά-ορισμένες, διότι εφαρμόζονται σε ορίσματα που σταδιακά βρίσκονται όλο και πιο βαθιά (στη στοίβα) σε κάθε αναδρομική κλήση.

Ο τύπος της λίστας είναι μία προσθετική μονάδα, με το κενό (nil) ως μηδενικό της μονάδας και το append ως την αθροιστική μονάδα.

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

Βλέπε επίσης

• Ουρά (δομή δεδομένων)