Η έννοια της Λίστας


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


Διαχείριση Λίστας 

Η δομή της λίστας απαρτίζεται από την θέση που καταλαμβάνει το αντικείμενο ή το στοιχείο που αποθηκεύουμε σε αυτή και από έναν δείκτη που "δείχνει" την θέση του στοιχείου.Δηλαδή η θέση  ενός στοιχείου μέσα σε µια λίστα είναι η χαρακτηριστική ιδιότητα του στοιχείου, Το πρώτο στοιχείο
µιας λίστας ονοµάζεται κεφαλή (head), ενώ μια λίστα µε κανένα στοιχείο ονοµάζεται κενή λίστα (null list).
Για να αναπαραστήσουμε μια λίστα αρκεί να ορίσουμε τη θέση που αποθηκεύεται το στοιχείο  το οποίο και θα ονομάζουμε κόμβο και τον δείκτη που θα δείχνει το κόμβο. Με άλλα λόγια ο υπολογιστής μας δεν γνωρίζει τι περιεχόμενο έχει σε κάθε κόμβο αλλά την τιμή του δείκτη του κόμβου.
Στην C ο ορισµός µιας  λίστας µπορεί να γίνει ως εξής:

typedef struct kombos *pointer;

typedef struct kombos {
            typostoixeiou stoixeio;
           deiktiskombou deiktis;
} KOMBOS;

pointer L;

Εδώ, το ‘*’  ορίζει έναν  δείκτη της δομής kombos µε το όνοµα ‘pointer’. Στην συνέχεια ορίζουμε τον κόμβο(struct) ‘kombos’,  αναγράφοντας τον τύπο του στοιχείου και το όνομά του, όπως πράττουμε το ίδιο και για τον δείκτη. Μεταβλητές του τύπου αυτού, όπως η L, είναι δείκτες και «δείχνουν» σε δεδοµένα τύπου ‘KOMBOS’, δηλαδή σε µια εγγραφή που περιγράφεται από τη δοµή (struct) ‘kombos’.

Διαπέραση Λίστας

Θα δώσουμε παρακάτω τον αλγόριθμο διαπέρασης μιας λίστας.

DL-DIAPERASH (L)

1 P<--L               //Αρχικοποίηση δείκτη

2 while P ≠ NUL //Συνθήκη τερµατισµού

3 PROCESS (STOIXEIO(KOMBOS(P))) //Εφαρµογή διαδικασίας

4 P<--DEIKTHS(KOMBOS(P)) //Ενηµέρωση τρέχοντος δείκτη
endwhile

Κατ’ αρχήν, αρχικοποιούµε τη βοηθητική (τοπική) µεταβλητή P, δίνοντάς της σαν τιµή τη διεύθυνση του πρώτου κόµβου της λίστας. Στη συνέχεια, ξεκινά µια επαναληπτική διαδικασία που έχει δύο βήµατα στο σώµα της. Στοπρώτο (βήµα 3), εφαρµόζεται η διαδικασία PROCESS στο στοιχείο του τρέχοντος κόµβου. Στο δεύτερο (βήµα 4), ενηµερώνεται ο δείκτης P ώστε να δείχνει τον επόµενο κόµβο της λίστας. Η εκτέλεση των βηµάτων αυτών τερµατίζεται όταν ο δείκτης P πάρει την τιµή NUL, που σηµαίνει ότι δεν υπάρχει επόµενος κόµβος.

Εισαγωγή σε λίστα

DL-EISAGWGH-META (P, PI)

1 if (P = NUL) or (PI = NUL)             //Έλεγχος δεικτών

2 then print ‘ΑΝΥΠΑΡΚΤΟΣ ΚΟΜΒΟΣ’    //Μήνυµα λάθους

3 else DEIKTHS(KOMBOS(P)) <--DEIKTHS(KOMBOS(PI)) //Ενηµέρωση δείκτη

4 DEIKTHS(KOMBOS(PI))<--P {Ενηµέρωση δείκτη}

endif

Δέχεται δύο παραµέτρους εισόδου, τον δείκτη στον προς εισαγωγή κόµβο (Ρ) και τον δείκτη στον κόµβο µετά τον οποίο θα γίνει η εισαγωγή (ΡΙ). Μετά τον έλεγχο για την ύπαρξη των δύο δεικτών και την επιστροφή κατάλληλου µηνύµατος (βήµατα 1-2), αρχίζει ο κυρίως αλγόριθµος που αποτελείται από δύο βήµατα. Στο βήµα 3, ο δείκτης του (προς εισαγωγή) κόµβου Ρ γίνεται δείκτης στον κόµβο που είναι µετά τον κόµβο PI, και με αυτόν τον τρόπο κρατάμε την πληροφορία για το ποιος είναι ο επόμενος δείκτης και κατά συνέπεια η επόμενη κενή θέση προς συμπλήρωση.

Διαγραφή σε λίστα

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

DL-DIAGRAFΗ(PI)

1 if (P=NUL) or (DEIKTHS(KOMBOS(PI))=NUL) //Έλεγχος δεικτών

2 then print ‘ΑΝΥΠΑΡΚΤΟΣ ΚΟΜΒΟΣ’                 //Μήνυµα λάθους

3 else A<--DEIKTHS(KOMBOS(PI))                     //Ενηµέρωση δεικτών

4 DEIKTHS(KOMBOS(P))<--DEIKTHS(KOMBOS(Α))

endif

Στο βήµα 1 γίνεται έλεγχος ύπαρξης του προηγούµενου (Ρ = ΝUL) και του προς διαγραφή (DEIKTHS(KOMBOS(PI)) = NIL) κόµβου. Αν κάποιος από αυτούς δεν υπάρχει, τότε επιστρέφει το αντίστοιχο µήνυµα. Αλλιώς, προχωρά στον κυρίως αλγόριθµο που είναι τα βήµατα 3και 4. 
Στο βήµα 3 κάνουµε την τιµή µιας βοηθητικής µεταβλητής δείκτη A ίση µε την τιµή του δείκτη στον υπό διαγραφή κόµβο δηλαδή αποθηκεύουµε την τρέχουσα τιµή του "δείκτη" του κόµβου.Στο βήµα 4 ενηµερώνουµε το δείκτη του προηγουµένου  κόµβου µε την τιµή του δείκτη του προς διαγραφή κόµβου ώστε να «δείχνει» στον επόµενο τού προς διαγραφή κόµβου.

Με άλλα λόγια αν έχουμε τους κόμβους 2-->3-->4 τότε ενημερώνουμε τον δείκτη της θέσης 2 με την τιμή του δείκτη της θέσης 3. Επειδή η θέση 3 δείχνει τον 4 τότε ουσιαστικά με την ενημέρωση αυτή ο 2 θα βλέπει για επόμενό του τον κόμβο 4! Δηλαδή ο κόμβος 3 διαγράφτηκε.