Алгоритм удаления элемента в списке по ключу

1. Введем дополнительный указатель и присвоим ему значение NULL:

Spis *key = NULL;

2. Введем с клавиатуры искомое значение i_p (ключ поиска).

3. Установим текущий указатель на начало списка:

t = begin;

4. Начало цикла (выполнять пока t!= NULL).

5. Сравниваем информационную часть текущего элемента с искомым.

5.1. Если они совпадают (t -> info = i_p), то (выводим на экран сообщение об успехе);

а) запоминаем адрес найденного элемента:

key = t;

б) завершаем поиск – досрочный выход из цикла (break);

5.2. Иначе, переставляем текущий указатель на следующий элемент:

t = t -> Next;

6. Конец цикла.

7. Контроль, если key = NULL, т.е. искомый элемент не найден, то сообщаем о неудаче и этап удаления не выполняем (return или exit).

1. Если найден элемент для удаления, т.е. key!= NULL, то удаляем элемент из списка в зависимости от его местонахождения.

2. Если удаляемый элемент находится в начале списка, т.е. key = begin, то создаем новый начальный элемент:

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

begin = begin -> Next;

б) указателю Prev элемента, который был вторым, а теперь стал первым присваиваем значение NULL, т.е. предыдущего нет:

begin -> Prev = NULL;

3. Если удаляемый элемент в конце списка, т.е. key равен end, то:

а) указатель конца списка переставляем на предыдущий элемент, адрес которого в поле Prev последнего (end):

end = end -> Prev;

б) обнуляем указатель на следующий (Next) элемент нового последнего элемента

end -> Next = NULL;

4. Если удаляемый элемент находится в середине списка, нужно обеспечить связь предыдущего и последующего элементов:

а) от k -го элемента с адресом key обратимся к предыдущему (k –1)-му элементу, адрес которого key -> Prev, и в его поле Next [(key -> Prev)-> Next ] запишем адрес (k +1)-го элемента, значение которого key -> Next:

(key -> Prev) -> Next = key -> Next;

б) аналогично в поле Prev (k +1)-го элемента с адресом key -> Next запишем адрес (k -1)-го элемента:

(key -> Next) -> Prev = key -> Prev;

5. Освобождаем память, занятую удаленным элементом free (key);