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

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

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


Содержание


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

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

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

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

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

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

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

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

 

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

 

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

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

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

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

 

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

 

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

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

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

 

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

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

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

 

C++. Линейный двусвязный список. Добавление элемента в конец списка. Шаг 1. Создание элемента и заполнение его даннымиРисунок 4. Создание элемента и заполнение данных. Заполняются поля next, prev и data элемента elem

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

C++. Линейный двухсвязный список Добавление элемента в конец пустого списка. Шаг 2. Настройка указателей начала и конца спискаРисунок 5. Добавление элемента в пустой список. Настройка указателей начала и конца списка

 

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

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

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

 

C++. Линейный двухсвязный список Добавление элемента в список. Шаг 1. Создание элементаРисунок 6. Создание элемента. Настройка указателя next и поля данных data элемента elem

C++. Линейный двухсвязный список Добавление элемента в список. Шаг 2. Настройка указателейРисунок 7. Добавление элемента в конец непустого списка. Установка указателя prev элемента elem и указателя next последнего элемента списка end

C++. Линейный двухсвязный список Добавление элемента в список. Шаг 3. Установка указателя последнего элемента спискаРисунок 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 изображены вышеприведенные шаги в визуализированной форме.

 

C++. Линейный двухсвязный список Вставка элемента в первую позицию списка. Шаг 1. Создание элемента

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

 

C++. Линейный двухсвязный список Вставка элемента в первую позицию списка. Шаг 2. Настройка указателя next элемента вставкиРисунок 10. Настройка указателя next вставляемого элемента

 

C++. Линейный двухсвязный список Вставка элемента в первую позицию списка. Шаг 3. Настройка указателя начала списка

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

C++. Линейный двухсвязный список Вставка элемента в первую позицию списка. Шаг 4. Установление указателя начала спискаРисунок 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.

 

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

C++. Линейный двухсвязный список. Вставка элемента в список. Шаг 2. Создание нового элементаРисунок 14. Вставка элемента в непустой список. Создание нового элемента. Заполнение поля data

C++. Линейный двухсвязный список. Вставка элемента в список. Шаг 3. Настройка указателей элемента вставки

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

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

 

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

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

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

 

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

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

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

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

C++. Линейный двухсвязный список. Удаление первого элемента из списка. Шаг 1. Получить позицию удаленияРисунок 17. Удаление первого элемента из списка. Шаг 1. Запомнить значение начала списка begin

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

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

C++. Линейный двухсвязный список. Удаление первого элемента из списка. Шаг 4. Удаление элементаРисунок 20. Удаление первого элемента из списка. Уничтожение элемента elem (освобождение памяти)

 

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

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

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

 

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

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

C++. Линейный двухсвязный список. Удаление элемента из списка. Шаг 3. Удаление элементаРисунок 23. Удаление элемента из списка. Шаг 3. Удаление элемента elem

 

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

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

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

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

C++. Линейный двухсвязный список. Удаление последнего элемента из списка. Шаг 1. Получить адрес последнего элементаРисунок 24. Удаление последнего элемента из списка. Запомнить адрес последнего элемента

C++. Линейный двухсвязный список. Удаление последнего элемента из списка. Шаг 2. Смещение указателя на предыдущий элементРисунок 25. Удаление последнего элемента из списка. Перемещение указателя end на предыдущий элемент списка

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

C++. Линейный двухсвязный список. Удаление последнего элемента из списка. Шаг 4. Настройка указателя окончания спискаРисунок 27. Удаление последнего элемента из списка. Установка в нулевое значение указателя next последнего элемента списка

 


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