Απλή Δομή Λίστας και Σύγκριση με Πίνακες
έγραψε:ΠΙΝΑΚΑΣ ΠΕΡΙΕΧΟΜΕΝΩΝ:
Μέρος 1ο - Απλή Δομή Λίστας και Σύγκριση με Πίνακες
Μέρος 2ο - Λίστα ως Όρισμα Αναφοράς (by Reference) & ως Όρισμα Τιμής (by Value) - Συναρτήσεις: print, length & destroy
Μέρος 3ο - Προσθήκη Νέων Κόμβων στην Αρχή της Λίστας - Συνάρτηση: prepened
Μέρος 4ο - Προσθήκη Νέων Κόμβων στο Τέλος της Λίστας - Συνάρτηση: append
Μέρος 5ο - Αναβαθμισμένη Δομή Λίστας (ενσωμάτωση δεικτών Κεφαλής & Ουράς και ενσωμάτωση Μήκους)
Μέρος 6ο - Επανακωδικοποίηση των Συναρτήσεων: prepend, append, print και destroy (κατάργηση της: length)
Λοιπόν, αποφάσισα να προσπαθήσω να αποσαφηνίσω όσο μπορώ τα περί singly linked lists (απλά συνδεδεμένες λίστες) ελπίζοντας πως θα φανούν χρήσιμα σε αρκετά παιδιά. Δεν ξέρω πόσα posts θα χρειαστούν. Θα εξαρτηθεί υποθέτω από την όρεξή μου και την ανταπόκριση της 1ης
Οι απλά συνδεδεμένες λίστες είναι άμεσα συγκρίσιμες με τους πίνακες (arrays) ως προς το σκοπό ύπαρξής τους, έχοντας υπέρ και κατά συγκριτικά με τους πίνακες.
Το βασικό τους υπέρ είναι πως καταναλώνουν & δημιουργούν ακριβώς όσο χώρο χρειάζονται, ενώ για του πίνακες πρέπει να κάνουμε μια πρόβλεψη για το μέγιστο πλήθος των στοιχείων τους, όταν τους πρωτο-ορίζουμε. Αν στην πράξη χρειαστούμε πολύ λιγότερα στοιχεία από όσα έχουμε προβλέψει, τότε έχουμε σπαταλήσει άδικα πολύτιμη μνήμη. Αν στην πράξη χρειαστούμε περισσότερα στοιχεία από όσα έχουμε προβλέψει, τότε την... κάτσαμε την βάρκα
(υπάρχουν και οι δυναμικοί πίνακες, ως ενδιάμεση λύση αλλά ας μη τα μπλέξουμε όλα μαζί και χαθούμε).Το βασικό μειονέκτημα των λιστών έναντι των πινάκων είναι ο αυξημένος χρόνος προσπέλασης και αναζήτησης κάποιου στοιχείου, καθώς και η μεγαλύτερη πολυπλοκότητα του κώδικα, που μεταξύ άλλων προϋποθέτει να έχει κατανοήσει κανείς τους δείκτες γενικώς.
Οι πίνακες είναι λίγο-πολύ γνωστό σε όλους πως αποτελούνται από συνεχόμενα στοιχεία στη μνήμη, που σημαίνει πως είναι πολύ εύκολο & γρήγορο να αναφερθούμε σε οποιοδήποτε στοιχείο του με ένα απλό indexing: array[i].
Οι λίστες αποτελούνται κι αυτές από στοιχεία που ονομάζονται κόμβοι (nodes) και δεν είναι συνεχόμενα στη μνήμη. Δεν είναι καν δημιουργημένα όταν ξεκινάμε. Το κάθε στοιχείο (κόμβος) είναι μια δομή δεδομένων (struct στη C) η οποία οφείλει να έχει το λιγότερο ένα πεδίο για τα δεδομένα του στοιχείου κι άλλο ένα που θα είναι δείκτης προς το επόμενο στοιχείο.
Ας πάρουμε για παράδειγμα έναν πίνακα από int και μια λίστα από int, για να τα συγκρίνουμε.
Για τον πίνακα, ας κάνουμε μια πρόβλεψη για χωρητικότητα 100 στοιχείων, οπότε θα τον ορίζαμε κάπως έτσι:
- Κώδικας: Επιλογή όλων
int main( void )
{
int array[100];
...
return 0;
}
Αν αντί για πίνακα επιλέξουμε την υλοποίηση σε λίστα, δεν χρειάζεται να κάνουμε πρόβλεψη για τη μέγιστη χωρητικότητά της, αλλά πρέπει να ορίσουμε μια δομή (struct) που θα αντιστοιχεί στον κάθε της κόμβο (στοιχείο). Κατόπιν πρέπει να ορίσουμε την αρχή της λίστας ως μια μεταβλητή που θα είναι δείκτης στο struct μας (την μεταβλητή συνήθως την ονομάζουμε list, head ή root). Επειδή αρχικά η λίστα μας είναι άδεια, αρχικοποιούμε τη μεταβλητή μας σε NULL.
Για παράδειγμα:
- Κώδικας: Επιλογή όλων
struct node {
int value;
struct node *next;
};
int main( void )
{
struct node *list;
list = NULL;
...
return 0;
}
Μια παρένθεση εδώ, σχετικά με δυνατότητα της C για ορισμό πρόσθετων τύπων που θα μας εξυπηρετήσει ώστε να μη γράφουμε συνέχεια τη λέξη struct. Στη C λοιπόν με την εντολή typedef μπορούμε να ορίζουμε δικούς μας τύπους δεδομένων ή να δημιουργούμε συνώνυμα για τους στάνταρ τύπους δεδομένων. Το πιο κλασικό παράδειγμα της δεύτερης περίπτωσης, είναι ο ορισμός του πρόσθετου τύπου "bool" για μεταβλητές που χρησιμοποιούνται ως boolean flags, που ως τύπος είναι απλά ένα συνώνυμο του κλασικού τύπου int...
- Κώδικας: Επιλογή όλων
typedef int bool;
bool x = 0; // ισοδυναμεί με: int x = 0;
Όταν ο πρόσθετος τύπος θέλουμε να είναι ένα struct (ή ένα enum ή ένα union) τότε μπορούμε να συγχωνεύσουμε σε ένα και μόνο βήμα τον ορισμό του struct και την δήλωσή του ως πρόσθετο τύπο, ως εξής:
- Κώδικας: Επιλογή όλων
typedef struct node {
int value;
struct node *next;
}Node;
Οπότε ξαναγράφοντας τον κώδικα για τον ορισμό της λίστας έχουμε:
- Κώδικας: Επιλογή όλων
typedef struct node {
int value;
struct node *next;
} Node;
int main( void )
{
Node *list;
list = NULL;
...
return 0;
}
Σε αυτό το σημείο, με την 1η υλοποίηση έχουμε ορίσει έναν ΑΔΕΙΟ πίνακα 100 στοιχείων τύπου int, ενώ με τη 2η υλοποίηση έχουμε ορίσει μια ΑΔΕΙΑ λίστα στοιχείων τύπου int (βασικά τύπου δομής struct node ή απλώς τύπου Node, αλλά εφόσον μιλάμε για λίστες είναι αυτονόητο πως το κάθε στοιχείο είναι δομή και μάλιστα με ένα πεδίο *next που δείχνει στο επόμενο στοιχείο, οπότε είναι θεμιτό να πούμε πως η λίστα είναι τύπου int, λόγω του πεδίου value που χαρακτηρίζει τα δεδομένα των κόμβων της).
Για να βάλουμε την τιμή πχ 52 στο 1ο στοιχείο του array, γράφουμε απλώς:
- Κώδικας: Επιλογή όλων
int array[100];
array[0] = 52;
Για να βάλουμε όμως την τιμή 52 στο 1ο στοιχείο της λίστας δεν είναι τόσο απλά τα πράματα!
Καταρχήν δεν υπάρχει καν δημιουργημένο 1ο στοιχείο! Απλά έχουμε έναν δείκτη list τύπου Node που δείχνει στο κενό (NULL). Άρα πρώτα πρέπει να δεσμεύσουμε στη μνήμη τόσο χώρο όσο χρειάζεται ένα στοιχείο της λίστας για τα δυο πεδία του (value και *next). Αυτό το κάνουμε με την στάνταρ συνάρτηση malloc() ή την πιο ασφαλή εκδοχή της, την calloc(). Αφού δημιουργήσουμε στη μνήμη χώρο για το 1ο στοιχείο, θα βάλουμε τιμές στα δυο πεδία του και κατόπιν θα βάλουμε τον δείκτη list να δείχνει σε αυτό το στοιχείο..
- Κώδικας: Επιλογή όλων
Node *list, *newnode;
list = NULL;
newnode = calloc(1, sizeof(Node) ); // ισοδυναμεί με: newnode = calloc(1, sizeof(struct node) );
newnode->value = 52;
newnode->next = NULL;
list = newnode;
...
free( list ); // αποδέσμευση της μνήμης του 1ος και μοναδικού στοιχείου της λίστας, πριν τερματίσουμε το πρόγραμμά μας
Στην προκειμένη περίπτωση επειδή μιλάμε για ένα και μόνο στοιχείο, και συγκεκριμένα το 1ο στοιχείο, θα μπορούσαμε να κάνουμε απευθείας τη διαδικασία με τον list, και να μη χρησιμοποιούσαμε καθόλου τον *newnode.
Π.χ.
- Κώδικας: Επιλογή όλων
Node *list = NULL; // ισοδυναμεί με: Node *list; list = NULL;
list = calloc(1, sizeof(Node) ); // ισοδυναμεί με: list = calloc(1, sizeof(struct node) );
list->value = 52;
list->next = NULL;
...
free( list ); // αποδέσμευση της μνήμης του 1ος και μοναδικού στοιχείου της λίστας, πριν τερματίσουμε το πρόγραμμά μας
Όταν όμως εισαγάγουμε στοιχεία στη μέση ή στο τέλος μιας λίστας που ΔΕΝ είναι κενή, τότε είναι απαραίτητο να χρησιμοποιήσουμε 2η μεταβλητή (την *newnode στο παραπάνω παράδειγμα) ... θα το δούμε παρακάτω. Προς το παρόν κρατήστε πως ο list πρέπει ΑΠΑΡΑΙΤΗΤΑ να δείχνει στην ΑΡΧΗ της λίστας μας ανά πάσα στιγμή. Αν τον μετακινήσουμε π.χ στο 2ο στοιχείο μετά δεν έχουμε τρόπο να γυρίσουμε πίσω, γιατί στη δομή του κάθε στοιχείου ΔΕΝ υπάρχει δείκτης προς το πίσω, μόνο προς τα εμπρός (ο *next).
Ας υποθέσουμε τώρα πως θέλουμε να προσθέσουμε την τιμή 62 στο 2ο στοιχείο της λίστας μας (στον πίνακα θα γράφαμε απλώς: array[1] = 62;). Η λογική είναι σχεδόν η ίδια με προηγουμένως. Θα δημιουργήσουμε χώρο στη μνήμη για το νέο στοιχείο με τη χρήση ενός δείκτη *newnode, θα του βάλουμε τιμές στα πεδία value και *next και κατόπιν θα βάλουμε το πεδίο *next του 1ου στοιχείου της λίστας να δείχνει στο νέο στοιχείο που δημιουργήσαμε. Η διαφορά με πριν είναι πως αυτή τη φορά θα πρέπει ο list->next να δείχνει στον newnode (και όχι ο list, αυτός δείχνει στο 1ο στοιχείο της λίστας, το 52).
- Κώδικας: Επιλογή όλων
Node *list = NULL, *newnode = NULL;
// δημιουργία και εισαγωγή του 1ου στοιχείου
list = calloc(1, sizeof(Node) ); // ισοδυναμεί με: list = calloc(1, sizeof(struct node) );
list->value = 52;
list->next = NULL;
// δημιουργία και εισαγωγή του 2ου στοιχείου
newnode = calloc(1, sizeof(Node) ); // ισοδυναμεί με: newnode = calloc(1, sizeof(struct node) );
newnode->value = 62;
newnode->next = NULL;
list->next = newnode;
...
free( list->next ); // αποδέσμευση της μνήμης του 2ου στοιχείου της λίστας, πριν τερματίσουμε το πρόγραμμά μας
free( list ); // αποδέσμευση της μνήμης του 1ου στοιχείου της λίστας, πριν τερματίσουμε το πρόγραμμά μας
Ο ολοκληρωμένος κώδικας για τη δημιουργία μιας λίστας και εισαγωγή των 2 πρώτων στοιχείων της, καθώς και τύπωμά τους στην οθόνη με ένα while-loop που χρησιμοποιεί έναν βοηθητικό δείκτη (dummy) για να διατρέξει τη λίστα είναι ο εξής:
- Κώδικας: Επιλογή όλων
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node *next;
} Node;
int main ( void )
{
Node *list = NULL, *newnode = NULL;
// δημιουργία και εισαγωγή του 1ου στοιχείου
list = calloc(1, sizeof(Node) ); // ισοδυναμεί με: list = calloc(1, sizeof(struct node) );
list->value = 52;
list->next = NULL;
// δημιουργία και εισαγωγή του 2ου στοιχείου
newnode = calloc(1, sizeof(Node) ); // ισοδυναμεί με: newnode = calloc(1, sizeof(struct node) );
newnode->value = 62;
newnode->next = NULL;
list->next = newnode;
// τύπωμα της λίστας με χρήση βοηθητικού δείκτη: dummy
Node *dummy = list;
while ( dummy != NULL ) {
printf("%d ", dummy->value);
dummy = dummy->next;
}
free( list->next ); // αποδέσμευση της μνήμης του 2ου στοιχείου της λίστας, πριν τερματίσουμε το πρόγραμμά μας
free( list ); // αποδέσμευση της μνήμης του 1ου στοιχείου της λίστας, πριν τερματίσουμε το πρόγραμμά μας
fflush(stdin); getchar();
return 0;
}
Δύο σημαντικές επισημάνσεις:
α) Στο while loop που τυπώνει τη λίστα, χρησιμοποιούμε έναν βοηθητικό δείκτη (dummy) που αρχικά τον βάζουμε να δείχνει στην αρχή της λίστας (dummy = list) και κατόπιν μέσα στο loop, αφού πρώτα τυπώσουμε την τιμή value τον μετακινούμε στον επόμενο κόμβο (dummy = dummy->next), μέχρι να βρει NULL. Θα μπορούσα αντί για τον dummy να χρησιμοποιούσα τον newnode για αυτή τη δουλειά, αφού από τη στιγμή που η δομή του newnode εισήχθη στο τέλος της λίστας μας, ο δείκτης αυτός κάθε αυτός δεν έχει πλέον λόγο ύπαρξης (διότι η δομή του 2ου στοιχείου είναι προσβάσιμη από τον δείκτη next του 1ου στοιχείου). Όρισα όμως νέο δείκτη, τον dummy, για να μην μπερδευτείτε... να είναι πιο ξεκάθαρο.
Γιατί δεν χρησιμοποίησα απευθείας τον list για να διατρέξω τη λίστα; Π.χ...
- Κώδικας: Επιλογή όλων
while ( list != NULL ) {
printf("%d ", list->value);
list = list->next;
}
Διότι έτσι στο τέλος του loop ο δείκτης list αντί να δείχνει στην αρχή της λίστας θα έδειχνε στο τέλος της (που είναι NULL δλδ). Οπότε μετά πως θα αποδέσμευα παρακάτω με τη συνάρτηση free() τον χώρο του 1ου και του 2ου στοιχείου, πριν τερματίσω το πρόγραμμα; Δεν θα είχα τρόπο να ξαναγυρίσω στην αρχή της λίστας!
β) Για κάθε πετυχημένο malloc() ή calloc() που κάνουμε, πρέπει ΟΠΩΣΔΗΠΟΤΕ να κάνουμε ένα αντίστοιχο free() πριν τερματίσουμε το πρόγραμμά μας, για να αποδεσμεύσουμε το χώρο μνήμης που έχουμε δεσμεύσει πριν επιστρέψουμε τον έλεγχο στο λειτουργικό σύστημα. Και μάλιστα, για να μην καλούμε άδικα τα free() πρέπει σε κάθε μας malloc() ή calloc() να ελέγχουμε αν πέτυχαν.
Οπότε ο σωστός κι ασφαλής κώδικας είναι ο εξής:
- Κώδικας: Επιλογή όλων
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node *next;
} Node;
int main ( void )
{
Node *list = NULL, *newnode = NULL;
// δημιουργία και εισαγωγή του 1ου στοιχείου
list = calloc(1, sizeof(Node) ); // ισοδυναμεί με: list = calloc(1, sizeof(struct node) );
if ( !list ) // ισοδυναμεί με: if (list == NULL )
{
puts("*** out of memory, aborting program");
exit(1);
}
list->value = 52;
list->next = NULL;
// δημιουργία και εισαγωγή του 2ου στοιχείου
newnode = calloc(1, sizeof(Node) ); // ισοδυναμεί με: newnode = calloc(1, sizeof(struct node) );
if ( !newnode ) // ισοδυναμεί με: if (newnode == NULL )
{
puts("*** out of memory, aborting program");
free( list ); // αποδέσμευση μνήμης 1ου στοιχείου
exit(1);
}
newnode->value = 62;
newnode->next = NULL;
list->next = newnode;
// τύπωμα της λίστας με χρήση βοηθητικού δείκτη: dummy
Node *dummy = list;
while ( dummy ) // ισοδυναμεί με: while (dummy != NULL )
{
printf("%d ", dummy->value);
dummy = dummy->next;
}
free( list->next ); // αποδέσμευση της μνήμης του 2ου στοιχείου της λίστας, πριν τερματίσουμε το πρόγραμμά μας
free( list ); // αποδέσμευση της μνήμης του 1ου στοιχείου της λίστας, πριν τερματίσουμε το πρόγραμμά μας
fflush(stdin); getchar();
exit(0);
}
Ο παραπάνω κώδικας είναι ΑΧΡΗΣΤΟΣ στην πράξη, αφού το μόνο που κάνει είναι να δημιουργεί μια λίστα, να τις βάζει 2 στοιχεία, να την τυπώνει και να την καταστρέφει πριν τερματίσει το πρόγραμμα.
Γράφτηκε αποκλειστικά και μόνο ως μια προσπάθεια αποσαφήνισης της φύσης και των βασικών ιδεών για τις απλά συνδεδεμένων λίστες. Ο κώδικας για τον αρχικό ορισμό μιας κενής λίστας ισχύει ατόφιος ως μια από τις πιθανές υλοποιήσεις, σε διάφορα real-life προγράμματα. Ο κώδικας όμως για την εισαγωγή στοιχείων στη λίστα δεν είναι σε καμία περίπτωση ο παραπάνω.
Προφανώς χρειάζεται ξεχωριστή συνάρτηση η οποία θα παίρνει σαν όρισμα τη λίστα και ένα value, και θα δημιουργεί έναν νέο κόμβο με αυτό το value, θα τον εισαγάγει στη λίστα, και θα μας την επιστρέφει (θα μας επιστρέφει δηλαδή την αρχή της λίστας).
Το αν οι νέοι κόμβοι θα εισαγάγονται στην αρχή ή στο τέλος της λίστας είναι μια απόφαση που θα πρέπει να πάρουμε εμείς, ανάλογα με τις ανάγκες του project μας. Μπορεί μάλιστα να μας εξυπηρετεί να εισαγάγουμε τους νέους κόμβους ΑΠΕΥΘΕΙΑΣ ΤΑΞΙΝΟΜΗΜΕΝΟΥΣ στη σωστή τους θέση, δηλαδή είτε στην αρχή, είτε στη μέση, είτε στο τέλος της λίστας, είτε σε αύξουσα είτε σε φθίνουσα σειρά (αυτό μάλιστα αποτελεί κι ένα από τα σημαντικά πλεονεκτήματα των λιστών έναντι των πινάκων, στην ταξινομημένη δηλαδή εισαγωγή των στοιχείων).
Ανάλογα λοιπόν τις ανάγκες μας, ο κώδικας της συνάρτησης list_insert() θα είναι διαφορετικός. Μπορούμε να φτιάξουμε και περισσότερες της μιας συνάρτσησης, π.χ. μια που θα εισαγάγει κόμβους στην αρχή της λίστας, μια που θα τους εισαγάγει στο τέλος και μια που θα τους εισαγάγει απευθείας στη σωστή τους θέση, σε αύξουσα (ή σε φθίνουσα) σειρά.
Πριν περάσουμε όμως σε αυτά, προέχει να έχουν γίνει κατανοητά τα όσα έχω αναλύσει σε αυτήν εδώ τη δημοσίευση.
Απορίες, επισημάνσεις, διορθώσεις, κλπ πάντα ευπρόσδεκτα!
Παραθέτω και δυο εικόνες μιας απλά συνδεδεμένης λίστας (και οι δυο αναφέρονται στο ίδιο πράγμα, κρατήστε όποια καταλαβαίνετε καλύτερα, σύμφωνα με αυτά που είπαμε παραπάνω).
ΕΙΚΟΝΑ 1η - Όπου: Data εμείς έχουμε: value, κι όπου: Pointer εμείς έχουμε: next
ΕΙΚΟΝΑ 2η - Όπου: Head εμείς έχουμε: list
.
