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

Question

Я разбираюсь со своими структурами данных и алгоритмами , и я только что столкнулся с проблемой удаления из линейных списков. Мне нужна помощь, в основном, с логи c, чтобы я мог с комфортом реализовать код на любом языке. Тем не менее, я изучаю C и C ++ в настоящее время и буду признателен, если какой-либо код будет написан в том же самом виде.

Учитывая приведенный ниже список, моя цель - удалить элемент c* 1006. *.

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

Теперь обратите внимание, я сделал следующее по порядку чтобы придумать новый список:

1) Ищите c

2) Удалено c

3) Смещены остальные элементы влево, потому что:

По определению: Линейные списки должны быть последовательными. Один элемент идет за другим, и не должно быть никаких «пробелов»

Я понимаю логи c для выполнения поиска и сдвига и могу с удобством реализовать их в коде. Теперь моя проблема с логи c для удаления. Вот где мне нужна помощь.

Я реализую свои линейные списки, используя массивы (Не уверен, есть ли другой способ) . Уменьшение размера массива составляет , а не опция. Мне нужно, чтобы размер массива оставался неизменным ... 5 в этом случае

Резюме: Как удалить элемент из линейного списка?

Answer 1

То, что вы используете, это ArrayList . Они поддерживают целочисленную переменную, часто называемую size, которая говорит, какая часть массива используется в настоящее время. В вашем случае после удаления последний слот массива будет пустым, поэтому size будет равно 4, даже если длина массива все еще равна 5.

Псевдокод для алгоритма удаления будет (с индексами массива, начинающимися с 0 и массивом с именем arr):

pos <- index of element you want to delete
from i <- pos to size-1:
    arr[i] = arr[i+1]
size <- size-1

То же самое, что вы сделали в своем вопросе: найдите элемент и удалите его, заменив его значение на тот, который следует, а также сделать это для всех следующих значений. В конце концов, теперь этот список на 1 меньше.