Linked list types - singly linked, doubly linked and circular

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

There are three common types of linked list.

• Single linked list
• doubly linked list
• Circular linked list

Single linked list

This is the most common. Each node has data and a pointer to the next node.

Where the address of the first node is a special name called HEAD.
The last node in the linked list is pointed to by NULL.

The node is represented as:

struct node {
    int data;
    struct node *next;
}

A three-element singly linked list can be created as:

/* Инициализируем узлы */
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;

Doubly linked list

We add a pointer to the previous node in the doubly linked list. Thus, we can go in any direction: forward (next) or backward (prev).

The node is represented as:

struct node {
    int data;
    struct node *next;
    struct node *prev;
}

A doubly linked list of three members can be created as:

/* Инициализируем узлы */
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;

Circular linked list

A circular linked list is a variant of a linked list where the last element is linked to the first element. This forms a circular loop.

A circular linked list can be either singly linked or doubly linked.

• For a singly linked list, the last element's next pointer points to the first element;
• In a doubly linked list, the prev pointer of the first element also points to the last element.

A circular singly linked list of three members can be created as:

/* Инициализируем узлы */
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;