(Α) Ερωτήσεις Σ/Λ
- Λάθος
- Σωστό
- Λάθος
- Λάθος
- Σωστό
- Λάθος
- Λάθος
- Σωστό
- Σωστό
- Λάθος
- Λάθος
(Β) Ερωτήσεις Συμπλήρωσης Κενών
- συνδεδεμένη, απομακρυσμένες, συνδέσμους
- Δεδομένα(data)
- Δείκτης(pointer), μνήμη
- λίστα, δυναμική
- Οι, συνδεδεμένες, λίστες, τους, πίνακες
(Γ) Ερωτήσεις Αντιστοίχησης
(1) α, β, γ, δ, ζ
(2) α, γ, ε
(Δ) Ερωτήσεις Ανάπτυξης
1 ) Απλά συνδεδεμένη λίστα (linked list) είναι ένα σύνολο κόμβων διατεταγμένων γραμμικά (ο ένας μετά τον άλλο). Κάθε κόμβος περιέχει εκτός από τα δεδομένα του και έναν δείκτη που δείχνει προς τον επόμενο κόμβο. Ο δείκτης του τελευταίου κόμβου δε δείχνει σε κάποιον κόμβο αλλά δείχνει στο κενό. Για να το δηλώσουμε αυτό λέμε ότι το πεδίο δείκτη του τελευταίου κόμβου έχει την τιμή NULL.
Για να προσπελάσουμε τους κόμβους της λίστας χρειάζεται να γνωρίζουμε τη διεύθυνση (θέση στη μνήμη) του πρώτου κόμβου της λίστας. Η διεύθυνση αυτή αποθηκεύεται σε μία ειδική μεταβλητή – δείκτη που την ονομάζουμε συνήθως Κεφαλή (Head).
2) Διαφορές μεταξύ Λιστών και Πινάκων
- O πίνακας θεωρείται μια δομή τυχαίας προσπέλασης, σε αντίθεση με μια λίστα που είναι δομή ακολουθιακής ή σειριακής προσπέλασης. Δηλαδή για να φθάσουμε σε έναν κόμβο μιας λίστας πρέπει να περάσουμε από όλους τους προηγούμενους ξεκινώντας από τον πρώτο.
- O πίνακας έχει σταθερό μέγεθος, το οποίο δηλώνεται εξαρχής στο στάδιο της μεταγλώττισης. Αυτό γίνεται διότι ο πίνακας είναι στατική δομή δεδομένων σε αντίθεση με τη λίστα που είναι δυναμική δομή και το μέγεθός της μπορεί να μεταβάλλεται.
- Oι κόμβοι της λίστας αποθηκεύονται σε μη συνεχόμενες θέσεις μνήμης σε αντιδιαστολή με τους πίνακες, όπου τα στοιχεία αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.
3) Πλεονεκτήματα λιστών
- Το δυναμικό τους μέγεθος
- η ευκολία εισαγωγής και διαγραφής από οποιοδήποτε μέρος της λίστας
- η μη αναγκαιότητα δήλωσης του μεγέθους τους.
4) Μειονεκτήματα λιστών
- Δεν επιτρέπουν την τυχαία πρόσβαση στη λίστα. Είναι αδύνατο να φτάσεις στον n-οστό κόμβο μιας απλά συνδεδεμένης λίστας χωρίς πρώτα να περάσεις από όλους τους προηγούμενους κόμβους διαδοχικά ξεκινώντας από τον πρώτο. Στην διπλά συνδεδεμένη λίστα μπορείς να ξεκινήσεις και από τον τελευταίο κόμβο. Επομένως δεν μπορούμε να πραγματοποιήσουμε με αποτελεσματικό τρόπο δυαδική αναζήτηση σε συνδεδεμένες λίστες.
- Οι συνδεδεμένες λίστες επιβαρύνουν την μνήμη περισσότερο από τους πίνακες. Οι κόμβοι της λίστας είναι δυναμικά κατανεμημένοι στην μνήμη και για κάθε κόμβο στη λίστα πρέπει, επιπλέον, να αποθηκεύσει έναν πρόσθετο δείκτη που θα δείχνει στον επόμενο κόμβο. Στην περίπτωση δε των διπλά συνδεδεμένων λιστών χρειαζόμαστε επιπλέον έναν δεύτερο δείκτη που θα δείχνει στον προηγούμενο κόμβο.
5) Βασικές πράξεις συνδεδεμένων λιστών
- Εισαγωγή κόμβου στη λίστα (στην αρχή, στο τέλος της ή και ενδιάμεσα).
- Διαγραφή κόμβου από τη λίστα (από την αρχή, το τέλος ή ενδιάμεσα).
- Έλεγχος για το αν η λίστα είναι κενή.
- Αναζήτηση κόμβου για την εύρεση συγκεκριμένου στοιχείου.
- Διάσχιση της λίστας και προσπέλαση των στοιχείων της (π.χ. εκτύπωση των δεδομένων που περιέχονται σε όλους τους κόμβους).