Линейный двухсвязный (двунаправленный) список. Общие сведения

В данной теме описываются основные операции, выполняемые над линейным двухсвязным (двунаправленным) списком. Продолжением данной темы является практический пример реализации класса List<T>, который можно найти по следующей ссылке:

Линейный двухсвязный список. Пример шаблонного класса

Содержание

Поиск на других ресурсах:

1. Общий вид двухсвязного списка. Основной элемент списка. Рисунок

В двухсвязном списке базовый элемент списка (узел) имеет следующие поля:

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

Рисунок 1. Базовый элемент списка

На языке C++ (и на других языках) двухсвязный список создается разработкой специального класса. В классе базовыми данными, представляющими список, являются:

begin – указатель на первый элемент списка;
end – указатель на последний элемент списка;
count – количество элементов в списке.

Общий вид двухсвязного списка изображен на рисунке 2.

Рисунок 2. Общий вид двусвязного списка

⇑

2. Создание списка

Перед добавлением новых элементов в список первоочередной задачей является создание пустого списка.

При создании списка можно выделить следующие этапы:

объявление указателей на начало и конец списка (begin, end);
установление нулевых значений указателям;
установка длины списка count в нулевое значение.

Рисунок 3. Создание списка. Этап 1 – объявление внутренних переменных. Этап 2 – заполнение переменных нулевыми значениями

⇑

3. Добавление элемента в конец списка

При добавлении элемента в конец списка выделяют следующие две ситуации:

добавление элемента в пустой список;
добавление элемента в непустой список (список, содержащий элементы).

⇑

3.1. Добавление нового элемента в конец пустого списка

Процесс добавления элемента в конец пустого списка состоит из следующих шагов:

создать новый элемент elem и заполнить его данными (рисунок 4);
установить начало и конец списка (begin, end) так, чтобы они указывали на новый элемент elem (рисунок 5);
увеличить общее количество элементов в списке (поле count).

Рисунок 4. Создание элемента и заполнение данных. Заполняются поля next, prev и data элемента elem

На рисунке 5 устанавливается значение указателей begin и end так, что они указывают на созданный элемент elem.

Рисунок 5. Добавление элемента в пустой список. Настройка указателей начала и конца списка

⇑

3.2. Добавление нового элемента в список, в котором уже есть элементы

Добавление нового элемента в пустой список состоит из следующих шагов:

создание нового элемента elem. Заполнение полей data и next элемента (рисунок 6);
настройка указателя prev элемента elem таким образом, что он указывает на текущую позицию указателя конца списка end (рисунок 7);
настройка указателя next последнего элемента end таким образом, чтобы он указывал элемент elem (рисунок 7);
смещение указателя конца списка elem на одну позицию, определенную указателем elem.

Рисунок 6. Создание элемента. Настройка указателя next и поля данных data элемента elem

Рисунок 7. Добавление элемента в конец непустого списка. Установка указателя prev элемента elem и указателя next последнего элемента списка end

Рисунок 8. Добавление элемента в конец непустого списка. Установка указателя конца списка end на последнюю позицию

⇑

4. Вставка элемента в заданную позицию списка

В отличие от операции добавления элемента в конец списка существует операция вставки элемента в список.

Если происходит вставка элемента в пустой список, то эта операция такая же, как добавление элемента в пустой список (см. пункт 3.1).

При вставке элемента в список, содержащий элементы, важна позиция вставки. В зависимости от позиции рассматриваются следующие ситуации:

элемент вставляется в первую позицию списка;
элемент вставляется во вторую, третью и т.д. позицию списка, а также последнюю позицию списка;
элемент вставляется за последней позицией списка. В этом случае данная вставка такая же как добавление элемента в конец непустого списка (как описывается в пункте 3.2).

⇑

4.1. Вставка элемента в первую позицию списка, содержащего элементы

Последовательность действий при вставке элемента в первую позицию списка следующая:

создать элемент и заполнить его данными (рис. 9). Заполняются поля data и prev;
установить указатель next элемента elem на первый элемент в списке begin (рисунок 10);
установить указатель prev первого элемента списка на вставляемый элемент elem (рисунок 11);
перенаправить указатель begin так, чтобы он указывал на новый элемент elem (рисунок 12);
увеличить общее количество элементов списка.

На рисунках 9, 10, 11, 12 изображены вышеприведенные шаги в визуализированной форме.

Рисунок 9. Вставка элемента в начало непустого списка. Создание нового элемента elem

Рисунок 10. Настройка указателя next вставляемого элемента

Рисунок 11. Присвоение указателю prev первого вставляемого элемента списка begin адреса элемента elem

Рисунок 12. Вставка элемента в начало списка. Перенаправление указателя begin на адрес элемента elem

⇑

4.2. Вставка элемента в середину списка, содержащего элементы

Для вставки элемента в середину списка в некоторую позицию index, нужно выполнить следующую последовательность шагов:

получить элемент elemPrev, который следует перед позицией вставки. Иными словами, получить элемент в позиции index-1 (рисунок 13);
получить элемент elemCur, размещаемый в позиции вставки index (рисунок 13);
создать новый элемент elemIns, который будет вставлен между элементами elemPrev и elemCur. Заполнить поле data элемента (рисунок 14);
установить указатель next элемента elemIns равным адресу элемента elemCur (рисунок 15);
установить указатель prev элемента elemIns равным адресу элемента elemPrev (рисунок 15);
сместить указатель next элемента elemPrev на элемент elemIns (рисунок 16);
сместить указатель prev элемента elemCur на элемент elemIns (рисунок 16).

Вышеприведенный пошаговый процесс отражен на рисунках 13, 14, 15, 16.

Рисунок 13. Вставка элемента в непустой список. Получить элементы в позициях index-1 и index

Рисунок 14. Вставка элемента в непустой список. Создание нового элемента. Заполнение поля data

Рисунок 15. Вставка элемента в непустой список. Установка указателей pred и next вставляемого элемента

Рисунок 16. Вставка элемента в непустой список. Перенаправление указателя next предыдущего элемента elemPrev и указателя prev следующего элемента elemCur на вставляемый элемент elemIns

⇑

5. Удаление элемента из списка

При удалении элемента из списка, содержащего элементы, рассматриваются три возможные ситуации:

удаляется первый элемент списка;
удаляется не первый и не последний элемент;
удаляется последний элемент списка.

⇑

5.1. Удаление первого элемента из списка

При удалении первого элемента из списка последовательность шагов следующая:

запомнить адрес первого элемента в значение elem (рисунок 17);
изменить значение указателя begin так, чтобы он указывал на следующий элемент (рисунок 18). Если следующего элемента нет, то указатель будет иметь значение nullptr;
установить значение указателя prev в нулевое значение (рисунок 19);
освободить память, выделенную для элемента elem;
уменьшить общее количество частей на 1.

Если в списке только один элемент, то приведенные выше шаги также подойдут для этого случая. Ниже на рисунках 17, 18, 19, 20 изображены основные шаги этого процесса.

Рисунок 17. Удаление первого элемента из списка. Шаг 1. Запомнить значение начала списка begin

Рисунок 18. Удаление первого элемента из списка. Шаг 2. Смещение указателя begin на следующий элемент

Рисунок 19. Удаление первого элемента из списка. Шаг 3. Установка указателя prev начала списка begin в нулевое значение

Рисунок 20. Удаление первого элемента из списка. Уничтожение элемента elem (освобождение памяти)

⇑

5.2. Удаление из середины списка

Если элемент удаляется из середины списка, то последовательность шагов следующая:

на основе индекса элемента index получить указатель на удаляемый элемент elem, а также на предыдущий elemPrev и следующий elemNext элементы (рисунок 21);
установить указатель next элемента elemPrev равным адресу элемента elemNext (рисунок 22);
установить указатель prev элемента elemNext равным адресу элемента elemPrev (рисунок 22);
удалить (освободить память) элемент elem (рисунок 23).

Рисунок 21. Удаление элемента из списка. Шаг 1. Получить удаляемый элемент, а также предыдущий и последующий элементы

Рисунок 22. Удаление элемента из списка. Шаг 2. Установка указателей предыдущего элемента elemPrev и следующего элемента elemNext в обход элемента elem

Рисунок 23. Удаление элемента из списка. Шаг 3. Удаление элемента elem

⇑

5.3. Удаление последнего элемента из списка

Для удаления последнего элемента из списка выполняется следующая последовательность действий:

запомнить адрес последнего элемента в списке в указателе elem;
переместить на предыдущий элемент указатель end, указывающий на последний элемент в списке;
освободить память, выделенную под последний элемент в списке;
установить указатель next элемента end в нулевое значение.

Операция удаления последнего элемента из списка подходит для случая, когда в списке есть только один элемент.

Рисунок 24. Удаление последнего элемента из списка. Запомнить адрес последнего элемента

Рисунок 25. Удаление последнего элемента из списка. Перемещение указателя end на предыдущий элемент списка

Рисунок 26. Удаление последнего элемента из списка. Освобождение памяти, выделенной под последний элемент

Рисунок 27. Удаление последнего элемента из списка. Установка в нулевое значение указателя next последнего элемента списка

⇑

Связанные темы

⇑

BestProg

C++. Линейный двухсвязный (двунаправленный) список