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;
