Δομές Δεδομένων — Πίνακες, Συνδεδεμένες Λίστες, Δέντρα & Γράφοι

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

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

Να ο πιο σύντομος χρήσιμος κανόνας:

• Πίνακας: καλύτερος για διάταξη με δείκτες.
• Συνδεδεμένη λίστα: καλύτερη για αλυσιδωτές τοπικές συνδέσεις.
• Δέντρο: καλύτερο για ιεραρχία.
• Γράφος: καλύτερος για δίκτυα.

Τι κάνουν πραγματικά οι πίνακες, οι συνδεδεμένες λίστες, τα δέντρα και οι γράφοι

Ένας πίνακας αποθηκεύει στοιχεία σε σταθερή σειρά και σου επιτρέπει να αναφέρεσαι άμεσα σε μια θέση, όπως «στοιχείο $7$». Στη συνηθισμένη συνεχόμενη υλοποίηση, αυτή η άμεση προσπέλαση με δείκτη είναι $O(1)$.

Μια συνδεδεμένη λίστα αποθηκεύει στοιχεία ως κόμβους, όπου κάθε κόμβος δείχνει σε έναν άλλο κόμβο. Μπορείς να μετακινείσαι από κόμβο σε κόμβο, αλλά για να φτάσεις στο $n$οστό στοιχείο συνήθως πρέπει να διασχίσεις προηγούμενους κόμβους, οπότε η πρόσβαση με βάση τη θέση είναι τυπικά $O(n)$.

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

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

Γρήγορη σύγκριση: πότε ταιριάζει κάθε δομή δεδομένων

Structure	Best mental model	Usually good at	Common limitation
Array	A numbered row of items	Direct access by index	Middle insertions and deletions often require shifting items
Linked list	A chain of nodes	Inserting or removing near a known node	Random access is slow
Tree	A branching hierarchy	Representing levels and parent-child relationships	Behavior depends heavily on tree type
Graph	A network of connections	Reachability, paths, and relationships	Algorithms are often more complex

Παράδειγμα εφαρμογής: επιλογή δομών σε μία εφαρμογή πανεπιστημιούπολης

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

Οι καρτέλες των ημερών στην οθόνη προγράμματος είναι φυσικά ένας πίνακας:

$$[\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}]$$

Το βασικό χαρακτηριστικό εδώ είναι η άμεση πρόσβαση με βάση τη θέση. Το «δείξε μου την καρτέλα $3$» έχει νόημα, και η σειρά μετράει.

Ο κατάλογος μαθημάτων είναι φυσικά ένα δέντρο:

$$\text{Department} \rightarrow \text{Course} \rightarrow \text{Section}$$

Κάθε επίπεδο περιέχει το επόμενο επίπεδο. Αυτό είναι ιεραρχία, άρα το δέντρο είναι το πιο καθαρό μοντέλο.

Τα μονοπάτια ανάμεσα στα κτίρια είναι φυσικά ένας γράφος. Ένα κτίριο μπορεί να συνδέεται με αρκετά άλλα, και οι διαδρομές μπορούν να επιστρέφουν σε προηγούμενα σημεία. Αν θέλεις τη συντομότερη διαδρομή από τη βιβλιοθήκη στο εργαστήριο, λύνεις πρόβλημα γράφου, όχι πρόβλημα δέντρου.

Μια συνδεδεμένη λίστα ταιριάζει σε ένα πιο στενό μέρος της ίδιας εφαρμογής: σε μια αλυσίδα από πρόσφατα επισκεφθείσες οθόνες, αν η βασική λειτουργία είναι η μετακίνηση μπροστά ή πίσω ένα βήμα κάθε φορά. Σε αυτή την περίπτωση, κάθε οθόνη χρειάζεται κυρίως συνδέσμους προς κοντινές οθόνες και όχι γρήγορη πρόσβαση στην $20$ή οθόνη.

Το μάθημα είναι ότι το «καλύτερο» εξαρτάται από τη δουλειά. Ένα προϊόν μπορεί να χρησιμοποιεί πολλές δομές δεδομένων, επειδή διαφορετικά μέρη των δεδομένων έχουν διαφορετικές σχέσεις.

Πώς να τα ξεχωρίζεις γρήγορα

Πολλοί μαθητές τα μαθαίνουν πρώτα ως λέξεις του λεξιλογίου. Αυτό κάνει το θέμα να φαίνεται αφηρημένο, αλλά η πρακτική ερώτηση είναι πιο απλή.

Ρώτησε: ποια λειτουργία πρέπει να είναι φθηνή;

Αν θέλεις το «πήγαινε στη θέση $i$» να είναι φθηνό, οι πίνακες είναι ισχυροί. Αν θέλεις το «ακολούθησε την επόμενη σύνδεση» να είναι φθηνό, οι συνδεδεμένες δομές βοηθούν. Αν θέλεις να «κατέβεις σε μια ιεραρχία», ταιριάζουν τα δέντρα. Αν θέλεις να «βρεις αν δύο πράγματα συνδέονται», ταιριάζουν οι γράφοι.

Συνηθισμένα λάθη όταν μαθαίνεις δομές δεδομένων

Υποθέτεις ότι μία δομή είναι πάντα η ταχύτερη

Δεν υπάρχει καθολικός νικητής. Το «γρήγορο» εξαρτάται από το τι κάνεις πιο συχνά και από την υλοποίηση.

Θεωρείς ότι τα δέντρα είναι αυτόματα αποδοτικά

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

Επιλέγεις συνδεδεμένη λίστα μόνο και μόνο επειδή η εισαγωγή ακούγεται φθηνή

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

Χρησιμοποιείς δέντρο ενώ τα δεδομένα είναι στην πραγματικότητα γράφος

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

Μπερδεύεις μια αφηρημένη δομή με ένα χαρακτηριστικό της γλώσσας

Το «array», το «list», το «map» ή το «tree» σε μια γλώσσα προγραμματισμού μπορεί να συνοδεύονται από επιλογές υλοποίησης που επηρεάζουν τη χρήση μνήμης και την ταχύτητα. Η αφηρημένη ιδέα και το συγκεκριμένο container σχετίζονται, αλλά δεν είναι ταυτόσημα.

Πού χρησιμοποιούνται οι πίνακες, οι συνδεδεμένες λίστες, τα δέντρα και οι γράφοι

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

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

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

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

Πώς να επιλέξεις τη σωστή δομή δεδομένων

Ξεκίνα κάνοντας δύο ερωτήσεις:

1. Τι σχέση έχουν τα δεδομένα: ακολουθία, ιεραρχία ή δίκτυο;
2. Ποια λειτουργία μετρά περισσότερο: προσπέλαση με δείκτη, τοπική ενημέρωση, ιεραρχική διάσχιση ή εύρεση διαδρομής;

Αυτές οι δύο απαντήσεις συνήθως περιορίζουν γρήγορα τις επιλογές.

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

Δοκίμασε τη δική σου εκδοχή

Διάλεξε τρία οικεία παραδείγματα, όπως μια playlist, ένα σύστημα φακέλων και έναν χάρτη συγκοινωνιών. Αναγνώρισε αν το καθένα είναι κυρίως ακολουθία, ιεραρχία ή δίκτυο και μετά διάλεξε τη δομή που κάνει εύκολη τη βασική λειτουργία. Αν θέλεις άλλη μία περίπτωση για να δοκιμαστείς, το GPAI Solver μπορεί να δημιουργήσει παρόμοια παραδείγματα ταξινόμησης.