Συνδεδεμένες λίστες

Συνδεδεμένες Λίστες(Linked Lists)

Ορισμός:

Μια συνδεδεμένη λίστα είναι μια ακολουθία κόμβων συνδεδεμένων μεταξύ τους. Ο κάθε κόμβος (node) αποτελείται από δύο τμήματα:

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

Τα στοιχεία της λίστας (οι κόμβοι) βρίσκονται σε συγκεκριμένη σειρά. Το πρώτο στοιχείο δείχνει το δεύτερο, το δεύτερο το τρίτο και τα λοιπά. Ο τελευταίος κόμβος δε δείχνει πουθενά (έχει τιμή null). Υπάρχει επίσης ένα ειδικό στοιχείο που ονομάζεται κεφαλή της λίστας(Head) το οποίο δείχνει στον πρώτο κόμβο της λίστας.

Χρηση της συνδεδεμένης λίστας.

Οι λίστες χρησιμοποιούνται για τη δυναμική αποθήκευση δεδομένων. Γενικά υπάρχουν δύο τρόποι να αποθηκευτούν συλλογές από συσχετιζόμενα δεδομένα, σαν πίνακες (arrays) και σαν λίστες (lists). Το πρόβλημα με τους πίνακες ότι το μέγεθός τους είναι αμετάβλητο. Έτσι προκειμένου να αποθηκεύσεις ένα σύνολο δεδομένων με χρήση πινάκων θα πρέπει να ξέρεις προκαταβολικά το μέγεθος τους, έτσι ώστε να δεσμεύσεις την απαραίτητη μνήμη για τον πίνακα. Στην πράξη όμως το μέγεθος αυτό δεν είναι πάντα γνωστό. Θα μπορούσαμε βέβαια εξαρχής να δεσμεύσουμε μια μεγάλη ποσότητα μνήμης τέτοια ώστε να καλύψει οποιαδήποτε ποσότητα δεδομένων που μπορεί να προκύψει στο πρόβλημά μας. Η λύση όμως αυτή μειονεκτεί. Καταρχήν αρχικά δεσμεύουμε περισσότερη μνήμη από όση χρειαζόμαστε ενώ μελλοντικά ακόμα και αυτή μπορεί να αποδειχτεί ανεπαρκής.
Με τις λίστες αντίθετα έχουμε δυναμική απόκτηση μνήμης. Η λίστες λειτουργούν με τέτοιο τρόπο που ο χώρος που χρειάζεται για κάθε στοιχείο δεδομένων αποκτάται δυναμικά τη στιγμή που το χρειάζεται. Έτσι δεσμεύουμε ακριβώς τη μνήμη που χρειαζόμαστε και όχι παραπάνω ενώ το πλήθος των δεδομένων που μπορούν να φορτωθούν στη μνήμη περιορίζεται από το φυσικό μέγεθος της μνήμης και από τίποτε άλλο.
Αν και μπορούμε να κατασκευάσουμε μια λίστα χρησιμοποιώντας πίνακες στην πράξη δεν είναι πολύ αποδοτικό. Στη σελίδα αυτή θα ασχοληθούμε με τις απλές συνδεδεμένες λίστες που κάνουν χρήση δεικτών.

Λειτουργίες πάνω σε συνδεδεμένες λίστες.

Αρχικοποίηση λίστας.
Καταστροφή (υπάρχουσας λίστας)
Προσθήκη στοιχείου στη λίστα.
Διαγραφή κόμβου.
Αναζήτηση κόμβου.
Εμφάνιση (ή οποιαδήποτε) άλλη λειτουργία ενός κόμβου ή όλων.

Αρχικοποίηση λίστας.

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

Ο ψευδοκώδικας για τα παραπάνω.

create new Head                //δημιουργία κεφαλής
Head.data=dummy            //Απόδοση συμβολικής τιμής
Head.next=null        //Ορίζουμε να δείχνει στο null

Καταστροφή λίστας.

Η καταστροφή της λίστας συνίσταται στην αποδέσμευση της μνήμης απο τα στοιχεία της λίστας και στον ορισμό της κεφαλής να δείχνει στο null.
Καταστρέφουμε τη λίστα όταν τα στοιχεία της δε μας χρειάζονται επιστρέφοντας στο σύστημα τη μνήμη που καταλάμβανουν.
Πως γίνεται αυτό; Όσο η κεφαλή δε δείχνει στο null σβήνουμε τον κόμβο στον οποίο δείχνει η κεφαλή και θέτουμε την κεφαλή να δείχνει στον κόμβο που έδειχνε ο κόμβος που σβήστηκε.

Ο ψευδοκώδικας για τα παραπάνω.

currentNode=Head.next
while(currentNode!=null)
            currentNode=currrentNode.next
            delete Head.next
            Head.next=currentNode
end while
Στο τέλος μένει μόνο η κεφαλή να δείχνει στο στοιχείο null.

Προσθήκη στοιχείου στη λίστα.

Υποθέτουμε πως η λίστα δεν είναι άδεια έτσι η κεφαλή (Head) δείχνει στον w που είναι ο πρώτος κόμβος της λίστας.
Αυτό συνεπάγεται πως Head=w .
Αρχικά δημιουργείται ο κόμβος v που πρόκειται να προστεθεί στη λίστα. Αρχικοποιούμε τον κόμβο γεμίζοντας το τμήμα πληροφορίας του (data) με κάποια τιμή. Ο κόμβος αυτός θα παρεμβληθεί στην αρχή της λίστας. Αυτό γίνεται ως εξής:
Θέτουμε τον κόμβο να δείχνει στο πρώτο στοιχείο της λίστας δηλαδή στο στοιχείο που δείχνει η κεφαλή. Η κεφαλή μετά θα πρέπει να δείχνει στο καινούργιο κόμβο. Το αποτέλεσμα όλων αυτών είναι η αποσύνδεση του Head και του παλιού πρώτου κόμβου, η παρεμβολή του νέου κόμβου, και η μεταφορά του παλιού κόμβου στη δεύτερη θέση.

Ο ψευδοκώδικας για τα παραπάνω.
create new node            //δημιούργησε νέο κόμβο
node.data=d                    //μεταβίβασε την πληροφορία d στον v
node.next=Head .next   //κάνε τον v να δείχνει εκεί που έδειχνε αρχικά η κεφαλή της λίστας
Head.next=node              //κάνε την Κεφαλή της λίστας να δείχνει στον καινούργιο κόμβο v

Ο παραπάνω ψευδοκώδικας λειτουργεί και όταν η λίστα είναι άδεια. Σε αυτή την περίπτωση Head.next=null. Ο καινούργιος κόμβος τώρα δείχνει στο null πράγμα που σημαίνει ότι δεν υπάρχει άλλος κόμβος μετά από αυτόν.
Γραφική απεικόνιση εισαγωγής νέου κόμβου στην αρχή της λίστας.

Διαγραφή κόμβου.

Έστω ότι θέλουμε να διαγράψουμε κάποιον κόμβο v ο οποίος περιέχει κάποια συγκεκριμένη πληροφορία. Για παράδειγμα σε μια λίστα ακεραίων θα μπορούσαμε να διαγράψουμε το πρώτο στοιχείο της λίστας με τιμή ίση με Κ=23. Ξεκινώντας από τον πρώτο κόμβο θα σαρώναμε σειριακά τη λίστα μέχρι να βρούμε κάποιον κόμβο με τιμή ίση με Κ. Αν τον βρίσκαμε θα τον διαγράφαμε. Πρέπει να τονιστεί εδώ ότι το στοιχείο Κ μπορεί να μην υπάρχει στη λίστα (οπότε δε γίνεται καμιά ενέργεια) ενώ μπορεί να υπάρχουν περισσότεροι του ενός κόμβου με τιμή ίση με Κ (οπότε σβήνουμε μόνο τον πρώτο κόμβο από αυτούς).

Τα βήματα που πρέπει να κάνουμε προκειμένου να διαγράψουμε τον ζητούμενο κόμβο είναι:

Ψάχνοντας σειριακά όλους τους κόμβους από τον πρώτο βρίσκουμε τον αμέσως προηγούμενο κόμβο από αυτόν που θα διαγράψουμε (από αυτόν που έχει την πληροφορία που θέλουμε).
Θέτουμε αυτόν τον κόμβο να δείχνει στον ίδιο κόμβο που δείχνει ο κόμβος που πρόκειται να διαγραφεί. Με λίγα λόγια παραλείπουμε από την αλυσίδα των κόμβων τον κόμβο που θα διαγράψουμε.
Τέλος σβήνουμε τον κόμβο αποδεσμεύοντας τη μνήμη που καταλάμβανε.

Ο ψευδοκώδικας για τα παραπάνω.

currentNode=Head	//ο τρέχων κόμβος είναι ο πρώτος
while( currentNode.next!= null and currentNode.next.data!=K)	//αν ο επόμενος κόμβος δεν είναι null ή δεν έχει την τιμή Κ
currentNode=currentNode.next	// θέσε τρέχων κόμβο τον επόμενο
if (currentNode.next!=null and currentNode.next.data==K)	//αν ο τρέχων κόμβος δεν είναι ο τελευταίος και το στοιχείο του επόμενου κόμβου είναι το Κ
deleteNode= currentNode.next currentNode.next=currentNode.next.next; delete deleteNode	// θέσε τον τρέχων δείκτη να δείχνει στο μεθεπόμενο κόμβο //αποδέσμευσε τη μνήμη που καταλαμβάνει ο διαγραφής κόμβος

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

Αναζήτηση κόμβου με τιμή ίση με Κ.

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

currentNode=Head.next	//το curNode δείχνει στο πρώτο στοιχείο της λίστας.
while (currentNode!=null)	// εκτέλεσε το βρόγχο όσο το curNode δεν είναι null
if (currentNode.data==K)	// αν το τμήμα δεδομένων του είναι Κ
return currentNode	// η αναζήτηση τελείωσε και η ρουτίνα επιστρέφει τον κόμβο
currentNode=currentNode.next	//διαφορετικά πήγαινε στον επόμενο κόμβο
end while
// ο κόμβος με το στοιχείο Κ δε βρέθηκε	// κανένα στοιχείο της λίστας δεν περιέχει την τιμή Κ

Ενέργειες στα στοιχεία της λίστας.

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

Ο ψευδοκώδικας για τη σχεδίαση όλων των σχημάτων που υπάρχουν σε μια λίστα με σχήματα.

currentNode=Head.next
while(currentNode!=null)                    //όσο ο τρέχων κόμβος δεν είναι null
        display(currentNode.shape)        //σχεδίασε το σχήμα του τρέχων κόμβου
        currentNode=currentNode.next        //κάνε τρέχων τον επόμενο κόμβο
end while

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

APPLET

Σε αυτό το Applet βλέπουμε τις λειτουργίες της εισαγωγής (Add), σβήσιμο συγκεκριμένου κόμβου (Delete) αναζήτησης (Search) , και καταστροφής λίστας (Destroy) όπως περιγράφτηκαν παραπάνω.