8 Κοινές Δομές Δεδομένων που κάθε Προγραμματιστής πρέπει να γνωρίζει

Μια γρήγορη εισαγωγή σε 8 δομές δεδομένων που χρησιμοποιούνται συνήθως

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

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

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

1. Πίνακες

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

Λειτουργίες συστοιχίας

• Τραβέρσα: Περάστε από τα στοιχεία και εκτυπώστε τα.
• Αναζήτηση: Αναζήτηση για ένα στοιχείο στον πίνακα. Μπορείτε να αναζητήσετε το στοιχείο με βάση την τιμή ή το ευρετήριό του
• Ενημέρωση: Ενημερώστε την τιμή ενός υπάρχοντος στοιχείου σε ένα δεδομένο ευρετήριο

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

Εφαρμογές πινάκων

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

2. Συνδεδεμένες λίστες

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

Ας εξετάσουμε τους ακόλουθους όρους σχετικά με τις συνδεδεμένες λίστες. Μπορείτε να πάρετε μια σαφή ιδέα ανατρέχοντας στο Σχήμα 2.

• Τα στοιχεία σε μια συνδεδεμένη λίστα είναι γνωστά ως κόμβοι.
• Κάθε κόμβος περιέχει ένα κλειδί και έναν δείκτη στον διάδοχό του κόμβο, γνωστό ως επόμενο.
• Το χαρακτηριστικό με το όνομα head δείχνει στο πρώτο στοιχείο της συνδεδεμένης λίστας.
• Το τελευταίο στοιχείο της συνδεδεμένης λίστας είναι γνωστό ως ουρά.

Ακολουθούν οι διάφοροι τύποι συνδεδεμένων λιστών που διατίθενται.

• Λίστα μεμονωμένα συνδεδεμένα — Η διέλευση των στοιχείων μπορεί να γίνει μόνο προς την κατεύθυνση προς τα εμπρός.
• Λίστα διπλά συνδεδεμένη — Η διέλευση στοιχείων μπορεί να γίνει τόσο προς τις εμπρός όσο και προς τα πίσω. Οι κόμβοι αποτελούνται από έναν πρόσθετο δείκτη που είναι γνωστός ως προηγούμενο, που δείχνει στον προηγούμενο κόμβο.
• Κυκλικές συνδεδεμένες λίστες — Συνδεδεμένες λίστες όπου ο προηγούμενος δείκτης της κεφαλής δείχνει προς την ουρά και ο επόμενος δείκτης της ουράς δείχνει προς το κεφάλι.

Συνδεδεμένες λειτουργίες λίστας

• Αναζήτηση: Βρείτε το πρώτο στοιχείο με το κλειδί k στη δεδομένη συνδεδεμένη λίστα με μια απλή γραμμική αναζήτηση και επιστρέφει έναν δείκτη σε αυτό το στοιχείο
• Εισαγωγή: Εισαγάγετε ένα κλειδί στη συνδεδεμένη λίστα. Μια εισαγωγή μπορεί να γίνει με 3 διαφορετικούς τρόπους. εισαγωγή στην αρχή της λίστας, εισαγωγή στο τέλος της λίστας και εισαγωγή στη μέση της λίστας.
• Διαγραφή: Καταργεί ένα στοιχείο x από μια δεδομένη συνδεδεμένη λίστα. Δεν μπορείτε να διαγράψετε έναν κόμβο με ένα μόνο βήμα. Μια διαγραφή μπορεί να γίνει με 3 διαφορετικούς τρόπους. διαγραφή από την αρχή της λίστας, διαγραφή από το τέλος της λίστας και διαγραφή από τη μέση της λίστας.

Εφαρμογές συνδεδεμένων λιστών

• Χρησιμοποιείται για διαχείριση πινάκων συμβόλων στο σχεδιασμό μεταγλωττιστή.
• Χρησιμοποιείται για εναλλαγή μεταξύ προγραμμάτων με χρήση Alt + Tab (εφαρμόζεται με χρήση Circular Linked List).

3. Στοίβες

Μια στοίβα είναι μια δομή LIFO (Last In First Out — το στοιχείο που τοποθετήθηκε επιτέλους μπορεί να προσπελαστεί αρχικά) που μπορεί να βρεθεί συνήθως σε πολλές γλώσσες προγραμματισμού. Αυτή η δομή ονομάζεται "στοίβα" επειδή μοιάζει με μια στοίβα του πραγματικού κόσμου - μια στοίβα από πιάτα.

Λειτουργίες στοίβας

Παρακάτω δίνονται οι 2 βασικές λειτουργίες που μπορούν να εκτελεστούν σε μια στοίβα. Ανατρέξτε στην Εικόνα 3 για να κατανοήσετε καλύτερα τις λειτουργίες στοίβας.

• Push: Εισαγάγετε ένα στοιχείο στην κορυφή της στοίβας.
• Pop: Διαγράψτε το ανώτατο στοιχείο και επιστρέψτε το.

Επιπλέον, παρέχονται οι ακόλουθες πρόσθετες λειτουργίες για μια στοίβα προκειμένου να ελεγχθεί η κατάστασή της.

• Peek: Επιστρέψτε το επάνω στοιχείο της στοίβας χωρίς να το διαγράψετε.
• isEmpty: Ελέγξτε εάν η στοίβα είναι άδεια.
• isFull: Ελέγξτε αν η στοίβα είναι γεμάτη.

Εφαρμογές στοίβων

• Χρησιμοποιείται για αξιολόγηση εκφράσεων (π.χ.: αλγόριθμος διαφυγής για ανάλυση και αξιολόγηση μαθηματικών παραστάσεων).
• Χρησιμοποιείται για την υλοποίηση κλήσεων συναρτήσεων στον προγραμματισμό αναδρομής.

4. Ουρές

Μια ουρά είναι μια δομή FIFO (First In First Out — το στοιχείο που τοποθετήθηκε στην αρχή μπορεί να προσπελαστεί αρχικά) που μπορεί να βρεθεί συνήθως σε πολλές γλώσσες προγραμματισμού. Αυτή η δομή ονομάζεται "ουρά" επειδή μοιάζει με μια πραγματική ουρά - άτομα που περιμένουν σε μια ουρά.

Λειτουργίες ουράς

Παρακάτω δίνονται οι 2 βασικές λειτουργίες που μπορούν να εκτελεστούν σε μια ουρά. Ανατρέξτε στο Σχήμα 4 για να κατανοήσετε καλύτερα τις λειτουργίες της ουράς.

• Αναμονή: Εισαγάγετε ένα στοιχείο στο τέλος της ουράς.
• Dequeue: Διαγράψτε το στοιχείο από την αρχή της ουράς.

Εφαρμογές ουρών

• Χρησιμοποιείται για τη διαχείριση νημάτων σε multithreading.
• Χρησιμοποιείται για την εφαρμογή συστημάτων ουράς (π.χ.: ουρές προτεραιότητας).

5. Πίνακες κατακερματισμού

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

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

Λειτουργία κατακερματισμού

Μια ειδική συνάρτηση που ονομάζεται συνάρτηση κατακερματισμού (h) χρησιμοποιείται για να ξεπεραστεί το προαναφερθέν πρόβλημα στην άμεση διευθυνσιοδότηση.

Στην άμεση πρόσβαση, μια τιμή με το κλειδί k αποθηκεύεται στην υποδοχή k. Χρησιμοποιώντας τη συνάρτηση κατακερματισμού, υπολογίζουμε τον δείκτη του πίνακα (slot) στον οποίο πηγαίνει κάθε τιμή. Η τιμή που υπολογίζεται χρησιμοποιώντας τη συνάρτηση κατακερματισμού για ένα δεδομένο κλειδί ονομάζεται τιμή κατακερματισμού που υποδεικνύει το ευρετήριο του πίνακα στον οποίο έχει αντιστοιχιστεί η τιμή.

h(k) = k % m

• h: Συνάρτηση κατακερματισμού
• k: Κλειδί του οποίου πρέπει να καθοριστεί η τιμή κατακερματισμού
• m: Μέγεθος του πίνακα κατακερματισμού (αριθμός διαθέσιμων θέσεων). Μια πρώτη τιμή που δεν είναι κοντά σε μια ακριβή ισχύ του 2 είναι μια καλή επιλογή για m.

Θεωρήστε τη συνάρτηση κατακερματισμού h(k) = k % 20, όπου το μέγεθος του πίνακα κατακερματισμού είναι 20. Δεδομένου ενός συνόλου κλειδιών, θέλουμε να υπολογίσουμε την τιμή κατακερματισμού καθενός για να προσδιορίσουμε το ευρετήριο όπου θα πρέπει να μπει στον πίνακα κατακερματισμού. Σκεφτείτε ότι έχουμε τα ακόλουθα κλειδιά, τον κατακερματισμό και το ευρετήριο του πίνακα κατακερματισμού.

• 1 → 1%20 → 1
• 5 → 5%20 → 5
• 23 → 23%20 → 3
• 63 → 63%20 → 3

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

Εφαρμογές κατακερματισμένων πινάκων

• Χρησιμοποιείται για την υλοποίηση ευρετηρίων βάσεων δεδομένων.
• Χρησιμοποιείται για την υλοποίηση συσχετιστικών πινάκων.
• Χρησιμοποιείται για την υλοποίηση της δομής δεδομένων "set".

6. Δέντρα

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

Διάφοροι τύποι δέντρων έχουν αναπτυχθεί τις τελευταίες δεκαετίες, προκειμένου να ταιριάζουν σε ορισμένες εφαρμογές και να πληρούν ορισμένους περιορισμούς. Μερικά παραδείγματα είναι το δυαδικό δέντρο αναζήτησης, το δέντρο B, το δέντρο με κόκκινο-μαύρο, το δέντρο κύλισης, το δέντρο AVL και το n-ary δέντρο.

Δυαδικά δέντρα αναζήτησης

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

Κάθε κόμβος σε ένα δυαδικό δέντρο αναζήτησης περιλαμβάνει τα ακόλουθα χαρακτηριστικά.

1. κλειδί: Η τιμή που είναι αποθηκευμένη στον κόμβο.
2. αριστερά: Ο δείκτης προς το αριστερό παιδί.
3. δεξιά: Ο δείκτης προς το σωστό παιδί.
4. p: Ο δείκτης προς τον γονικό κόμβο.

Ένα δυαδικό δέντρο αναζήτησης παρουσιάζει μια μοναδική ιδιότητα που το διακρίνει από άλλα δέντρα. Αυτή η ιδιότητα είναι γνωστή ως ιδιότητα δυαδικής αναζήτησης δέντρου.

Έστω x ένας κόμβος σε ένα δυαδικό δέντρο αναζήτησης.

• Εάν το y είναι ένας κόμβος στο αριστερό υποδέντρο του x, τότε y.key ≤ x.key
• Εάν το y είναι ένας κόμβος στο δεξιό υποδέντρο του x, τότε y.key ≥ x.key

Εφαρμογές δέντρων

• Δυαδικά δέντρα: Χρησιμοποιείται για την εφαρμογή αναλυτών εκφράσεων και επιλύσεων εκφράσεων.
• Δυαδικό δέντρο αναζήτησης: χρησιμοποιείται σε πολλές εφαρμογές αναζήτησης όπου τα δεδομένα εισέρχονται και εξέρχονται συνεχώς.
• Heaps: χρησιμοποιείται από την JVM (Java Virtual Machine) για την αποθήκευση αντικειμένων Java.
• Treaps: χρησιμοποιείται στην ασύρματη δικτύωση.

Δείτε τα άρθρα μου παρακάτω σχετικά με 8 χρήσιμες δομές δεδομένων δέντρων και αυτοεξισορροπούμενα δυαδικά δέντρα αναζήτησης.

7. Σωροί

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

Ας δούμε πώς μπορούμε να αναπαραστήσουμε τους σωρούς. Οι σωροί μπορούν να αναπαρασταθούν χρησιμοποιώντας δέντρα καθώς και πίνακες. Τα σχήματα 7 και 8 δείχνουν πώς μπορούμε να αναπαραστήσουμε έναν δυαδικό σωρό χρησιμοποιώντας ένα δυαδικό δέντρο και έναν πίνακα.

Οι σωροί μπορούν να είναι 2 τύπων.

1. Ελάχιστος σωρός — το κλειδί του γονέα είναι μικρότερο ή ίσο με αυτό των παιδιών του. Αυτό ονομάζεται ιδιότητα min-heap. Η ρίζα θα περιέχει την ελάχιστη τιμή του σωρού.
2. Max Heap — το κλειδί του γονέα είναι μεγαλύτερο ή ίσο με εκείνο των παιδιών του. Αυτό ονομάζεται ιδιότητα max-heap. Η ρίζα θα περιέχει τη μέγιστη τιμή του σωρού.

Εφαρμογές σωρών

• Χρησιμοποιείται στον αλγόριθμο heapsort.
• Χρησιμοποιείται για την υλοποίηση ουρών προτεραιότητας καθώς οι τιμές προτεραιότητας μπορούν να ταξινομηθούν σύμφωνα με την ιδιότητα heap όπου ο σωρός μπορεί να υλοποιηθεί χρησιμοποιώντας έναν πίνακα.
• Οι συναρτήσεις ουράς μπορούν να υλοποιηθούν χρησιμοποιώντας σωρούς εντός O(log n) χρόνου.
• Χρησιμοποιείται για την εύρεση της μικρότερης (ή μεγαλύτερης) τιμής kᵗʰ σε έναν δεδομένο πίνακα.

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

8. Γραφήματα

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

Η τάξη ενός γραφήματος είναι ο αριθμός των κορυφών του γραφήματος. Το μέγεθος ενός γραφήματος είναι ο αριθμός των άκρων του γραφήματος.

Δύο κόμβοι λέγεται ότι είναι γειτονικοί εάν συνδέονται μεταξύ τους από το ίδιο άκρο.

Σκηνοθετημένα γραφήματα

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

Λέμε ότι το (u, v) είναι συμπτωματικό από ή φεύγει από την κορυφή u και είναι συμπίπτει με ή εισάγεται στην κορυφή v.

Self-Loops: Ακμές από μια κορυφή προς τον εαυτό της.

Μη κατευθυνόμενα γραφήματα

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

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

Μπορείτε να διαβάσετε περισσότερα για τους αλγόριθμους γραφημάτων από το άρθρο μου 10 αλγόριθμοι γραφημάτων που εξηγούνται οπτικά.

Εφαρμογές γραφημάτων

• Χρησιμοποιείται για την αναπαράσταση δικτύων μέσων κοινωνικής δικτύωσης. Κάθε χρήστης είναι μια κορυφή και όταν οι χρήστες συνδέονται δημιουργούν μια άκρη.
• Χρησιμοποιείται για την αναπαράσταση ιστοσελίδων και συνδέσμων από τις μηχανές αναζήτησης. Οι ιστοσελίδες στο διαδίκτυο συνδέονται μεταξύ τους με υπερσυνδέσμους. Κάθε σελίδα είναι μια κορυφή και η υπερσύνδεση μεταξύ δύο σελίδων είναι μια άκρη. Χρησιμοποιείται για την κατάταξη σελίδων στο Google.
• Χρησιμοποιείται για την αναπαράσταση τοποθεσιών και διαδρομών στο GPS. Οι θέσεις είναι κορυφές και οι διαδρομές που συνδέουν τοποθεσίες είναι ακμές. Χρησιμοποιείται για τον υπολογισμό της συντομότερης διαδρομής μεταξύ δύο τοποθεσιών.

Τελικές σκέψεις

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

Τέλος, θα ήθελα να ευχαριστήσω τον κ. A Alkaff Ahamed για την παροχή πολύτιμων σχολίων και προτάσεων για τη βελτίωση αυτού του άρθρου.

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

Ευχαριστώ πολύ για την ανάγνωση. 😊

Στην υγειά σας! 😃

βιβλιογραφικές αναφορές

[1] Εισαγωγή στους Αλγόριθμους, Τρίτη Έκδοση των Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest και Clifford Stein.

[2] Λίστα δομών δεδομένων από τη Wikipedia (https://en.wikipedia.org/wiki/List_of_data_structures)