Стандартные функции для двусвязного списка

Рассмотрим несколько стандартных функций для двусвязного списка. Функция push добавляет новый элемент в i-ую позицию списка. Функция выполняет следующие действия:

1. создаёт новый элемент;

2. копируем значение информационного поля;

3. если данный элемент является единственным:

· оба указателя (next и pred) ссылаются на этот элемент,

· указатель first указывает на единственный элемент в списке.

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

Добавим новое значение в двусвязный список (push 4), новый элемент будем добавлять после первого. После операции push список содержит один элемент (Рисунок 6).

Рисунок 6 - После операции push

Добавим ещё несколько значений (push 6 и push 7), каждый новый элемент будем добавлять после первого. Список содержит три элемента (Рисунок 7) в следующей последовательности.

Рисунок 7- Добавление новых значений

Функция pop выталкивает i-ый элемент из списка. Функция выполняет следующие действия:

1)если список пуст, выходим из функции;

2) если в список содержит единственный элемент:

копируем значение информационного поля

удаляем элемент из списка

присваиваем заголовку пусто

3)иначе сдвигаем указатель на i-ый элемент:

если заголовок указывает на i-ый элемент (first==t), тогда перемещаем заголовок на следующий элемент (First=t-> next)

копируем значение информационного поля

удаляем i-ый элемент из списка

4) возвращаем значение информационного поля.

Выполнив функцию pop над линейным списком (выталкиваем 3-ий элемент), получим следующее состояние связного списка (Рисунок 8).

Рисунок 8 - Выталкивание элемента.

Функция view пробегает по всем элементам и выводит в консоль значение информационного поля. Просмотр элементов осуществляется слева направо, но легко можно переписать функцию и изменить просмотр элементов справа налево (заменить a=a-> next на a=a-> pred). Функция clean удаляет все элементы в списке и присваивает заголовку пусто (first=null). После данной операции список возвращается в исходное состояние.