Παρατηρείστε τα σχήματα των απλών και διπλών συνδεδεμένων λιστών. Μπορείτε να εντοπίσετε τις διαφορές τους; Σχεδιάστε στη συνέχεια μία διπλά συνδεδεμένη λίστα που θα αποτυπώνει την οδική μετάβαση μεταξύ Αθηνών και Ιωαννίνων μέσω της νέας Ιονίας οδού.
Σκέψη / Μεθοδολογία: Η βασική διαφορά απλής/διπλής λίστας είναι το πλήθος δεικτών ανά κόμβο (1 vs 2) και η δυνατότητα αμφίδρομης διάσχισης. Για τη σχεδίαση, επιλέγουμε ενδιάμεσους σταθμούς της Ιονίας οδού μεταξύ Αθήνας και Ιωαννίνων.
Απάντηση: Διαφορά: στην απλά συνδεδεμένη λίστα κάθε κόμβος έχει ΕΝΑΝ δείκτη (προς τον επόμενο) και η διάσχιση γίνεται μόνο προς μία κατεύθυνση, ξεκινώντας πάντα από την Κεφαλή. Στη διπλά συνδεδεμένη λίστα κάθε κόμβος έχει ΔΥΟ δείκτες (προς τον επόμενο ΚΑΙ προς τον προηγούμενο), οπότε η διάσχιση μπορεί να ξεκινήσει από οποιονδήποτε κόμβο και να προχωρήσει και προς τις δύο κατευθύνσεις.
Ενδεικτική διπλά συνδεδεμένη λίστα της διαδρομής: Κεφαλή/Ουρά ⇄ [Αθήνα] ⇄ [Αντίρριο] ⇄ [Αγρίνιο] ⇄ [Ιωάννινα], όπου κάθε κόμβος συνδέεται με τον διπλανό του και προς τις δύο κατευθύνσεις (όπως στο παράδειγμα των σταθμών του μετρό), με τον πρώτο κόμβο (Αθήνα) να μην έχει προηγούμενο και τον τελευταίο (Ιωάννινα) να μην έχει επόμενο.
Πρόσεξε:
Εντοπίστε τις διαφορές στην προσπέλαση όσον αφορά τη λίστα, τη στοίβα και την ουρά. Για την απάντησή σας σκεφθείτε αν η εισαγωγή ενός στοιχείου σε μία στοίβα μπορεί να γίνει σε οποιαδήποτε θέση της.
Σκέψη / Μεθοδολογία: Συγκρίνουμε τους περιορισμούς πρόσβασης των τριών δομών: η στοίβα/ουρά επιτρέπουν πρόσβαση ΜΟΝΟ σε συγκεκριμένη/ες θέση/εις (κορυφή, ή front/rear), ενώ η λίστα (χωρίς αυτόν τον περιορισμό) επιτρέπει εισαγωγή/διαγραφή οπουδήποτε, αν και πάντα με σειριακή διάσχιση.
Απάντηση: Στη στοίβα η πρόσβαση περιορίζεται αυστηρά στην κορυφή (top) — η εισαγωγή ενός στοιχείου ΔΕΝ μπορεί να γίνει σε οποιαδήποτε θέση της, παρά μόνο στην κορυφή. Στην ουρά η πρόσβαση περιορίζεται σε δύο συγκεκριμένες θέσεις: εισαγωγή μόνο στο rear, εξαγωγή μόνο στο front. Στη λίστα, αντίθετα, δεν υπάρχει τέτοιος αυστηρός περιορισμός θέσης — μπορούμε να εισάγουμε ή να διαγράψουμε έναν κόμβο σε ΟΠΟΙΑΔΗΠΟΤΕ θέση (αρχή, τέλος, ή ενδιάμεσα), αρκεί πρώτα να φτάσουμε εκεί ακολουθώντας διαδοχικά τους δείκτες από την Κεφαλή (σειριακή, όχι τυχαία, προσπέλαση).
Πρόσεξε:
