Существует три распространенных типа связанного списка.
- Единственный связанный список
- Двусвязный список
- Круговой связанный список
Единственный связанный список
Это самый распространенный. Каждый узел имеет данные и указатель на следующий узел.
Где адрес первого узла специальное имя, называемое HEAD.
На последний узел в связанном списке указывает NULL.
Узел представлен как:
struct node {
int data;
struct node *next;
}
Трехэлементный односвязный список может быть создан как:
/* Инициализируем узлы */ 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;
Двусвязный список
Мы добавляем указатель на предыдущий узел в двусвязном списке. Таким образом, мы можем идти в любом направлении: вперед (next) или назад (prev).
Узел представлен как:
struct node {
int data;
struct node *next;
struct node *prev;
}
Двусвязный список из трех участников может быть создан как:
/* Инициализируем узлы */ 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;
Круговой связанный список
Круговой связанный список - это вариант связанного списка, в котором последний элемент связан с первым элементом. Это образует круговую петлю.
Круговой связанный список может быть либо односвязным, либо двусвязным.
- Для односвязного списка указатель next последнего элемента указывает на первый элемент;
- В двусвязном списке указатель prev первого элемента также указывает на последний элемент.
Круговой односвязный список из трех членов может быть создан как:
/* Инициализируем узлы */ 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;
