Облако знаний. Связные списки (C++). Информатика. 11 класс

Связные списки (C++)

Связный список – структура данных, состоящая из последовательности элементов, где каждый узел хранит:
- данные (значение);
- указатель (ссылку) на следующий узел в списке.
Элементы располагаются в динамической памяти (куче), а не в непрерывной области памяти, как в массиве.

Реализуется с помощью структуры (struct).

struct Node { int data; // Полезные данные
(может быть любой тип)
Node* next; // Указатель на следующий узел 
// Конструктор для удобства инициализации 
Node (int value) : data (value), next (nullptr) {}

Основные виды связных списков:
- односвязный список: узел содержит указатель только на следующий элемент. Обход только в одну сторону;
- двусвязный список: узел содержит указатели и на следующий, и на предыдущий элемент. Удобнее для удаления и обхода назад, но требует больше памяти:
```
struct DNode { 
	int data; DNode* next;
	DNode* prev; 
	Dnode (int value) : data (value), next (nullptr), 
	prev (nullptr) {}  };
```
- кольцевой список: «хвост» списка указывает на его «голову», образуя кольцо.
Самое важное преимущество перед массивами: эффективная вставка/удаление. Не требует сдвига всех последующих элементов, как в массиве.

Было полезно?