Типи зв'язаного списку - однозв'язні, двозв'язні та круговий

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

Існує три поширені типи зв'язаного списку.

• Єдиний пов'язаний список
• Двозв'язковий список
• Круговий зв'язаний список

Єдиний пов'язаний список

Це найпоширеніший. Кожен вузол має дані та покажчик на наступний вузол.

Де адреса першого вузла спеціальне ім'я, зване 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;