Διπλά συνδεδεμένες λίστες και τρόπος εφαρμογής τους στην Python 3

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

Δεν είναι έγκυρη αλυσίδα! Αυτό θα σπάσει μια συνδεδεμένη λίστα!

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

Για πληροφορίες σχετικά με λίστες που συνδέονται απλά, επισκεφτείτε το άρθρο του συμμαθητή μου:

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

Πώς λοιπόν εφαρμόζει μια διπλά συνδεδεμένη λίστα; Αυτό είναι το πώς στην Python 3

Απλά προσθέστε ένα .prev στην κλάση σας κόμβου. Τώρα είστε έτοιμοι να ξεκινήσετε την εφαρμογή!

Πλεονεκτήματα - Με τον κώδικα Python 3!

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

Μειονεκτήματα

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

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

Αλλά τι θα χρησιμοποιηθεί για αυτό;

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

Πηγή: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

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

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

Τώρα σκεφτείτε το λογισμικό επεξεργασίας κειμένου ή το πρόγραμμα επεξεργασίας φωτογραφιών της επιλογής σας. Κάθε φορά που κάνετε λάθος, μπορείτε να πατήσετε CTRL (CMD για Mac) + Z για να αναιρέσετε την τελευταία ενέργεια. Ομοίως, είστε σε θέση να επαναλάβετε αυτό που έχετε αναιρέσει με το CTRL (CMD για Mac) + Y. Τώρα, γιατί αυτός ο ήχος είναι εξοικειωμένος; Θα μπορούσε επίσης να εφαρμοστεί με μια διπλά συνδεδεμένη λίστα! Ο προηγούμενος δείκτης επισημαίνει τις ενέργειες που έγιναν, ενώ ταυτόχρονα είναι σε θέση να επαναλάβει τις ενέργειες εάν ανακαλέσετε πάρα πολύ.

Πηγή: https://gfycat.com/brilliantbeautifuldassieΠηγή: https://www.solitairecardgames.com/how-to-play-solitaire

Μια λιγότερο προφανής εφαρμογή που σκέφτηκα ήταν στο παιχνίδι Solitaire. Στο πλάι υπάρχει μια εικόνα των ορολογιών της Πασιέντζας για να συμβάλει στην απεικόνιση του σημείου μου.

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

Για μια πιο ζωντανή συζήτηση των χρήσεων σε διπλά συνδεδεμένες λίστες θα πρότεινα να ρίξω μια ματιά σε αυτή τη συζήτηση για stackoverflow:

Έτσι, την επόμενη φορά που εφαρμόζετε έναν συνδεδεμένο κατάλογο, γιατί να μην δοκιμάσετε ένα διπλά συνδεδεμένο; Δεν είναι πολύ περισσότερος κώδικας στην κορυφή μιας συνδεδεμένης λίστας και υπάρχουν βαθιά οφέλη!

Επιπρόσθετοι πόροι

Ένας πλήρης σύνδεσμος με την εφαρμογή Python 3 μιας διπλά συνδεδεμένης λίστας μπορεί να βρεθεί στο repos Github μου.

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

https://www.geeksforgeeks.org/doubly-linked-list/

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.youtube.com/watch?v=JdQeNxWCguQ