Συνδεδεμενες λιστες και ελεγχος τελευταιου στοιχειου

[migf1]

Thx φίλε Star_Light για τα καλά σου λόγια, αλλά δεν είναι κάτι το εντυπωσιακό αυτός ο κώδικας. Μια απλή υλοποίηση απλής συνδεδεμένης λίστας είναι, χωρίς κάποιον εντυπωσιακό αλγόριθμο ή κάποια εξεζητημένη τεχνική. Οι απλές συνδεδεμένες λίστες είναι στοιχειώδης δομή για όποιον ασχολείται με προγραμματισμό και αποτελεί ένα από τα πρώτα πράγματα που μαθαίνει κανείς στις δομές δεδομένων.

Αυτό που ίσως δεν είναι τόσο συνηθισμένο, είναι το πέρασμα της λίστας by reference στην list_insert(), που είναι και ο βασικός λόγος που την έχω κάνει να επιστρέφει Boolean τιμή. Αυτή την υλοποίηση είναι πιο εύκολο να την παρακολουθήσει κάποιος που προέρχεται από άλλες γλώσσες, διότι όταν καλείται η συνάρτηση στην main() ο τελεστής & μπροστά από το όρισμα list κάνει και συντακτικά σαφές πως η λίστα αλλάζει μέσα στην list_insert().

Μια εναλλακτική υλοποίηση, και μάλλον πιο συνηθισμένη, είναι η λίστα να περνιέται by value μέσα στην list_insert() αλλά τότε η συνάρτηση θα πρέπει να επιστρέφει την αρχή της λίστας, η οποία θα πρέπει κατόπιν να εκχωρηθεί στον δείκτη της λίστας στην main().

Δηλαδή:

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


List *list_insert( List *list, int data)
{
... // παραλλαγμένος κώδικας
return list;
}

// -------------------------------------------------------------------------------
int main( void )
{
int data = ...;
List *list = NULL;
list = list_insert( list, data );
...
list_destroy( &list );
...
}


Ο "παραλλαγμένος κώδικας" αυτής της εκδοχής της list_insert() είναι πιο σύντομος και πιο... C like (αν θέλετε να σας τον γράψω κι αυτόν), αλλά έχει το επιπλέον overhead στην main(), όπως εξήγησα πριν. Όλο μαζί, μάλλον μπερδεύει περισσότερο τον αρχάριο συγκριτικά με τον κώδικα που έδωσα παραπάνω (αν κι αυτός ενδέχεται να μπερδέψει τοπικά τον αρχάριο, λόγω του διπλού δείκτη που χρησιμοποιεί μέσα στην συνάρτηση).

Off topic:
Σε ότι αφορά τώρα το αποθετήριο, ειλικρινά δεν καταλαβαίνω γιατί θα πρέπει να κάτσω να μάθω κάτι που δεν μου χρειάζεται ούτε προσωπικά ούτε εξυπηρετεί κατά την άποψή μου καλύτερα τις ανάγκες παρουσίασης κώδικα σε ένα προγραμματιστικό φόρουμ.

Δηλαδή όλοι όσοι διαβάζουν το φόρουμ αυτό για να μπορέσουν να αποκτήσουν πρόσβαση στους κώδικες που παρουσιάζουμε (που ουσιαστικά είναι snippets) θα πρέπει πρώτα να κάτσουν να μάθουν πως δουλεύουν τα αποθετήρια; Το βρίσκω παράλογο!

Η προσωπική μου άποψη είναι πως τόσο το code-tag του φόρουμ για μικρά αποσπάσματα, όσο και sites όπως τα ideone.com & codepad.org για μεγαλύτερα, είναι υπερ-αρκετά για τους σκοπούς που εξυπηρετεί ένα γενικό φόρουμ προγραμματισμού, όπως αυτό.

Αν ήμασταν μια ομάδα ανάπτυξης λογισμικού που είχαμε κοινό στόχο την ανάπτυξη μιας εφαρμογής, για την οποία ο καθένας από εμάς είχε αναλάβει να γράψει κώδικα σε επιμέρους τομείς, τα οποία μέρη έπρεπε να εξετάζουν ή/και να χρησιμοποιούν και τα υπόλοιπα μέρη του team, τότε ναι το καταλαβαίνω να χρησιμοποιούσαμε και αποθετήρια και revision control systems (και τηλεδιασκέψεις :p) και να καθόμουν να μάθω ότι χρειαζόταν για την επίτευξη του κοινού τελικού στόχου.

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

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

[Star_Light]

ΛΟιπον εγω εκατσα και διαβασα τον κωδικα σου και εχω βαλει τα σχολια. Απλα σε καποια φαση οπως ειπες και παραπανω χρησιμοποιεις μεσα στην συναρτηση σαν ορισμα εναν δεικτη απο δεικτες **list αυτο νομιζω οτι το κανεις πιο πολυ για να διαγράψεις εναν κομβο. Επειδη οταν διαγραφουμε εναν κομβο απλα κανουμε τον δεικτη να δειχνει στον επομενο του επομενου και αφαιρουμε τον επομενο. A->B->C : B: next C : ο επομενος του τρεχοντα επομενου next->C.next οποτε εφοσον ο next ειναι ηδη δείκτης ουσιαστικα κανεις αυτο το κολπο επειδη παλι θες να δειξεις σε εναν δεικτη. Α->C Σε κατανοησα σωστα? Eπισης σε καποια σημεια χρησιμοποιεις και καποιον δεικτη ενδιαμεσα για να μην χασεις την τιμη ?

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

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

typedef enum { FALSE=0, TRUE } Bool; /*Orizetai metavliti tipou enwsis Bool h aparithmisi
ksekinaei apo to FALSE=0 opote kai to TRUE einai 1*/

typedef struct node {
int data; /*Ta dedomena tou komvou */
struct node *next; /*O deiktis pros ton epomeno komvo */
} List;

/* ------------------------------------------------------------------
* Insert 'data' as Last node of 'list'
*/
Bool list_insert( List **list, int data )
{
List *head = NULL, *dummy = NULL;
List *new = calloc(1, sizeof(struct node) );
if ( !new )
return FALSE; /* H calloc apetuxe */

new->data = data; /* O 1os komvos */
new->next = NULL; /* O epomenos deiktis einai NULL (mexri na dimiourgi8ei kainourgios komvos) */

if ( !*list ) { /*An o deiktis listas dn dinei egkuri dieuthinsi */
*list = new; /* 8ese ton list na deixnei ston new */
return TRUE; /* epestrepse TRUE */
}

head = dummy = *list;
while ( head ) {
dummy = head;
head = head->next; /* O HEAD deixnei ston A px kai o new pou prokeitai na bei ston A? */
}
dummy->next = new;

return TRUE;
}

/* ------------------------------------------------------------------
* Print 'list' contents
*/
void list_print( List *list )
{
if ( !list )
return;

while ( list ) { /* Oso o deiktis dinei mi mideniki timi */
printf("%d ", list->data ); /* Ektupwse ta data tou komvou */
list = list->next; /* Pleon o deiktis deixnei ston epomeno komvo */
}

return;
}
/* ------------------------------------------------------------------
* Free memory reserved for 'list'
*/
void list_destroy( List **list )
{
if ( !*list )
return;

List *dummy = NULL;
while ( *list ) {
dummy = *list; /* Estw A=B kai B=C free(A) opote menei B=C */
*list = (*list)->next; /*Thetw ton deikti na deixnei ston amesws epomeno (C) gia diagrafi tis listas */
free( dummy ); /*Apodesmeusi mnimis gia dummy <=> o dummy diagrafetai */
}

return;
}

/* ------------------------------------------------------------------
*
*/
int main( void )
{
register int i=0; /* DHlwsi i san kataxwriti gia taxutita ston kwdika */
List *list = NULL; /* Dilwsi deikti tupou Listas me timi NULL */


for (i=19; i>9; i--) /* 10 ektupwseis komvwn */
list_insert( &list, i); /* Kaleitai h sunartisi list_insert */

list_print( list ); /* Klhsh tis list_print me orisma list epeidi eine aplos deiktis */
list_destroy( &list ); /* Klhsh tis list_destroy me orisma &list epeidi einai deiktis apo deiktes */

fflush(stdin); getchar();
return 0;
}


σΤΑ ΣΗμεια που δεν εχω βαλει σχολια σε εχω χασει λιγο αλλα θα τα ξανακοιταξω πριν σε ρωτησω.

[migf1]

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

Εν τάχει, ναι ο dummy είναι για να κρατάει κάπου τον προηγούμενο κόμβο όταν ο head πάει στον επόμενο (head->next). Σχετικά με τον διπλό δείκτη, δεν το κάνω για την διαγραφή κόμβων, το κάνω για να δουλεύω απευθείας στη μνήμη που βρίσκεται η αρχή της λίστας, ώστε να μη χρειάζεται να την επιστρέφω από την συνάρτηση (κατά πλήρη αντιστοιχία δηλαδή του pass by reference που κάνουμε σε οποιαδήποτε μεταβλητή, όταν θέλουμε να διατηρήσει την τιμή της και μετά το πέρας της συνάρτησης).

[Star_Light]

ειναι υποχρεωτικο να χρησιμοποιησει συναρτησεις καποιος για να υλοποιήσει την δημιουργια , την εισαγωγη και την διαγραφη????
Κοιτα οι μονες μου αποριες οπως εχω πει και στον λινους ειναι σε 2-3 δεικτες... απλα σε τετοια προγραμματα ειναι ευκολο να χασεις
την μπαλα.

[simosx]

ΥΓ. Αν ενδιαφέρει το φόρουμ μπορώ να σας δώσω και κώδικα π.χ. για ταξινομημένη εισαγωγή κόμβων στη λίστα (είτε σε αύξουσα είτε σε φθίνουσα σειρά). Ή για παράδειγμα, στο νήμα με το παιχνίδι της Ξερής έχω γράψει στο αρχείο: stack.c τις βασικές συναρτήσεις για τη διαχείριση στοίβας.

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

Χεχε, είναι προ-απαιτούμενο δηλαδή;

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

Για την πρόταση που κάνεις, μπορεί να υλοποιηθεί αποδοτικά όταν ο κώδικας μπει σε κάποιο αποθετήριο πηγαίου κώδικα.
Έτσι, οι άμεσα ενδιαφερόμενοι αλλά και τρίτα μέλη που θα ενδιαφερθούν στο μέλλον, θα είναι σε θέση να παρακολουθήσουν την εξέλιξη του κώδικα, εύκολα και ποιοτικά.
Θα είναι πιο εύκολο να συνεισφέρει κάποιος τρίτος με την ενεργοποίηση συνεργατών.

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

Αυτό που βλέπω είναι ότι δε γνωρίζεις ακόμα τα πλεονεκτήματα που προσφέρει π.χ. το git με το GitHub.com, και πως μπορεί να βοηθήσει τα άτομα που μαθαίνουν προγραμματισμό.
Για παράδειγμα, να ένα πρόγραμμα, https://github.com/simos/lotto/blob/master/lotto.py
Να όλα τα commit (προσθήκες στον κώδικα): https://github.com/simos/lotto/commits/master
Να μια αλλαγή όπου διορθώνει ένα σφάλμα, https://github.com/simos/lotto/commit/5 ... becf742b88

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

[migf1]

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

Σου παραθέτω ξανά τον κώδικα, γεμάτο από σχόλια στα Ελληνικά (σχεδόν σε κάθε γραμμή). Όπου έχεις απορία, γράψε συγκεκριμένα κι αναλυτικά τι θα ήθελες να ξεκαθαρίσουμε (έστω κι αν χρειαστεί να το πάμε γραμμή-γραμμή )

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


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

typedef enum { FALSE=0, TRUE } Bool; // πρόσθετος τύπος δεδομένων για Boolean τιμές
// (εφόσον FALSE=0, το TRUE ισούται με 1)

typedef struct node { // δομή δεομέμων για κάθε κόμβο της λίστας
int data; // τα δεδομένα του κόμβου
struct node *next; // δείκτης προς τον επόμενο κόμβο
} List;

/* ------------------------------------------------------------------
* Insert 'data' as Last node of 'list'
*/
Bool list_insert( List **list, int data )
{
List *head = NULL, *dummy = NULL; // αρχικοποίηση 2 βοηθητικών δεικτών
List *new = calloc(1, sizeof(struct node) ); // δέσμευση μνήμης για νέο κόμβο
if ( !new ) // αποτυχία της calloc (new == NULL)
return FALSE;

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

if ( !*list ) { // η λίστα είναι κενή (*list == NULL)
*list = new; // κάνε τον νέο κόμβο αρχή της λίστας
return TRUE;
}

/* Εισαγωγή του νέου κόμβου στο τέλος της λίστας.
*
* Αλγοριθμος:
* Ο head διατρέχει τη λίστα μέχρι το τέλος της (μέχρι δλδ ο head να βρει NULL)
* κάθε φορά που ο head πάει στον επόμενο κόμβο, ο dummy δείχνει στον κόμβο που
* ήταν ο head πριν πάει στον επόμενο. Όταν τελειώσει το loop, ο head είναι
* NULL και ο dummy δείχνει στον τελευταίο κόμβο της λίστας
*/
head = dummy = *list; // οι head & dummy δείχνουν στην αρχή της λίστας
while ( head ) { // όσο ο head δεν είναι NULL
dummy = head; // εκχώρησέ τον στον dummy (θυμήσου τον)
head = head->next; // μετακίνησε τον στον επόμενο κόμβο
}

// σε αυτό το σημείο ο dummy δείχνει στον τελευταίο κόμβο της λίοτας
dummy->next = new; // κάνε τον να δείχνει στον new

return TRUE;
}

/* ------------------------------------------------------------------
* Print 'list' contents
*/
void list_print( List *list )
{
if ( !list ) // η λίστα είναι κενή
return;

while ( list ) { // όσο ο list δεν είναι NULL
printf("%d ", list->data ); //τύπωσε τα δεδομένα του κόμβου του list
list = list->next; // μετακίνησε τον list στον επόμενο κόμβο
}

return;
}
/* ------------------------------------------------------------------
* Free memory reserved for 'list'
*/
void list_destroy( List **list )
{
if ( !*list ) // η λίστα είναι κενή
return;

List *dummy = NULL; // αρχικοποίηση βοηθητικού δείκτη
while ( *list ) { // όσο ο *list δεν είναι NULL
dummy = *list; // εκχώρησέ τον στον dummy (θυμήσου τον)
*list = (*list)->next; // μετακίνησε τον στον επόμενο κόμβο
free( dummy ); // αποδέσμευσε τον προηγούμενο κόμβο
}

return;
}

/* ------------------------------------------------------------------
*
*/
int main( void )
{
register int i=0; // προσωρινός μετρητής
List *list = NULL; // αρχικοποίηση της λίστας

// εισαγωγή 10 ακεραίων στην λίστα (από το 19 έως το 9)
for (i=19; i>9; i--)
list_insert( &list, i);

list_print( list ); // τύπωμα των περιεχομένων της λίστας
list_destroy( &list ); // αποδεσμευση μνήμης για όλους τους κόμβους της λίστας

fflush(stdin); getchar();
return 0;
}


ειναι υποχρεωτικο να χρησιμοποιησει συναρτησεις καποιος για να υλοποιήσει την δημιουργια , την εισαγωγη και την διαγραφη????
Κοιτα οι μονες μου αποριες οπως εχω πει και στον λινους ειναι σε 2-3 δεικτες... απλα σε τετοια προγραμματα ειναι ευκολο να χασεις
την μπαλα.

ΥΓ. Σίμο ναι, αισθάνομαι πως με πιέζεις και με αυτό τον τρόπο ενεργοποιείς όλα τα αρνητικά μου αντανακλαστικά. Κάποια στιγμή, όπως σου έγραψα, θα κάτσω να μάθω κάποιο από τα αποθετήρια (όχι κατά ανάγκη το git). Αυτό όμως θα συμβεί όταν θα αισθανθώ ότι μου χρειάζεται και όχι επειδή προσπαθεί να μου το επιβάλλει κάποιος. Ελπίζω να με κατανοείς, κι εννοείται πως δεν έχω κανένα πρόβλημα να το χρησιμοποιείτε όσοι θεωρείτε πως σας διευκολύνει

[Star_Light]

Κοιτα καταρχην δεν μπορω να καταλαβω πως δεχεται ο δεικτης αυτο

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

List *dummy = NULL;

ενα αυτο και δευτερον απλα για ευκολια πηγα να το κανω πολυ απλα για να μαθω αρχικα

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

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

/* List of integers */
struct s_list {
int val; /* Integer value */
struct s_list *next;
};

int main()
{
struct s_list *head, *p;
int n;
int i;

head = NULL;
/* Read list elements */
for(i=0; i<4; i++){
p = (struct s_list *)malloc(sizeof(struct s_list));
p->val = n;
p->next = head;
head = p;
}


printf("\nStarting output:\n");
/* Print list elements */
for(p = head; p; p = p->next)
printf("%d\n", p->val);
}


ας πουμε αυτο μου βγαζει 0 -> 0 -> 0 -> 0 εχω καποιο προβλημα με τα data?
Η'απλα δεν ενωνω τοους κομβους αποτελεσματικα οποτε απλα επαναλαμβανει
τον αρχικο? Παλουκακι οι λιστες εχω αρχισει και κουραζομαι :/

ευχαριστω για την υπομονη σου παντως

[Star_Light]

απλα το προβλημα για μενα στον δικο σου κωδικα ειναι οτι κανεις κατι αεροπλανικα με τους δεικτες και εγω εχω βασικη γνωση για αυτους. ΟΠοτε λογικο να χανομαι... Αν και αρχικα οκ επιασα ως ενα βαθμο τον κωδικα παντως πολυ εξυπνος ειδικα εκει στην while ( list ) ουσιαστικα οριζεις να σταματησει η while οταν θα βρει μια τιμη που δεν ειναι εγκυρη βασικα εξ ορισμου γινεται αυτο οποτε λες ποια τιμη δεν μου κανει εμενα? Η NULL οκ αυτο συμπιπτει και με τον τερματισμο της while. Εγω να σου πω την αληθεια θα το εκανα με for και θα το εκανα ετσι ->

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

for(ptr=head_ptr; ptr->next_ptr!=NULL ptr=ptr->next_ptr)

[migf1]

Κοιτα καταρχην δεν μπορω να καταλαβω πως δεχεται ο δεικτης αυτο

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

List *dummy = NULL;

Αν το καταλαβαίνεις καλύτερα, το παραπάνω ισοδυναμεί με αυτό εδώ:

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


List *dummy;
dummy = NULL;


ενα αυτο και δευτερον απλα για ευκολια πηγα να το κανω πολυ απλα για να μαθω αρχικα

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


[snip]


ας πουμε αυτο μου βγαζει 0 -> 0 -> 0 -> 0 εχω καποιο προβλημα με τα data?
Η'απλα δεν ενωνω τοους κομβους αποτελεσματικα οποτε απλα επαναλαμβανει
τον αρχικο? Παλουκακι οι λιστες εχω αρχισει και κουραζομαι :/

ευχαριστω για την υπομονη σου παντως

Δώσε μου 5-10 λεπτάκια να πάω μια... τουαλέτα (αλήθεια ) κι άλλα 5-10 να δω τι κάνει ο κώδικά σου κι επιστρέφω.

[migf1]

Μια χαρά δουλεύει ο κώδικά σου, αλλά αντί για...

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


p->val = n;


υποθέτω ήθελες να γράψεις...

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


p->val = i;


ή αν όντως ήθελες να βάλεις n, αρχικοποίησέ το σε μια τιμή όταν το πρωτο-ορίζεις, γιατί χωρίς αρχικοποίηση ο κάθε compiler βάζει ότι θέλει ως αρχική τιμή.

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

Με τον... δικό μου τρόπο, αυτό γράφεται ως εξής:

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


/* ------------------------------------------------------------------
* Insert 'data' as 'list's First node
*/
Bool list_insfirst( List **list, int data )
{
List *new = calloc(1, sizeof(struct node) );
if ( !new )
return FALSE;

new->data = data;
new->next = *list;
*list = new;

return TRUE;
}


που ουσιαστικά κάνει το ίδιο πράγμα

Τώρα, σχετικά με το for-loop, όσο δεν σου χρειάζεται να "θυμάσαι" τον εκάστοτε προηγούμενο κόμβο όταν μετακινείσαι στον επόμενο, τότε το for είναι ok. Αν όμως χρειάζεται να "θυμάσαι" τον εκάστοτε προηγούμενο κόμβο (όπως π.χ. όταν πρέπει να εισαγάγεις τους νέους κόμβους στο τέλος της λίστας ή να τους εισαγάγεις ταξινομημένα απευθείας στη σωστή τους θέση), τότε το while είναι σαφώς πιο κατάλληλο, και κυρίως πιο κατανοητό.

Ένας άλλος τρόπος για να μη χρειάζεται να "θυμάσαι" τον εκάστοτε προηγούμενο κόμβο όταν διατρέχεις τη λίστα, είναι αντί για απλή συνδεδεμένη λίστα να χρησιμοποιήσεις διπλά συνδεδεμένη λίστα (doubly linked list), στην οποία ο κάθε κόμβος εκτός από δείκτη next έχει και δείκτη prev.