Σε αυτό το σεμινάριο, θα μάθετε διαφορετικούς τύπους συνδεδεμένων λιστών. Επίσης, θα βρείτε την εφαρμογή της συνδεδεμένης λίστας στο C.
Πριν μάθετε για τον τύπο της συνδεδεμένης λίστας, βεβαιωθείτε ότι γνωρίζετε για τη δομή δεδομένων LinkedList.
Υπάρχουν τρεις κοινοί τύποι συνδεδεμένης λίστας.
- Συνδεδεμένη λίστα
- Διπλά συνδεδεμένη λίστα
- Κυκλική συνδεδεμένη λίστα
Συνδεδεμένη λίστα
Είναι το πιο κοινό. Κάθε κόμβος έχει δεδομένα και δείκτη στον επόμενο κόμβο.
Λίστα μεμονωμένη σύνδεση
Ο κόμβος παρουσιάζεται ως:
struct node ( int data; struct node *next; )
Μπορείτε να δημιουργήσετε μια τριμελή λίστα μεμονωμένων συνδέσεων ως:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Διπλά συνδεδεμένη λίστα
Προσθέτουμε ένα δείκτη στον προηγούμενο κόμβο σε μια λίστα διπλά συνδεδεμένων. Έτσι, μπορούμε να πάμε προς οποιαδήποτε κατεύθυνση: προς τα εμπρός ή προς τα πίσω.
Διπλά συνδεδεμένη λίστα
Ένας κόμβος παρουσιάζεται ως
struct node ( int data; struct node *next; struct node *prev; )
Μια τριμελής διπλά συνδεδεμένη λίστα μπορεί να δημιουργηθεί ως
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; one->prev = NULL; two->next = three; two->prev = one; three->next = NULL; three->prev = two; /* Save address of first node in head */ head = one;
Κυκλική συνδεδεμένη λίστα
Μια κυκλική συνδεδεμένη λίστα είναι μια παραλλαγή μιας συνδεδεμένης λίστας στην οποία το τελευταίο στοιχείο συνδέεται με το πρώτο στοιχείο. Αυτό σχηματίζει έναν κυκλικό βρόχο.
Κυκλική συνδεδεμένη λίστα
Μια κυκλική συνδεδεμένη λίστα μπορεί να είναι είτε μεμονωμένη είτε διπλή σύνδεση.
- για τη μοναδική συνδεδεμένη λίστα, ο επόμενος δείκτης του τελευταίου στοιχείου δείχνει το πρώτο στοιχείο
- Στη λίστα διπλά συνδεδεμένων, ο δείκτης του πρώτου στοιχείου δείχνει και το τελευταίο στοιχείο.
Μια τριμελής κυκλική λίστα που συνδέεται μεμονωμένα μπορεί να δημιουργηθεί ως:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = one; /* Save address of first node in head */ head = one;
