Існує три поширені типи зв'язаного списку.
- Єдиний пов'язаний список
- Двозв'язковий список
- Круговий зв'язаний список
Єдиний пов'язаний список
Це найпоширеніший. Кожен вузол має дані та покажчик на наступний вузол.
Де адреса першого вузла спеціальне ім'я, зване 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;
