Однобічно зв'язаний список

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

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

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

Найчастіше вузлом списку вважають структурний тип (структуру), який зберігає у собі певну інформаційну частину (іншу структуру або тип даних) та посилання (вказівник) на наступний вузол у списку. Список має «голову» head, тобто вказівник на початок списку та інколи має кінець tail, проте найчастіше його не використовують.

Переваги та недоліки списків у порівнянні з масивами

Переваги списків над масивами

1. Можливість додавати вузол у кінець списку. Масив має статичний розмір, і, якщо, вільного місця там немає, доведеться створювати масив більшого розміру, копіювати у нього елементи «старого» масиву і тільки після цього додавати новий елемент
2. Можливість видаляти вузол і звільнювати пам'ять, яку він займав. У масиві можна лише зсунути елементи і розглядати його, як масив меншого розміру. Пам'ять при цьому не звільняється.
3. Можливість вставляти вузол у середину списку. При умові, що масив не заповнений до кінця, можна «розсунути» елементи і вставити між ними необхідний. Якщо ж масив повний — доведеться створювати новий масив більшого розміру, копіювати елементи і вставляти новий.

Недоліки списків перед масивами

1. Відсутність поіндексного доступу до елементів списку
2. Зайвий час на прохід по списку для пошуку/видалення/додавання елементу у кінець
3. Використання більшого об'єму пам'яті за рахунок покажчиків на наступний вузол

Операції зі списками

Додати вузол у кінець списку

Для того, щоб додати вузол А у кінець списку, треба знайти останній вузол В у цьому списку, заповнити інформаційну частину вузла А і вказівнику вузла А присвоїти 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;
}

Див. також

• Лінійний список
• Черга (структура даних)
• Зв'язаний список