Ubuntu-gr Forum

ΑΠΛΑ ΣΥΝΔΕΔΕΜΕΝΕΣ ΛΙΣΤΕΣ (Singly Linked Lists) - ΜΕΡΟΣ 4ο

Προσθήκη Νέων Κόμβων στο Τέλος της Λίστας
ΣΥΝΑΡΤΗΣΗ: list_append

έγραψε:Μετάβαση στον Πίνακα Περιεχομένων

Σε συνέχεια του 3ου μέρους, ας δούμε τώρα δυο διαφορετικές υλοποιήσεις μιας συνάρτησης list_append( &list, value) που θα δημιουργεί έναν νέο κόμβο, θα εκχωρεί την τιμή value στο αντίστοιχο πεδίο του κόμβου και θα τον προσθέτει στο τέλος της λίστας.

Στην πρώτη υλοποίηση θα χρησιμοποιήσουμε τον κλασικό τρόπο, ο οποίος θα διατρέχει τη λίστα από την αρχή μέχρι το τέλος της, για να προσθέσει κατόπιν τον νέο κόμβο. Είναι φανερό πως κοστίζει πολύ σε ταχύτητα (αφού διατρέχει ολόκληρη τη λίστα). Τη λίστα θα την περνάμε BY REFERENCE και όπως θα δούμε θα χρειαστούμε 2 βοηθητικούς δείκτες για να κάνουμε την εισαγωγή.

Ας ονομάσουμε αυτή τη συνάρτηση: list_append_slow() κι ας δούμε τον κώδικά της...

Κώδικας: Επιλογή όλων


/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στο τέλος της λίστας
* με τον κλάσικό, αργό τρόπο που διατρέχει όλη την λίστα.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
Bool list_append_slow( Node **list, int value )
{
Node *head = NULL, *dummy = NULL; // βοηθητικοί δείκτες
Node *new = calloc(1, sizeof(struct node) ); // δημιουργία του νέου κόμβου
if ( !new ) // αποτυχία του calloc()
return FALSE; // πρόωρος τερματισμός

new->value = value; // αρχικοποίηση του νέου κόμβου
new->next = NULL;

if ( !*list ) { // εισαγωγή σε κενή λίστα
*list = new;
return TRUE;
}

// εισαγωγή σε μη κενή λίστα
head = dummy = *list; // τοποθέτηση βοηθητικών δεικτών στην αρχή της λίστας
while ( head ) { // ο head διατρέχει τη λίστα
dummy = head; // ο dummy "θυμάται" τον εκάστοτε προηγούμενο κόμβο
head = head->next;
}
dummy->next = new; // εισαγωγή του νέου κόμβου

return TRUE;
}


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

Ας επισημάνω όμως πως επειδή τον δείκτη list (που δείχνει στην αρχή της λίστας) τον περνάμε BY REFERENCE στη συνάρτηση, δεν μπορούμε να τον χρησιμοποιήσουμε για να διατρέξουμε τη λίστα (θα χάναμε την επαφή μας με την αρχή της λίστας, αφού BY REFERENCE σημαίνει κατ' ουσίαν πως δουλεύουμε απευθείας με την αυθεντική μεταβλητή και όχι με κάποιο αντίγραφό της). Για αυτό και τη λίστα τη διατρέχουμε με τον βοηθητικό, τοπικό δείκτη: head.

Επίσης, επειδή στις απλά συνδεδεμένες λίστες μόλις προσπεράσουμε έναν κόμβο δεν έχουμε τρόπο να γυρίσουμε πίσω (η δομή των κόμβων δεν έχει πεδίο: prev, έχει μόνο: next) χρειαζόμαστε έναν δεύτερο βοηθητικό δείκτη (τον dummy στην περίπτωσή μας) ο οποίος είναι πάντα "ένα βήμα πίσω" από τον head. Έτσι όταν ο head βρει NULL (το τέλος της λίστας) τότε ο dummy δείχνει στον τελευταίο κόμβο της λίστας.

Οπότε, για να εισαγάγουμε τον (ήδη δημιουργημένο & αρχικοποιημένο) νέο κόμβο: new στο τέλος της λίστας, μόλις τελειώσει το loop απλώς βάζουμε το πεδίο next του dummy να δείχνει στον νέο κόμβο... dummy->next = new;

Σε αυτό το σημείο, σαν εξάσκηση για τα όσα έχουμε πει μέχρι τώρα, μπορείτε να δοκιμάσετε μόνοι σας να τροποποιήσετε την παραπάνω συνάρτηση ώστε να δέχεται τον δείκτη list BY VALUE (αντί για BY REFERENCE) και να επιστρέφει στη main την ανανεωμένη λίστα, έτσι ώστε όταν την καλείτε στην main() να εκχωρείτε την τιμή επιστροφής της στον αυθεντικό δείκτη list.

Π.χ. ...

Κώδικας: Επιλογή όλων


...
int main( void )
{
Node *list=NULL;
...
list = list_append_slow( list, 52);
list = list_append_slow( list, 62);
list = list_append_slow( list, 72 );
...
list_print( list );
...
list_destroy( list );
return EXIT_SUCCESS;
}


Ως αντιπαραβολή, με το BY REFERENCE πέρασμα του list στην συνάρτηση (ο κώδικας που σας έδωσα έτοιμο) το παραπάνω παράδειγμα γράφεται ως εξής...

Κώδικας: Επιλογή όλων


...
int main( void )
{
Node *list=NULL;
...
list_append_slow( &list, 52);
list_append_slow( &list, 62);
list_append_slow( &list, 72 );
...
list_print( list );
...
list_destroy( list );
return EXIT_SUCCESS;
}


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

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

Θα μου πείτε, και γιατί να βάζουμε τους νέους κόμβους στο τέλος της λίστας και όχι στην αρχή της; Η απάντηση είναι πως δεν είναι ίδιες οι ανάγκες όλων των projects.

Π.χ. αν οι οι κόμβοι χαρακτηρίζονται από ημερομηνίες, τότε η εισαγωγή νέων κόμβων στην αρχή της λίστας όχι μόνο έχει νόημα, αλλά ενδέχεται να είναι και η πλέον ενδεδειγμένη. Για παράδειγμα, αν βάζουμε στην αρχή της λίστας την ημερομηνία που τροποποιείται από κάποιον χρήστη ένα αρχείο μαζί με το όνομα του χρήστη, τότε έχουμε αυτόματα ένα χρονολογικά ταξινομημένο log αρχείο για το ποιοι χρήστες και πότε τροποποίησαν το εν λόγω αρχείο (με τις πρόσφατες ημερομηνίες πρώτες).

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

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

Αυτό προϋποθέτει πως μαζί με τον δείκτη list θα πρέπει να διατηρούμε στην main() και έναν δείκτη που θα δείχνει ανά πάσα στιγμή στο τέλος της λίστας. Προφανώς θα πρέπει να τον περνάμε κι αυτόν μέσα στην συνάρτηση: list_append() μαζί με τον list.

Όταν χρησιμοποιούμε δύο δείκτες για την αρχή και το τέλος της λίστας, αυτόν που δείχνει στην αρχή συνήθως τον ονομάζουμε head, αλλά επειδή τον έχουμε συνηθίσει ως list σε αυτό το tutorial, θα τον αφήσω έτσι.

Παραθέτω λοιπόν τον κώδικα της γρήγορης συνάρτησης: list_append( &list, &tail, 52); στην οποία πλέον ούτε άλλους τοπικούς βοηθητικούς δείκτες χρειαζόμαστε, ούτε καν διατρέχουμε τη λίστα. Απλώς πάμε και βάζουμε το πεδίο next του tail να δείχνει στον νέο κόμβο new: (*tail)->next = new; και κατόπιν ενημερώνουμε τον tail ώστε να δείχνει στον νέο κόμβο, μιας και αυτός είναι πια ο τελευταίος στη λίστα: *tail = new;

Κώδικας: Επιλογή όλων


/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στο τέλος της λίστας
* με χρήση δείκτη tail για δραματική επίσπευση της ταχύτητας εισαγωγής.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
Bool list_append( Node **list, Node **tail, int value )
{
Node *new = calloc(1, sizeof(struct node) );
if ( !new )
return FALSE;

new->value = value;
new->next = NULL;

if ( !*list ) {
*list = *tail = new;
return TRUE;
}

(*tail)->next = new;
*tail = new;

return TRUE;
}

int main( void )
{
Node *list=NULL, *tail=NULL;
...
list_append( &list, &tail, 1);
list_append( &list, &tail, 2);
list_append( &list, &tail, 0);
...
list_destroy( list );
return EXIT_SUCCESS;
}


Και πάλι παρέλειψα επίτηδες ελέγχους αποτυχίας μετά από κάθε εισαγωγή, στο παραπάνω παράδειγμα, για να είναι πιο ευανάγνωστος ο κώδικας. Η λίστα που παράγει ο παραπάνω κώδικας είναι η εξής:

Κώδικας: Επιλογή όλων

1 -> 2 -> 0 -> NULL

με τον δείκτη list να δείχνει στον κόμβο του 1 και τον δείκτη tail να δείχνει στον κόμβο του 0.

Σε ότι αφορά τον κώδικα της συνάρτησης αυτής κάθε αυτής, ξεχωριστή αναφορά χρειάζεται η ειδική περίπτωση κατά την οποία ο νέος κόμβος πάει να προστεθεί σε κενή λίστα. Σε αυτή την περίπτωση, βάζουμε τόσο τον δείκτη *list όσο και τον δείκτη *tail να δείχνουν στον νέο κόμβο και τερματίζουμε τη συνάρτηση.

Σημειώστε επίσης πως τώρα που έχουμε να διαχειριστούμε 2 σημαντικούς δείκτες μέσα στη συνάρτηση, το πέρασμά τους BY REFERENCE είναι η ΠΡΟΦΑΝΗΣ υλοποίηση, μιας και οι συναρτήσεις μπορούν να έχουν μονάχα μια τιμή επιστροφής κι εμείς χρειαζόμαστε αλλαγμένους και τους 2 δείκτες όταν η ροή επιστρέψει στην main()

Ως μικρή επιβεβαίωση της κατανόησης του πως λειτουργεί η γρήγορη: list_append() αφήνω πάνω σας την προσθήκη σχολίων στον κώδικά της.

Πριν κλείσω το 4ο μέρος του tutorial, χρειάζεται μια ακόμα σημαντική διευκρίνηση...

Αν εκτός του στάνταρ δείκτη list (που δείχνει πάντα στην αρχή της λίστας) επιλέξετε να χρησιμοποιήσετε ΚΑΙ δείκτη tail που θα δείχνει ανά πάσα στιγμή στον τελευταίο κόμβο της λίστας, τότε θα πρέπει να ΤΡΟΠΟΠΟΙΗΣΕΤΕ ΚΑΙ τον κώδικα της συνάρτησης: list_prepend() περνώντας της ΚΑΙ τον δείκτη tail στα ορίσματά της.

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

Κώδικας: Επιλογή όλων


/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στην αρχή της λίστας.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
Bool list_prepend( Node **list, Node **tail, int value )
{
Node *new = calloc(1, sizeof(struct node) );
if ( !new )
return FALSE;

new->value = value;
if ( !*list ) {
new->next = NULL;
*list = *tail = new;
}
else {
new->next = *list;
*list = new;
}

return TRUE;
}


Προφανώς δεν μπορούμε να μπλέκουμε εκδόσεις συναρτήσεων που προβλέπουν μονάχα τη χρήση του δείκτη list με εκδόσεις που προβλέπουν τη χρήση και του list και του tail. Αν δηλαδή στο πρόγραμμά μας θελήσουμε να έχουμε και συνάρτηση list_prepend() και συνάρτηση list_append() θα πρέπει πρώτα να αποφασίσουμε αν θα χρησιμοποιήσουμε ΚΑΙ δείκτη tail στον τελευταίο κόμβο της λίστας μας και να υλοποιήσουμε ανάλογα τον κώδικα και των δυο συναρτήσεων.

Τελειώνοντας αυτό το 4ο μέρος, παραθέτω ολοκληρωμένο τελικό κώδικα που χρησιμοποιεί ΚΑΙ δείκτη tail στη λίστα, συνεχίζοντας από εκεί που σταματάει ο τελικός κώδικας του 3ου μέρους. Χρησιμοποιώ ΚΑΙ δείκτη tail, ενώ τις εκδόσεις των συναρτήσεων που δεν προβλέπουν χρήση του tail τις έχω συμπεριλάβει, αλλά ΑΠΕΝΕΡΓΟΠΟΙΗΜΕΝΕΣ μέσα σε σχετικά μπλοκ σχολίων.

Το πρόγραμμα πρώτα εισαγάγει τις τιμές 52 και 62 στο τέλος της λίστας ( list_append() ), μετά τις τιμές 72 και 82 στην αρχή της λίστας ( list_prepend() ). Κατόπιν τυπώνει το συνολικό πλήθος των στοιχείων και ξεχωριστά το 1ο και το τελευταίο στοιχείο της λίστας. Μετά τυπώνει όλα τα στοιχεία ένα προς ένα, καταστρέφει τη λίστα και τερματίζει.

Κώδικας: Επιλογή όλων


/*
* Singly Linked List Tutorial, Part 4
* (comments are in Greek)
*/

#include <stdio.h>
#include <stdlib.h>

typedef enum { FALSE=0, TRUE } Bool; // ο δικός μας πρόσθετος τύπος Boolean

typedef struct node { // δομή του κάθε κόμβου της λίστας
int value;
struct node *next;
} Node;

/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στην αρχή της λίστας.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
/*** ΑΠΕΝΕΡΓΟΠΟΙΗΜΕΝΟΣ ΚΩΔΙΚΑΣ (δεν προβλέπει *tail)

Bool list_prepend_notail( Node **list, int value )
{
Node *new = calloc(1, sizeof(Node) );
if ( !new )
return FALSE;

new->value = value;
new->next = (*list);
(*list) = new;

return TRUE;
}
***/

/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στο τέλος της λίστας
* με τον κλάσικό, αργό τρόπο που διατρέχει όλη την λίστα.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
/*** ΑΠΕΝΕΡΓΟΠΟΙΗΜΕΝΟΣ ΚΩΔΙΚΑΣ (δεν προβλέπει *tail)

Bool list_append_slow( Node **list, int value )
{
Node *head = NULL, *dummy = NULL; // βοηθητικοί δείκτες
Node *new = calloc(1, sizeof(struct node) ); // δημιουργία του νέου κόμβου
if ( !new ) // αποτυχία του calloc()
return FALSE; // πρόωρος τερματισμός

new->value = value; // αρχικοποίηση του νέου κόμβου
new->next = NULL;

if ( !*list ) { // εισαγωγή σε κενή λίστα
*list = new;
return TRUE;
}

// εισαγωγή σε μη κενή λίστα
head = dummy = *list; // τοποθέτηση βοηθητικών δείκτών στην αρχή της λίστας
while ( head ) { // ο head διατρέχει τη λίστα
dummy = head; // ο dummy "θυμάται" τον εκάστοτε προηγούμενο κόμβο
head = head->next;
}
dummy->next = new; // εισαγωγή του νέου κόμβου

return TRUE;
}
***/

/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στην αρχή της λίστας.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
Bool list_prepend( Node **list, Node **tail, int value )
{
Node *new = calloc(1, sizeof(struct node) );
if ( !new )
return FALSE;

new->value = value;
if ( !*list ) {
new->next = NULL;
*list = *tail = new;
}
else {
new->next = *list;
*list = new;
}

return TRUE;
}

/* ------------------------------------------------------------------
* Δημιουργία και εισαγωγή νέου κόμβου με τιμή value, στο τέλος της λίστας
* με χρήση δείκτη tail για δραματική επίσπευση της ταχύτητας εισαγωγής.
* Επιστρέφει FALSE σε περίπτωση αποτυχίας της calloc(), αλλιώς TRUE
* ------------------------------------------------------------------
*/
Bool list_append( Node **list, Node **tail, int value )
{
Node *new = calloc(1, sizeof(struct node) );
if ( !new )
return FALSE;

new->value = value;
new->next = NULL;

if ( !*list ) {
*list = *tail = new;
return TRUE;
}

(*tail)->next = new;
*tail = new;

return TRUE;
}

/* ------------------------------------------------------------------
* Μέτρημα κι επιστροφή του πλήθους κόμβων της λίστας
* ------------------------------------------------------------------
*/
int list_len( Node *list )
{
register int i = 0;
for (i=0; list; i++) // ισοδυναμεί με: for (i=0; list != NULL; i++)
list = list->next;

/** ΕΝΑΛΛΑΚΤΙΚΟΣ ΚΩΔΙΚΑΣ
while ( list ) { // ισοδυναμεί με: while ( list != ΝULL ) {
list = list->next;
i++;
}
**/
return i;
}

/* ------------------------------------------------------------------
* Τύπωμα του πεδίου value όλων των κόμβων της λίστας
* ------------------------------------------------------------------
*/
void list_print( Node *list )
{
while ( list ) {
printf("%d ", list->value);
list = list->next;
}
putchar('\n'); // αλλαγή γραμμής

return;
}

/* ------------------------------------------------------------------
* Απελευθέρωση της μνήμης που έχουμε δεσμεύσει για κάθε κόμβο της λίστας
* ------------------------------------------------------------------
*/
void list_destroy( Node *list )
{
if ( !list ) // ισοδυναμεί με: if ( list == NULL )
return;

Node *dummy = NULL;
while ( list ) { // ισοδυναμεί με: while ( list != NULL ) {
dummy = list->next;
free( list );
list = dummy;
}

return;
}

// -------------------------------------------------------------------
int main ( void )
{
Node *list = NULL, *tail = NULL;

// δημιουργία και εισαγωγή 1ου στοιχείου στο ΤΕΛΟΣ
if ( list_append( &list, &tail, 52) == FALSE ) { // αποτυχία
puts("*** out of memory, aborting program");
exit( EXIT_FAILURE );
}

// δημιουργία και εισαγωγή 2ου στοιχείου στο ΤΕΛΟΣ
if ( list_append( &list, &tail, 62) == FALSE) { // αποτυχία
puts("*** out of memory, aborting program");
list_destroy( list) ; // καταστροφή προηγούμενων κόμβων
exit( EXIT_FAILURE );
}

// δημιουργία και εισαγωγή 3ου στοιχείου στην ΑΡΧΗ
if ( list_prepend( &list, &tail, 72) == FALSE) { // αποτυχία
puts("*** out of memory, aborting program");
list_destroy( list) ; // καταστροφή προηγούμενων κόμβων
exit( EXIT_FAILURE );
}

// δημιουργία και εισαγωγή 4ου στοιχείου στην ΑΡΧΗ
if ( list_prepend( &list, &tail, 82) == FALSE) { // αποτυχία
puts("*** out of memory, aborting program");
list_destroy( list) ; // καταστροφή προηγούμενων κόμβων
exit( EXIT_FAILURE );
}

// καταμέτρηση και τύπωμα του πλήθους των κόμβων στη λίστα
printf("The list consists of %d nodes\n", list_len( list) );

// τύπωμα των πεδίων value του 1ου και του τελευταίου κόμβου
printf("(head = %d, tail = %d)\n", list->value, tail->value);

// τύπωμα των στοιχείων της λίστας
list_print( list );

// αποδέσμευση όλων των κόμβων από τη μνήμη
list_destroy( list );

fflush(stdin); getchar();
exit( EXIT_SUCCESS );
}


Μπορείτε να δείτε τον κώδικα με syntax-highlighting, δείγμα εξόδου και σύνδεσμο κατεβάσματος εδώ: http://codepad.org/3WR5kyQR

Σε αυτό το σημείο δεν ξέρω αν είναι καλή ιδέα αν πρέπει να συνεχίσω με τα tutorials ή να σταματήσω μέχρι να μου δώσετε το ΟΚ για να πάμε παρακάτω.

Προσωπικά θέλω να αναλύσω και κώδικα που εισαγάγει τους νέους κόμβους απευθείας ταξινομημένους στη σωστή τους θέση, καθώς επίσης και μια λίγο πιο προχωρημένη υλοποίηση η οποία αντί να κρατάει χύμα στη main() τους δείκτες list και tail, να τους "συγκεντρώνει" σε μια ξεχωριστή δομή την οποία και θα περνάει κατόπιν στις διάφορες συναρτήσεις.

Όπως και την αντικατάσταση της συνάρτησης list_len() που ... σέρνεται, ειδικά όταν έχουμε τεράστιες λίστες (αφού για να μετρήσει το πλήθος των στοιχείων διατρέχει όλους τους κόμβους έναν προς έναν). Διατηρώντας ξεχωριστή μεταβλητή για το πλήθος των στοιχείων που θα την αυξάνουμε κατά 1 μέσα στις συναρτήσεις εισαγωγής κάθε φορά που προσθέτουμε έναν νέο κόμβο (κι αντίστοιχα μειώνοντάς την κατά 1 κάθε φορά που διαγράφουμε έναν κόμβο) ο χρόνος που θα χρειαζόμαστε για να βρούμε το πλήθος των στοιχείων της λίστας, από O(n) που είναι τώρα με την list_len() θα πέσει σε O(1)... που σημαίνει θα είναι απλά η εξέταση της τιμής μιας και μόνο μεταβλητής.

Μια τέτοια έξτρα δομή, θα μετατρέψει τους ορισμούς μας ως εξής...

Κώδικας: Επιλογή όλων


typedef struct node {
int data;
struct node *next;
} Node;

typedef struct {
Node *head, *tail;
int len;
} List;


και προφανώς χρειάζεται να τροποποιήσουμε και τον κώδικα των συναρτήσεων.

Π.χ. αντί για...

Κώδικας: Επιλογή όλων

Bool list_append( Node **list, Node **tail, int *len, int value);

(όπου len, η αυθεντική μεταβλητή της main() που θα κρατάει το πλήθος των στοιχείων)

θα έχουμε...

Κώδικας: Επιλογή όλων

Bool list_append( List *list, int data);

με τις ανάλογες φυσικά τροποποιήσεις μέσα στον κώδικα της συνάρτησης.

Το ερώτημα είναι, είμαστε έτοιμοι για αυτό ή χρειάζεται ένα διάλειμμα για να εμπεδωθούν όσα έχει καλύψει μέχρι στιγμής το tutorial; Ή να τα γράψω έτσι κι αλλιώς να υπάρχουν κι ο καθένας να τα ακολουθήσει με τους δικούς του ρυθμούς;

Για παράδειγμα, στο σημείο που έχουμε φτάσει μέχρι τώρα, δεν είναι ακόμα εύκολο να παρακολουθήσει κανείς tutorials από real-life εφαρμογή των λιστών, όπως για παράδειγμα αυτό εδώ που εξηγεί πως μπορεί να φτιάξει κανείς game objects με λίστες και να τα εμφανίσει γραφικώς και στην οθόνη: http://www.gamedev.net/page/resources/_ ... ects-r2041