Συνδεμένη λίστα

Τελικά ας δούμε μιά εφαρμογή των τεχνικών διάθεσης μνήμης στη διαχείριση 
μιάς βασικής δομής δεδομένων, της συνδεμένης λίστας. Μπορούμε να τη 
σκεφτούμε σαν ένα παιγνίδι του θησαυρού όπου μας δίνουν ένα σημείωμα που 
λέει 'κοίταξε στο σημείο Α'. Εκεί βρίσκουμε ένα άλλο σημείωμα που λέει 
'κοίταξε στο σημείο Β', κ.ο.κ. μέχρι που τελικά φθάνουμε στο θησαυρό. Η 
συνδεμένη λίστα αποτελείται από εγγραφές όπου η πρώτη ξέρει τη διεύθυνση της 
δεύτερης, η δεύτερη της τρίτης κ.ο.κ. Η απλή συνδεμένη λίστα δεν μας δίνει τη 
δυνατότητα να γυρίσουμε προς τα πίσω αλλά πάντα μπορούμε να πάμε στην 
αρχή και να ξαναξεκινήσουμε από εκεί. 

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

Οι εκτελέσιμες προτάσεις αρχίζουν με τη κλήση της συνάρτησης malloc γιά τη 
διάθεση μιάς εγγραφής. Οι προτάσεις εκχώρησης που ακολουθούν δίνουν στα 
πεδία της εγγραφής κάποιες τιμές. Το πεδίο του δείκτη παίρνει τη τιμή του 
μηδενικού δείκτη (NULL) αφού η παρούσα εγγραφή είναι η πρώτη αλλά και η 
τελευταία της λίστας και επομένως ο δείκτης δεν έχει να δείξει πουθενά. Η 
πρώτη αυτή εγγραφή συνηθίζεται να ονομάζεται κεφαλή (head) της λίστας και 
έχει ιδιαίτερη σημασία αφού αποτελεί τη μοναδική είσοδο που μας επιτρέπει να 
διατρέξουμε όλη τη λίστα. Ο δείκτης start που είναι ο αποδέκτης της τιμής που 
επέστρεψε η συνάρτηση malloc περιέχει τη διεύθυνση της κεφαλής της λίστας 
και γι΄ αυτό το λόγο θα παραμείνει αμετάβλητος σε όλη τη διάρκεια του 
προγράμματος. Αν ο start αλλάξει κατά λάθος τιμή και η κεφαλή δεν δείχνεται 
από άλλο δείκτη τότε δεν υπάρχει τρόπος ανάκτησης της διεύθυνσης της 
κεφαλής. 

Το ζευγάρι των δύο άλλων δεικτών prior και point χρησιμοποιείται γιά να 
δημιουργήσουμε και να διατρέξουμε τη λίστα. Στην αρχή ο δείκτης prior παίρνει 
την τιμή του start δηλαδή δείχνει και αυτός στη καφαλή της λίστας, που 
άλλωστε είναι το μοναδικό στοιχείο της λίστας αυτή τη στιγμή. Η επανάληψη 
for εκτελείται όσες φορές επιτρέπει η σταθερά RECORDS και σε κάθε 
επανάληψη προστίθεται ένα νέο στοιχείο στη λίστα. Προσοχή στην εναλλαγή 
θέσεων των δύο δεικτών prior και point: Ο point δείχνει κάθε φορά τη νέα 
εγγραφή που δημιουργείται με malloc και η οποία είναι κατ' αρχή ανεξάρτητη 
από την υπόλοιπη λίστα. Μόλις τα πεδία της εγγραφής πάρουν κάποιες αρχικές 
τιμές τότε η νέα εγγραφή συνδέεται στο τέλος της λίστας. Η σύνδεση αυτή 
γίνεται με τη βοήθεια του δείκτη prior: Ο δείκτης αυτός δείχνει πάντα το 
τελευταίο στοιχείο της λίστας. Άρα η εκχώρηση 

prior->next = point;

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

Στο τέλος κάθε βήματος επανάληψης έχουμε μιά πλήρη λίστα με τα παρακάτω 
χαρακτηριστικά που ισχύουν γιά οποιαδήποτε λίστα: 
  • Υπάρχει ένας δείκτης (εδώ ο start) που δείχνει τη κεφαλή της λίστας.
  • Κάθε στοιχείο της λίστας περιέχει ένα δείκτη (εδώ ο next) που δείχνει στο επόμενο στοιχείο της λίστας.
  • Στο τελευταίο στοιχείο της λίστας ο δείκτης προς το επόμενο στοιχείο είναι μηδενισμένος.

Το σχήμα που ακολουθεί δείχνει τις αλλαγές που συμβαίνουν κατά την 
εκτέλεση του δεύτερου βήματος της επανάληψης.

 Η επανάληψη do-while που ακολουθεί είναι τυπική των τεχνικών πρόσβασης 
σε μιά συνδεμένη λίστα. Γενικά δεν γνωρίζουμε τον αριθμό των στοιχείων μιάς 
λίστας, άρα δεν μπορούμε να χρησιμοποιήσουμε επανάληψη for. Αυτό που 
έχουμε στη διάθεσή μας είναι μιά συνθήκη τερματισμού, ότι δηλαδή ο τελευταίος 
δείκτης είναι μηδενικός. Άρα είναι λογική η χρήση μιάς επανάληψης με while. 
Γιατί do-while και όχι while-do; Αυτό εξαρτάται από τη σύμβαση σχετικά με 
τη κεφαλή της λίστας, δηλαδή τον όρισμό της άδειας λίστας. Μπορεί να έχουμε 
ένα άδειο ή κανένα στοιχείο στη λίστα. Στη περίπτωσή μας η άδεια λίστα 
ορίζεται ως η λίστα με ένα άδειο στοιχείο που δείχνεται από το δείκτη start. 
Τότε έχουμε τουλάχιστο μιά επανάληψη και άρα χρησιμοποιούμε do-while. Θα 
μπορούσε κανείς να θεωρήσει οτι η άδεια λίστα ισοδυναμεί με ένα μηδενικό 
δείκτη start. Τότε χρησιμοποιούμε while-do.

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

Η πρώτη επανάληψη do-while εμφανίζει τα περιεχόμενα της λίστας. Οι δείκτες 
prior και point χρησιμοποιούνται και πάλι γιά να διατρέξουμε τη λίστα. 
Προσπαθήστε να εκφράσετε την ίδια επανάληψη με ένα μόνο δείκτη. Η 
εκτύπωση δίνεται παρακάτω

General is a Mixed Breed, and is 4 years old.
Frank is a Laborador Retriever, and is 3 years old.
Frank is a Laborador Retriever, and is 3 years old.
Frank is a Laborador Retriever, and is 3 years old.
Frank is a Laborador Retriever, and is 3 years old.
Frank is a Laborador Retriever, and is 3 years old.
Frank is a Laborador Retriever, and is 3 years old.

Η τελευταία επανάληψη do-while αποδεσμέυει το χώρο της μνήμης που 
καταλαμβάνει η λίστα.
Αφηρημένοι τύποι δεδομένων

Εκτός από τη μαζική εισαγωγή, εμφάνιση και διαγραφή στοιχείων υπάρχουν και 
ορισμένες άλλες βασικές λειτουργίες που μπορούμε να καθορίσουμε γιά τη 
συνδεμένη λίστα. Μερικές από αυτές είναι
  • Απαρίθμηση στοιχείων
  • Μετακίνηση δείκτη σε θέση ή στοιχείο
  • Αναζήτηση στοιχείου και εμφάνιση στοιχείου
  • Εισαγωγή στοιχείου με βάση τη θέση του ή άλλο κριτήριο
  • Διαγραφή στοιχείου με βάση τη θέση του ή άλλο κριτήριο

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

create_list(start);
delete_list(start);
print_list(start);
...

αποκρύβοντας έτσι όλες τις λεπτομέρειες της διαχείρισης της συνδεμένης 
λίστας, με εξάιρεση ίσως τη μορφή της εγγραφής που αποτελεί το στοιχείο της 
λίστας. Η προγραμματιστική αυτή τεχνική ανεφέρεται ως δημουργία ενός 
'αφηρημένου τύπου δεδομένων' (Abstract Data Type, ADT). 

'Ηδη έχουμε συναντήσει έναν τουλάχιστο αφηρημένο τύπο δεδομένων, αυτόν της 
συμβολοσειράς (string), που είναι ένας ειδικός πίνακας χαρακτήρων. Ολόκληρη η 
βιβλιοθήκη με αρχείο κεφαλή STRING.H είναι αφιερωμένη σε συναρτήσεις που 
διευκολύνουν τη διαχείριση των συμβολοσειρών.
Άλλες δομές δεδομένων

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

Ορισμένες γραμμικές δυναμικές δομές είναι 

1. Η στοίβα (stack), είναι λίστα που επιτρέπει πρόσβαση μόνο στη κεφαλή της.
2. Η ουρά (queue) είναι λίστα που επιτρέπει πρόσβαση μόνο στα δύο άκρα της, 
    στο ένα γιά εισαγωγή και στο άλλο γιά εξαγωγή στοιχείων.
3. Η διπλή συνδεμένη (doubly linked) λίστα είναι λίστα όπου το κάθε στοιχείο 
    δείχνει το προηγούμενο και το επόμενο στοιχείο.
4. Η κυκλική (cicrular) λίστα όπου το τελευταίο στοιχείο δείχνει το πρώτο.
5. Η διπλή κυκλική συνδεμένη λίστα, συνδυασμός των 3 και 4.

Ορισμένες διδιάστατες δυναμικές δομές είναι

1. Διδιάστατες λίστες, όπου κάθε στοιχείο μιάς λίστας αποτελεί τη κεφαλή μιάς 
    άλλης λίστας.
2. Δυαδικά δένδρα (binary trees), όπου υπάρχει ένας πατρικός κόμβος (ρίζα), 
    κάθε ενδιάμεσος κόμβος έχει δύο κλάδους εκτός από τους τελικούς κόμβους που 
    δεν έχουν κλάδους.
3. Διπλά συνδεμένα δυαδικά δένδρα όπου έχουμε διπλόυς δείκτες ώστε να 
    επιτρέπεται και η προς τα πίσω πρόσβαση.
4. Τετραδικά δένδρα (quad-trees), τυχαία δένδρα κ.λ.π.
5. Γενικά δίκτυα ή γραφήματα απλής ή διπλής κατεύθυνσης.

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

Ο συμβολομεταφραστής είναι ένα άλλο παρέδειγμα χρήσης δομών δεδομένων. Ο 
πίνακας συμβόλων πώς υλοποιείται; Τα δένδρα σάρωσης τι τύπου είναι;
 
Ολόκληρα βιβλία γραφονται γιά μία και μοναδική δομή δεδομένων, όπως και 
γιά προβλήματα ταξινόμησης, αναζήτησης, συμβολομετάφρασης, διεχίρισης 
αρχείων κ.λ.π. Αυτά ξεπερνούν κατά πολύ ένα εισαγωγικό κείμενο στη C.

Περιεχόμενα Κεφαλαίου