W tym samouczku nauczysz się różnych typów list połączonych. Implementację powiązanej listy znajdziesz również w C.
Zanim dowiesz się o typie połączonej listy, upewnij się, że znasz strukturę danych LinkedList.
Istnieją trzy popularne typy list połączonych.
- Lista pojedynczo połączona
- Lista podwójnie połączona
- Lista połączona cyklicznie
Lista pojedynczo połączona
To jest najczęściej. Każdy węzeł ma dane i wskaźnik do następnego węzła.
Lista pojedynczo połączona
Węzeł jest reprezentowany jako:
struct node ( int data; struct node *next; )
Trzyelementową listę połączoną pojedynczo można utworzyć jako:
/* 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;
Lista podwójnie połączona
Dodajemy wskaźnik do poprzedniego węzła na liście podwójnie połączonej. W ten sposób możemy iść w dowolnym kierunku: do przodu lub do tyłu.
Lista podwójnie połączona
Węzeł jest reprezentowany jako
struct node ( int data; struct node *next; struct node *prev; )
Trzyelementową listę podwójnie połączoną można utworzyć jako
/* 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;
Lista połączona cyklicznie
Lista połączona cyklicznie to odmiana listy połączonej, w której ostatni element jest połączony z pierwszym elementem. To tworzy okrągłą pętlę.
Lista połączona cyklicznie
Lista połączona cyklicznie może być połączona pojedynczo lub podwójnie.
- w przypadku listy pojedynczo połączonej następny wskaźnik ostatniej pozycji wskazuje na pierwszą pozycję
- Na liście podwójnie połączonej wskaźnik poprzedni pierwszego elementu wskazuje również na ostatni element.
Trzyelementową okrągłą listę pojedynczo połączoną można utworzyć jako:
/* 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;
