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

Связный список представляет собой последовательность элементов (узлов), соединенных в цепочку. Последовательность может содержать любое количество элементов, поскольку при создании списка используется динамическое распределение памяти.
Каждый элемент связного списка представляет собой отдельный объект, содержащий поле для хранения информации и указатель на следующий элемент списка (а в случае двусвязного списка в объекте хранится также указатель на предыдущий элемент).

Структура связного списка в C++

Рисунок 1 – Структура связного списка

Для представления элемента списка, хранящего, например, символы, можно использовать структуру:
struct node
{
char value;
node* next;
};
Поле value используется для хранения, собственно, символа, next – указатель на следующий элемент списка. При работе со списками на практике чаще всего приходится выполнять следующие операции:
- создание / уничтожение списка
- добавление элемента
- удаление элемента
- поиск нужного элемента в списке
Для выделения памяти под элементы можно использовать оператор new.
Последовательность действий при создании списка: выделить память под 1-й элемент. В поле value записать значение. В поле next – 0:

node *top = new node;
top->value = ’s’;
top->next = NULL;

Добавление элемента в список: сохранить адрес последнего элемента во временной переменной; создать новый элемент, записать в него значение, в поле next – указатель на предыдущий элемент.

node *prev = top;
top = new node;
top->value = ‘d’;
top->next = prev; //связать с предыдущим

Удалять элементы можно с помощью оператора delete. Его формат: delete <указатель>.
Стек (stack) – это последовательность некоторых однотипных элементов. Данные в стеке организованы по принципу «последним вошел – первым вышел». Это означает, что добавлять и удалять элементы стека можно только с одного конца стека. Доступный конец стека называется его вершиной, операция добавления элемента в стек называется помещением в стек, а операция извлечения из стека – выталкиванием.
Вектор (vector) – это последовательность элементов, доступ к которым осуществляется по индексу. Вектор можно наращивать по мере необходимости, и он осуществляет контроль значений индексов. Добавлять элементы можно только в конец вектора. Вектор предназначен для хранения элементов одного типа.
Очередь (queue) – последовательность однотипных элементов. Данные в очереди, в отличие от стека, организованы по принципу «первым вошел – первым вышел». Добавляются элементы в конец очереди, считываются – с начала очереди.
Пример. Создать класс List для хранения списка символов.
struct node
{
char value;
node* next;
};
class List
{
private:
node *top; // указатель на последний занесенный в список элемент
int size; // размер списка
public:
List() : top (NULL), size(0)
{}
void Push(char c)
{
if (size == 0)
{
top = new node;
top ->value = c;
top ->next = NULL;
//………
}
//………
}
// другие функции
};