Εισαγωγή

Η Λίστα είναι η τέταρτη κατά σειρά δομή δεδομένων και είναι δυναμική δηλ μπορύμε να αυξομοιώσουμε το πλήθος των κόμβων της.

Τι είναι η Συνδεδεμένη Λίστα; 

Μία (απλά) συνδεδεμένη λίστα (linked list) είναι ένα σύνολο κόμβων διατεταγμένων γραμμικά (ο ένας μετά τον άλλο). Κάθε κόμβος περιέχει εκτός από τα δεδομένα του και έναν δείκτη που δείχνει προς τον επόμενο κόμβο.
Ο δείκτης του τελευταίου κόμβου δε δείχνει σε κάποιον κόμβο (δείκτης στο κενό). Για να το δηλώσουμε αυτό λέμε ότι το πεδίο δείκτη του τελευταίου κόμβου έχει την τιμή NULL. Για να προσπελάσουμε τους κόμβους της λίστας χρειάζεται να γνωρίζουμε τη διεύθυνση (θέση στη μνήμη) του πρώτου κόμβου της λίστας. Η διεύθυνση αυτή αποθηκεύεται σε μία ειδική μεταβλητή που την ονομάζουμε συνήθως Κεφαλή (Head).

Διπλά Συνδεδεμένη Λίστα

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

Πλεονεκτήματα/Μειονεκτήματα των λιστών έναντι των πινάκων

Πλεονεκτήματα

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

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

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

Βασικές πράξεις των συνδεδεμένων λιστών

Οι βασικές πράξεις των συνδεδεμένων λιστών είναι οι παρακάτω:
• Εισαγωγή κόμβου στη λίστα (εισαγωγή κόμβου στην αρχή, στο τέλος της λίστας ή ενδιάμεσα).
• Διαγραφή κόμβου από τη λίστα (διαγραφή από την αρχή, το τέλος της λίστας ή ενδιάμεσα).
• Έλεγχος για το αν η λίστα είναι κενή.
• Αναζήτηση κόμβου για την εύρεση συγκεκριμένου στοιχείου.
• Διάσχιση της λίστας και προσπέλαση των στοιχείων της (π.χ. εκτύπωση των δεδομένων που περιέχονται σε όλους τους κόμβους της λίστας).

Ερωτήσεις ανάπτυξης απο Πανελλαδικές εξετάσεις

  1. Δίδεται η λίστα:

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

    β. Να περιγράψετε τη διαδικασία για τη διαγραφή του κόμβου με δεδομένα Κ από την αρχική λίστα. (2016-A2)

  2. Δίνεται μια λίστα η οποία αποτελείται από 5 κόμβους. Το πρώτο πεδίο του κάθε κόμβου είναι ένα γράμμα και το δεύτερο πεδίο είναι η διεύθυνση του επόμενου κόμβου, όπως φαίνεται στο παρακάτω διάγραμμα, που σχηματίζει τη λέξη ΔΕΚΤΗ:

    Η λίστα αυτή απεικονίζεται στη μνήμη με τη μορφή που φαίνεται στο παρακάτω σχήμα.

    Στον τελευταίο κόμβο, το δεύτερο πεδίο έχει την τιμή 0, η οποία σηματοδοτεί το τέλος της λίστας. ΑΡΧΗ

    α. Να σχεδιάσετε στο τετράδιό σας την απεικόνιση της μνήμης μετά από τη διαγραφή του κατάλληλου κόμβου από την αρχική λίστα, ώστε να σχηματίζεται η λέξη ΔΕΤΗ.

    β. Να σχεδιάσετε στο τετράδιό σας την απεικόνιση της μνήμης μετά από την εισαγωγή, στην αρχική λίστα, του κόμβου με πρώτο πεδίο το γράμμα Α στη θέση 21, ώστε να σχηματίσει η λέξη ΔΕΚΑΤΗ.  (E2016-B1)

  3. χ
  4. χ
  5. χ
  6. χ
  7. χ
  8. χ