Типы связанного списка - односвязные, двусвязные и круговой

Типы связанного списка, алгоритм

Существует три распространенных типа связанного списка.

• Единственный связанный список
• Двусвязный список
• Круговой связанный список

Единственный связанный список

Это самый распространенный. Каждый узел имеет данные и указатель на следующий узел.

Где адрес первого узла специальное имя, называемое 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;