Τρεις ακόμα πολύ σπουδαίες δομές δεδομένων είναι οι λίστες, τα δένδρα και οι γράφοι. Οι δομές αυτές ανήκουν στην κατηγορία των δυναμικών δομών δεδομένων.
🔑 Βασική Διαφορά: Στις δυναμικές δομές, οι κόμβοι δεν είναι απαραίτητο να κατέχουν συνεχόμενες θέσεις μνήμης και συνδέονται μεταξύ τους με τη βοήθεια των δεικτών.
📌 3.18 Τι είναι οι δείκτες στις δυναμικές δομές δεδομένων;
Ο δείκτης (pointer) είναι ένας ιδιαίτερος τύπος μεταβλητής που προσφέρεται από τις περισσότερες σύγχρονες γλώσσες προγραμματισμού.
Ο δείκτης δεν λαμβάνει αριθμητικές τιμές όπως ακέραιες, πραγματικές κ.α., αλλά οι τιμές του είναι διευθύνσεις στην κύρια μνήμη.
Συνήθως ο δείκτης είναι ένα πεδίο κάθε κόμβου της δομής, ενώ το πεδίο Δεδομένα μπορεί να περιέχει μία ή περισσότερες αλφαριθμητικές ή αριθμητικές τιμές.
⚠️ Σημείωση: Οι όροι index και pointer αποδίδονται στα ελληνικά ως δείκτης. Και οι δύο παραπέμπουν σε θέσεις (θέση πίνακα ο πρώτος και θέση μνήμης ο δεύτερος).
📌 3.19 Περιγράψτε τη Δομή της (Απλά) Συνδεδεμένης Λίστας
Μια (απλά) συνδεδεμένη λίστα (linked list) είναι ένα σύνολο κόμβων διατεταγμένων γραμμικά. Κάθε κόμβος περιέχει εκτός από τα δεδομένα του και έναν δείκτη που δείχνει προς τον επόμενο κόμβο.
Κεφαλή (head): Δείκτης που δείχνει στον πρώτο κόμβο
Δείκτης τελευταίου κόμβου: Τιμή NULL (= κενό), φαίνεται με «•»
Δείκτες υπολοίπων κόμβων: Περιέχουν τη διεύθυνση του επόμενου κόμβου
💡 Σημαντικό: Οι κόμβοι μιας λίστας μπορεί να βρίσκονται σε οποιεσδήποτε θέσεις μνήμης (όχι απαραίτητα συνεχόμενες). Η σύνδεση γίνεται μόνο μέσω των δεικτών.
📌 3.20 Περιγράψτε τη λειτουργία της Εισαγωγής και της Διαγραφής σε μια Λίστα
▪️ Εισαγωγή (Insertion)
Ο δείκτης του προηγούμενου κόμβου να δείχνει το νέο κόμβο
Ο δείκτης του νέου κόμβου να δείχνει τον επόμενο κόμβο (να πάρει την τιμή που είχε πριν ο δείκτης του προηγούμενου)
▪️ Διαγραφή (Deletion)
Αλλάζει τιμή ο δείκτης του προηγούμενου κόμβου και δείχνει πλέον τον επόμενο αυτού που διαγράφεται. Ο κόμβος που διαγράφηκε αποτελεί "άχρηστο δεδομένο".
📌 3.21 Τι είναι η Διπλά Συνδεδεμένη Λίστα;
Μια διπλά συνδεδεμένη λίστα επιτρέπει διασχιση και προς τις δύο κατευθύνσεις. Κάθε κόμβος έχει δύο δείκτες:
Ένας που δείχνει τον επόμενο κόμβο
Ένας που δείχνει τον προηγούμενο κόμβο
Έχει δύο δείκτες: κεφαλή (head) → πρώτος κόμβος και ουρά (tail) → τελευταίος κόμβος.
Στον πρώτο κόμβο, ο δείκτης προς τον προηγούμενο είναι NULL. Στον τελευταίο κόμβο, ο δείκτης προς τον επόμενο είναι NULL.
✅ Πλεονέκτημα: Διευκολύνεται η ταξινόμηση και η αναζήτηση. ❌ Μειονέκτημα: Αυξάνεται η πολυπλοκότητα και απαιτείται επιπλέον μνήμη για τον δεύτερο δείκτη.
📌 3.22 Ποιες είναι οι βασικές λειτουργίες στις Λίστες;
Εισαγωγή κόμβου στη λίστα (στην αρχή, στο τέλος ή ενδιάμεσα)
Διαγραφή κόμβου από τη λίστα (από την αρχή, το τέλος ή ενδιάμεσα)
Έλεγχος για το αν η λίστα είναι κενή (head = NULL)
Αναζήτηση κόμβου για την εύρεση συγκεκριμένου στοιχείου
Διάσχιση της λίστας και προσπέλαση των στοιχείων της
📌 3.23 Να αναφέρετε τις διαφορές της Λίστας σε σχέση με τον Πίνακα
Χαρακτηριστικό
Πίνακας
Λίστα
Προσπέλαση
Τυχαία — άμεση πρόσβαση σε οποιοδήποτε στοιχείο
Ακολουθιακή — πρέπει να περάσουμε από όλους τους προηγούμενους
Μέγεθος
Σταθερό, δηλώνεται εξαρχής (στατική δομή)
Δυναμικό, μεταβάλλεται (δυναμική δομή)
Αποθήκευση
Συνεχόμενες θέσεις μνήμης
Μη συνεχόμενες θέσεις μνήμης
📌 3.24 Να αναφέρετε τα πλεονεκτήματα της Λίστας
Το δυναμικό της μέγεθος — δεν χρειάζεται προκαθορισμός μεγέθους
Η ευκολία εισαγωγής και διαγραφής από οποιοδήποτε μέρος της λίστας
Η μη αναγκαιότητα δήλωσης του μεγέθους εξαρχής
📌 3.25 Να αναφέρετε τα μειονεκτήματα της Λίστας
Η τυχαία πρόσβαση δεν επιτρέπεται. Είναι αδύνατο να φτάσουμε στον n-οστό κόμβο χωρίς να περάσουμε από όλους τους προηγούμενους. Δεν μπορούμε να κάνουμε αποτελεσματικά δυαδική αναζήτηση.
Οι συνδεδεμένες λίστες έχουν πολύ μεγαλύτερη επιβάρυνση από τους πίνακες, αφού οι κόμβοι είναι δυναμικά κατανεμημένοι (λιγότερο αποτελεσματικοί στη χρήση της μνήμης) και κάθε κόμβος πρέπει να αποθηκεύσει έναν πρόσθετο δείκτη (ή δύο στη διπλά συνδεδεμένη).
🎮 Διαδραστική Απλά Συνδεδεμένη Λίστα
Πειραματίσου με την προσθήκη και διαγραφή κόμβων. Παρατήρησε πώς οι δείκτες συνδέουν τους κόμβους:
head → NULL
(Κενή λίστα)
💡 Συμβουλή: Κάνε κλικ σε κάθε ερώτηση για να δεις την αναλυτική απάντηση.
1. Ποιες άλλες δομές δεδομένων υπάρχουν εκτός από στοίβα και ουρά;
▼
Τρεις ακόμα πολύ σπουδαίες δομές δεδομένων είναι:
Οι λίστες
Τα δένδρα
Οι γράφοι
Οι δομές αυτές ανήκουν στην κατηγορία των δυναμικών δομών δεδομένων, όπου οι κόμβοι δεν είναι απαραίτητο να κατέχουν συνεχόμενες θέσεις μνήμης και συνδέονται μεταξύ τους με τη βοήθεια των δεικτών.
2. Τι είναι ο δείκτης (pointer) στις δυναμικές δομές δεδομένων;
▼
Ο δείκτης (pointer) είναι ένας ιδιαίτερος τύπος μεταβλητής που προσφέρεται από τις περισσότερες σύγχρονες γλώσσες προγραμματισμού.
Ο δείκτης δεν λαμβάνει αριθμητικές τιμές (ακέραιες, πραγματικές κ.α.)
Οι τιμές του είναι διευθύνσεις στην κύρια μνήμη
Συνήθως είναι ένα πεδίο κάθε κόμβου της δομής
Το πεδίο Δεδομένα περιέχει αλφαριθμητικές ή αριθμητικές τιμές
⚠️ Σημείωση: Οι όροι index και pointer αποδίδονται στα ελληνικά ως δείκτης. Ο πρώτος παραπέμπει σε θέση πίνακα και ο δεύτερος σε θέση μνήμης.
3. Τι είναι η (απλά) συνδεδεμένη λίστα;
▼
Μια (απλά) συνδεδεμένη λίστα (linked list) είναι ένα σύνολο κόμβων διατεταγμένων γραμμικά. Κάθε κόμβος περιέχει:
Τα δεδομένα του
Έναν δείκτη που δείχνει προς τον επόμενο κόμβο
Κεφαλή (head): Δείκτης που δείχνει στον πρώτο κόμβο της λίστας.
Τελευταίος κόμβος: Ο δείκτης του έχει τιμή NULL (κενό), φαίνεται με το σύμβολο «•».
4. Πώς γίνεται η εισαγωγή κόμβου σε μια λίστα;
▼
Για την εισαγωγή (παρεμβολή) ενός νέου κόμβου:
Ο δείκτης του προηγούμενου κόμβου να δείχνει το νέο κόμβο
Ο δείκτης του νέου κόμβου να δείχνει τον επόμενο κόμβο (να πάρει την τιμή που είχε πριν ο δείκτης του προηγούμενου)
Έτσι διατηρείται η λογική σειρά των κόμβων, αν και οι φυσικές θέσεις στη μνήμη μπορεί να είναι τελείως διαφορετικές.
5. Πώς γίνεται η διαγραφή κόμβου από μια λίστα;
▼
Για τη διαγραφή ενός κόμβου:
Ο δείκτης του προηγούμενου κόμβου αλλάζει τιμή και δείχνει πλέον τον επόμενο αυτού που διαγράφεται
Ο κόμβος που διαγράφηκε αποτελεί "άχρηστο δεδομένο" και ο χώρος μνήμης που καταλάμβανε παραχωρείται για άλλη χρήση.
💡 Σημαντικό: Σε αντίθεση με τους πίνακες, στη λίστα δεν χρειάζεται να μετακινήσουμε στοιχεία — απλά αλλάζουμε έναν δείκτη!
6. Τι είναι η διπλά συνδεδεμένη λίστα;
▼
Μια διπλά συνδεδεμένη λίστα είναι μια λίστα όπου κάθε κόμβος έχει δύο δείκτες:
Έναν που δείχνει τον επόμενο κόμβο
Έναν που δείχνει τον προηγούμενο κόμβο
Έχει δύο δείκτες:
κεφαλή (head) → πρώτος κόμβος
ουρά (tail) → τελευταίος κόμβος
Έτσι μπορούμε να διατρέξουμε τη λίστα και προς τις δύο κατευθύνσεις.
Στον πρώτο κόμβο, ο δείκτης προς τον προηγούμενο είναι NULL. Στον τελευταίο κόμβο, ο δείκτης προς τον επόμενο είναι NULL.
✅ Πλεονέκτημα: Διευκολύνεται η ταξινόμηση και η αναζήτηση. ❌ Μειονέκτημα: Αυξάνεται η πολυπλοκότητα και απαιτείται επιπλέον μνήμη για τον δεύτερο δείκτη.
7. Ποιες είναι οι βασικές λειτουργίες στις λίστες;
▼
Εισαγωγή κόμβου στη λίστα (στην αρχή, στο τέλος ή ενδιάμεσα)
Διαγραφή κόμβου από τη λίστα (από την αρχή, το τέλος ή ενδιάμεσα)
Έλεγχος για το αν η λίστα είναι κενή (head = NULL)
Αναζήτηση κόμβου για την εύρεση συγκεκριμένου στοιχείου
Διάσχιση της λίστας και προσπέλαση των στοιχείων της
8. Ποιες οι διαφορές της Λίστας σε σχέση με τον Πίνακα;
▼
Χαρακτηριστικό
Πίνακας
Λίστα
Προσπέλαση
Τυχαία — άμεση πρόσβαση σε οποιοδήποτε στοιχείο
Ακολουθιακή — πρέπει να περάσουμε από όλους τους προηγούμενους
Μέγεθος
Σταθερό, δηλώνεται εξαρχής (στατική δομή)
Δυναμικό, μεταβάλλεται (δυναμική δομή)
Αποθήκευση
Συνεχόμενες θέσεις μνήμης
Μη συνεχόμενες θέσεις μνήμης
9. Ποια είναι τα πλεονεκτήματα της λίστας;
▼
Το δυναμικό της μέγεθος — δεν χρειάζεται προκαθορισμός μεγέθους
Η ευκολία εισαγωγής και διαγραφής από οποιοδήποτε μέρος της λίστας
Η μη αναγκαιότητα δήλωσης του μεγέθους εξαρχής
10. Ποια είναι τα μειονεκτήματα της λίστας;
▼
Η τυχαία πρόσβαση δεν επιτρέπεται. Είναι αδύνατο να φτάσουμε στον n-οστό κόμβο χωρίς να περάσουμε από όλους τους προηγούμενους. Δεν μπορούμε να κάνουμε αποτελεσματικά δυαδική αναζήτηση.
Οι συνδεδεμένες λίστες έχουν μεγαλύτερη επιβάρυνση από τους πίνακες, γιατί:
Οι κόμβοι είναι δυναμικά κατανεμημένοι (λιγότερο αποτελεσματικοί στη χρήση μνήμης)
Κάθε κόμβος πρέπει να αποθηκεύσει έναν πρόσθετο δείκτη (ή δύο στη διπλά συνδεδεμένη)
11. Τι σημαίνει head = NULL;
▼
Όταν head = NULL, η λίστα είναι κενή — δεν περιέχει κανέναν κόμβο.
Αυτός είναι ο τρόπος ελέγχου για το αν μια λίστα είναι κενή.
12. Γιατί δεν μπορούμε να κάνουμε δυαδική αναζήτηση σε λίστα;
▼
Η δυαδική αναζήτηση απαιτεί τυχαία πρόσβαση — δηλαδή τη δυνατότητα να πάμε άμεσα στο μεσαίο στοιχείο.
Στη λίστα, η πρόσβαση είναι ακολουθιακή/σειριακή. Για να φτάσουμε στον n-οστό κόμβο, πρέπει να περάσουμε από όλους τους προηγούμενους ξεκινώντας από τον πρώτο (ή από τον τελευταίο στη διπλά συνδεδεμένη).
Άρα, η δυαδική αναζήτηση σε λίστα δεν είναι αποτελεσματική — θα είχε πολυπλοκότητα O(n) αντί για O(log n).
🎯 Οδηγίες: Επίλεξε μία απάντηση σε κάθε ερώτηση. Θα δεις άμεση ανατροφοδότηση.
1. Ποιες από τις παρακάτω δομές ανήκουν στις δυναμικές δομές δεδομένων;
α) Μόνο οι λίστες
β) Μόνο οι πίνακες
γ) Λίστες, δένδρα και γράφοι
δ) Μόνο οι στοίβες και οι ουρές
2. Ο δείκτης (pointer) παίρνει τιμές που είναι:
α) Ακέραιες
β) Πραγματικές
γ) Διευθύνσεις στην κύρια μνήμη
δ) Αλφαριθμητικές
3. Σε μια απλά συνδεδεμένη λίστα, κάθε κόμβος περιέχει:
α) Μόνο δεδομένα
β) Δεδομένα και δείκτη προς τον επόμενο κόμβο
γ) Μόνο δείκτες
δ) Δεδομένα και δύο δείκτες
4. Ο δείκτης του τελευταίου κόμβου μιας λίστας έχει τιμή:
α) 0
β) NULL
γ) -1
δ) head
5. Ποιος δείκτης δείχνει στον πρώτο κόμβο μιας λίστας;
α) tail
β) head (κεφαλή)
γ) rear
δ) top
6. Για τη διαγραφή κόμβου από λίστα αρκεί να αλλάξει:
α) Ο δείκτης του κόμβου που διαγράφεται
β) Ο δείκτης του προηγούμενου κόμβου
γ) Ο δείκτης head
δ) Τα δεδομένα του κόμβου
7. Σε μια διπλά συνδεδεμένη λίστα, κάθε κόμβος έχει:
α) Έναν δείκτη
β) Δύο δείκτες
γ) Κανέναν δείκτη
δ) Τρεις δείκτες
8. Σε μια διπλά συνδεδεμένη λίστα, ο δείκτης που δείχνει στον τελευταίο κόμβο ονομάζεται:
α) head
β) tail (ουρά)
γ) rear
δ) top
9. Ποιο είναι πλεονέκτημα της λίστας σε σχέση με τον πίνακα;
α) Τυχαία πρόσβαση σε οποιοδήποτε στοιχείο
β) Δυναμικό μέγεθος
γ) Συνεχόμενες θέσεις μνήμης
δ) Δυαδική αναζήτηση
10. Ποιο είναι μειονέκτημα της λίστας σε σχέση με τον πίνακα;
α) Μπορεί να αλλάζει μέγεθος
β) Εύκολη εισαγωγή/διαγραφή
γ) Δεν επιτρέπεται τυχαία πρόσβαση
δ) Δεν χρειάζεται δήλωση μεγέθους
11. Ο πίνακας έχει προσπέλαση:
α) Τυχαία
β) Ακολουθιακή μόνο
γ) Μόνο από την αρχή
δ) Μόνο από το τέλος
12. Η λίστα έχει προσπέλαση:
α) Τυχαία
β) Ακολουθιακή/σειριακή
γ) Μόνο από την αρχή
δ) Μόνο από το τέλος
13. Σε μια διπλά συνδεδεμένη λίστα, στον πρώτο κόμβο ο δείκτης προς τον προηγούμενο είναι:
α) head
β) NULL
γ) tail
δ) 0
14. Ποιο από τα παρακάτω ΔΕΝ είναι βασική λειτουργία σε λίστα;
α) Εισαγωγή κόμβου
β) Διαγραφή κόμβου
γ) Αναζήτηση κόμβου
δ) Ταξινόμηση με QuickSort
15. Γιατί απαιτείται επιπλέον μνήμη σε κάθε κόμβο λίστας;
α) Για τα δεδομένα
β) Για τον/τους δείκτη/δείκτες
γ) Για τον κώδικα
δ) Για το λειτουργικό σύστημα
🏆 Τελικό Σκορ
💪 Προκλήσεις: Προσπάθησε να τις λύσεις μόνος σου πριν δεις την απάντηση!
Άσκηση 1: Αντιστοίχιση
⭐
Να αντιστοιχίσετε κάθε στοιχείο της Στήλης Α με το κατάλληλο της Στήλης Β.
Σε μια απλά συνδεδεμένη λίστα, κάθε κόμβος περιέχει δεδομένα και έναν δείκτη.
Ο δείκτης head δείχνει στον πρώτο κόμβο της λίστας.
Ο δείκτης του τελευταίου κόμβου έχει τιμή NULL.
Στη διπλά συνδεδεμένη λίστα, κάθε κόμβος έχει δύο δείκτες.
Ο πίνακας έχει τυχαία προσπέλαση, ενώ η λίστα έχει ακολουθιακή προσπέλαση.
Λύση:
1. δεδομένα, δείκτη
2. head (κεφαλή)
3. NULL
4. δύο
5. τυχαία, ακολουθιακή
Άσκηση 3: Σωστό / Λάθος
⭐⭐
Σε μια λίστα, οι κόμβοι αποθηκεύονται σε συνεχόμενες θέσεις μνήμης.
Ο δείκτης head δείχνει στον τελευταίο κόμβο.
Στη διπλά συνδεδεμένη λίστα μπορούμε να διατρέξουμε τη λίστα προς τις δύο κατευθύνσεις.
Ο πίνακας είναι δυναμική δομή δεδομένων.
Στη λίστα, για να διαγράψουμε έναν κόμβο αλλάζουμε τον δείκτη του προηγούμενου.
Μπορούμε να κάνουμε αποτελεσματικά δυαδική αναζήτηση σε λίστα.
Λύση:
1. ΛΑΘΟΣ — Οι κόμβοι της λίστας αποθηκεύονται σε μη συνεχόμενες θέσεις μνήμης.
2. ΛΑΘΟΣ — Ο head δείχνει στον πρώτο κόμβο, όχι στον τελευταίο.
3. ΣΩΣΤΟ — Αυτό είναι το βασικό πλεονέκτημα της διπλά συνδεδεμένης λίστας.
4. ΛΑΘΟΣ — Ο πίνακας είναι στατική δομή, όχι δυναμική.
5. ΣΩΣΤΟ — Αλλάζουμε τον δείκτη του προηγούμενου να δείχνει τον επόμενο.
6. ΛΑΘΟΣ — Η λίστα έχει ακολουθιακή πρόσβαση, άρα δυαδική αναζήτηση δεν είναι αποτελεσματική.
Άσκηση 4: Ανάπτυξη
⭐⭐⭐
Να αναπτύξετε σε 5-6 γραμμές γιατί η λίστα είναι προτιμότερη από τον πίνακα όταν θέλουμε να κάνουμε συχνές εισαγωγές και διαγραφές στοιχείων στο ενδιάμεσο της δομής.
Λύση:
Η λίστα είναι προτιμότερη για συχνές εισαγωγές και διαγραφές στο ενδιάμεσο γιατί:
Στον πίνακα, για να εισάγουμε ή διαγράψουμε ένα στοιχείο στο ενδιάμεσο, πρέπει να μετακινήσουμε όλα τα επόμενα στοιχεία — πολυπλοκότητα O(n).
Στη λίστα, απλά αλλάζουμε τους δείκτες του προηγούμενου και του νέου κόμβου — πολυπλοκότητα O(1) αν ξέρουμε τη θέση.
Επίσης, η λίστα έχει δυναμικό μέγεθος, οπότε δεν υπάρχει πρόβλημα υπερχείλισης όπως στον πίνακα.