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

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

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

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

Τα στοιχεία μέσα στη συνδεδεμένη λίστα αποθηκεύονται σε μεμονωμένους κόμβους που συνδέονται (συνδεδεμένοι) χρησιμοποιώντας δείκτες. Μπορείτε να σκεφτείτε μια συνδεδεμένη λίστα ως μια αλυσίδα κόμβων που συνδέονται μεταξύ τους μέσω διαφορετικών δεικτών.

Σχετίζεται με: Εισαγωγή στη χρήση συνδεδεμένων λιστών στην Java

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

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

Οι ερωτήσεις συνέντευξης που σχετίζονται με συνδεδεμένες λίστες συνήθως περιστρέφονται γύρω από την εισαγωγή, την αναζήτηση ή τη διαγραφή ενός συγκεκριμένου στοιχείου. Η εισαγωγή σε μια συνδεδεμένη λίστα απαιτεί χρόνο O(1), αλλά η διαγραφή και η αναζήτηση μπορεί να χρειαστούν χρόνο O(n) στη χειρότερη περίπτωση. Άρα οι συνδεδεμένες λίστες δεν είναι ιδανικές.

2. Δυαδικό δέντρο

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

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

Σχετίζεται με: Ένας οδηγός για αρχάριους για δυαδικά δέντρα

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

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

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

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

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

Κάθε πίνακας κατακερματισμού αποθηκεύει στοιχεία δεδομένων σε ένα ζεύγος τιμής-δείκτη.

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

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

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

4. Στοίβες

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

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

Οι στοίβες έχουν δύο κύριες λειτουργίες — push και pop. Το Push χρησιμοποιείται για την εισαγωγή ενός στοιχείου στη στοίβα και το pop αφαιρεί το ανώτατο στοιχείο από τη στοίβα.

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

5. Ουρές

Οι ουρές είναι παρόμοιες με τις στοίβες, αλλά λειτουργούν με τρόπο FIFO (First In First Out), που σημαίνει ότι μπορείτε να έχετε πρόσβαση στα στοιχεία που εισαγάγατε νωρίτερα. Η δομή δεδομένων ουράς μπορεί να απεικονιστεί ως οποιαδήποτε ουρά πραγματικής ζωής, όπου οι άνθρωποι τοποθετούνται με βάση τη σειρά άφιξής τους.

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

Σχετίζεται με: Ένας οδηγός για αρχάριους για την κατανόηση των ουρών και των ουρών προτεραιότητας

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

6. Πλήθος

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

Ομοίως, ο ριζικός κόμβος ενός Max Heap περιέχει τη μέγιστη τιμή κλειδιού του σωρού. πρέπει να διατηρήσετε την ιδιότητα min/max heap σε όλο το σωρό.

Σχετίζεται με: Heaps vs. Στοίβες: Τι τους ξεχωρίζει;

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

Μάθετε Δομές Δεδομένων

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

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

7 αλγόριθμοι που πρέπει να γνωρίζει κάθε προγραμματιστής

Αυτοί οι αλγόριθμοι είναι απαραίτητοι για τη ροή εργασίας κάθε προγραμματιστή.

Διαβάστε Επόμενο

Σχετικά με τον Συγγραφέα