Однобічно зв'язаний список
Однозв'язний список — вид зв'язаного списку, який складається з вузлів, кожен з яких містить у собі дані (інформаційну частину) та посилання на наступний вузол.
Структура однобічно зв'язаного списку
Структура списку
Найчастіше вузлом списку вважають структурний тип (структуру), який зберігає у собі певну інформаційну частину (іншу структуру або тип даних) та посилання (вказівник) на наступний вузол у списку. Список має «голову» head, тобто вказівник на початок списку та інколи має кінець tail, проте найчастіше його не використовують.
Переваги та недоліки списків у порівнянні з масивами
Переваги списків над масивами
- Можливість додавати вузол у кінець списку. Масив має статичний розмір, і, якщо, вільного місця там немає, доведеться створювати масив більшого розміру, копіювати у нього елементи «старого» масиву і тільки після цього додавати новий елемент
- Можливість видаляти вузол і звільнювати пам'ять, яку він займав. У масиві можна лише зсунути елементи і розглядати його, як масив меншого розміру. Пам'ять при цьому не звільняється.
- Можливість вставляти вузол у середину списку. При умові, що масив не заповнений до кінця, можна «розсунути» елементи і вставити між ними необхідний. Якщо ж масив повний — доведеться створювати новий масив більшого розміру, копіювати елементи і вставляти новий.
Недоліки списків перед масивами
- Відсутність поіндексного доступу до елементів списку
- Зайвий час на прохід по списку для пошуку/видалення/додавання елементу у кінець
- Використання більшого об'єму пам'яті за рахунок покажчиків на наступний вузол
Операції зі списками
Додати вузол у кінець списку
Для того, щоб додати вузол А у кінець списку, треба знайти останній вузол В у цьому списку, заповнити інформаційну частину вузла А і вказівнику вузла А присвоїти NULL, і «приєднати» його до останнього вузла у списку, тобто до вузла В.
Додати вузол у початок списку
Для того, щоб додати вузол А у початок списку, потрібно заповнити інформаційну частину вузла А, вказівник А направити на голову head списку і зробити цей вузол головою.
Видалити заданий вузол зі списку
Для того, щоб видалити необхідний вузол, потрібно послідовно перебирати вузли, запам'ятовуючи попередній вузол В. Коли необхідний вузол А буде знайдено, потрібно вказівник «попередника» (тобто вузла В) зв'язати з наступним вузлом (тим, що йде після вузла А) і видалити вузол А.
Реалізація списку у С++
Реалізація вузла
struct Node
{
int value; // певна інформативна частина
Node * next; // вказівник (pointer) на наступну структуру-вузол у списку
};
Node * head = NULL; // вказівник на голову списку, спочатку він нікуди не вказує, бо список порожній
Реалізація функції додавання у кінець списку
void addToEnd(int v)
{
Node * n;
if (!head)
{
head = new Node;
head->value = v;
head->next = NULL;
return;
}
else
{
n = head;
while (n->next)
n = n->next;
Node * newNode = new Node;
newNode->value = v;
newNode->next = NULL;
n->next = newNode;
return;
}
}
Реалізація функції додавання у початок списку
void addToBegin(int v)
{
Node * n = new Node;
n->value = v;
n->next = head;
head = n;
}
Реалізація функції видалення певного вузла
void deleteNode(Node * n)
{
Node * k = head;
if (head == n)
{
head = n->next;
delete n;
return;
}
while (k->next != n)
k = k->next;
k->next = n->next;
delete n;
}
Реалізація функції пошуку вузла за інформаційною частиною
Node * find(const int v)
{
Node * n = head;
while (n)
{
if (n->value == v)
return n;
n = n->next;
}
return NULL;
}
Реалізація функції вставки вузла після заданого вузла
void insert(const int v, Node * n)
{
Node * newNode = new Node;
newNode->value = v;
newNode->next = n->next;
n->next = newNode;
}