Однозв язний список вид зв язаного списку який складається з вузлів кожен з яких містить у собі дані інформаційну частин

Однозв'язний список — вид зв'язаного списку, який складається з вузлів, кожен з яких містить у собі дані (інформаційну частину) та посилання на наступний вузол.

Структура однобічно зв'язаного списку

Структура списку

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