Связные списки
В этом руководстве вы познакомитесь с различными типами связанных списков и узнаете, как реализовать его на Си.
Существует три основных типа связанных списков.
- Односвязный список.
- Двусвязный список.
- Кольцевой связный список.
Односвязный список
Это самый распространенный тип связных списков. В каждом узле есть указатель на следующий узел.
Узел в этом случае выглядит вот так:
struct node {
int data;
struct node *next;
}
Создадим односвязный список из 3 членов на Си:
/* Объявляем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Присваиваем значения */
one->data = 1;
two->data = 2;
three->data = 3;
/* Связываем узлы */
one->next = two;
two->next = three;
three->next = NULL;
/* Сохраняем «адрес» первого узла в корне */
head = one;
Двусвязный список
Если добавить указатель на предыдущий узел, получится двусвязный список. В нём можно «двигаться» в обоих направлениях: и вперед, и назад.
Поэтому двусвязный список еще называют двунаправленным.
Узел в этом случае выглядит вот так:
struct node {
int data;
struct node *next;
struct node *prev;
}
Создадим двусвязный список из 3 членов на Си:
/* Объявляем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Присваиваем значения */
one->data = 1;
two->data = 2;
three->data = 3;
/* Связываем узлы */
one->next = two;
one->prev = NULL;
two->next = three;
two->prev = one;
three->next = NULL;
three->prev = two;
/* Сохраняем «адрес» первого узла в корне */
head = one;
Кольцевой связный список
В кольцевом связанном списке последний элемент связан с первым элементом.
Кольцевой связный список может быть как односвязным, так и двусвязным.
-
В односвязном указатель на следующий элемент последнего узла указывает на первый узел.
-
В двусвязном указатель на предыдущий элемент первого узла указывает на последний узел.
Создадим кольцевой односвязный список на Си:
/* Объявляем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Присваиваем значения */
one->data = 1;
two->data = 2;
three->data = 3;
/* Связываем узлы */
one->next = two;
two->next = three;
three->next = one;
/* Сохраняем «адрес» первого узла в корне */
head = one;