В этом руководстве вы познакомитесь с различными типами связанного списка. Также вы найдете реализацию связанного списка на 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;
