Однозв'язний список — вид зв'язаного списку, який складається з вузлів, кожен з яких містить у собі дані (інформаційну частину) та посилання на наступний вузол.
Структура однобічно зв'язаного списку
Структура списку Найчастіше вузлом списку вважають структурний тип (структуру), який зберігає у собі певну інформаційну частину (іншу структуру або тип даних) та посилання (вказівник) на наступний вузол у списку. Список має «голову» 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; }
Див. також Зв'язаний список Розгорнутий зв'язний список Черга (структура даних)
Джерела