Добавление элементов к связному списку

Простой связный список, показанный на рис. 2.2, обладает несколькими важными свойствами. Во‑первых, можно очень легко добавить новую ячейку в начало списка. Установим указатель новой ячейки NextCell на текущую вершину списка. Затем установим указатель top_cell на новую ячейку. Рис. 2.3 соответствует этой операции. Код на языке Visual Basic для этой операции очень прост:

Set new_cell.NextCell = top_cell

Set top_cell = new_cell

@Рис. 2.3. Добавление элемента в начало связного списка

Сравните размер этого кода и кода, который пришлось бы написать для добавления нового элемента в начало списка, основанного на массиве, в котором потребовалось бы переместить все элементы массива на одну позицию, чтобы освободить место для нового элемента. Эта операция со сложностью порядка O(N) может потребовать много времени, если список достаточно длинный. Используя связный список, моно добавить новый элемент в начало списка всего за пару шагов.

======29

Так же легко добавить новый элемент и в середину связного списка. Предположим, вы хотите вставить новый элемент после ячейки, на которую указывает переменная after_me. Установим значение NextCell новой ячейки равным after_me.NextCell. Теперь установим указатель after_me.NextCell на новую ячейку. Эта операция показана на рис. 2.4. Код на Visual Basic снова очень прост:

Set new_cell.NextCell = after_me.NextCell

Set after_me.NextCell = new_cell

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

Удалить элемент из вершины связного списка так же просто, как и добавить его. Просто установите указатель top_cell на следующую ячейку в списке. Рис. 2.5 соответствует этой операции. Исходный код для этой операции еще проще, чем код для добавления элемента.

Set top_cell = top_cell.NextCell

Когда указатель top_cell перемещается на второй элемент в списке, в программе больше не останется переменных, указывающих на первый объект. В этом случае, счетчик ссылок на этот объект станет равен нулю, и система автоматически уничтожит его.

Так же просто удалить элемент из середины списка. Предположим, вы хотите удалить элемент, стоящий после ячейки after_me. Просто установите указатель NextCell этой ячейки на следующую ячейку. Эта операция показана на рис. 2.6. Код на Visual Basic прост и понятен:

after_me.NextCell = after_me.NextCell.NextCell

@Рис. 2.4. Добавление элемента в середину связного списка

=======30

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

Снова сравним этот код с кодом, который понадобился бы для выполнения той же операции, при использовании списка на основе массива. Можно быстро пометить удаленный элемент как неиспользуемый, но это оставляет в списке ненужные значения. Процедуры, обрабатывающие список, должны это учитывать, и соответственно быть более сложными. Присутствие чрезмерного количества «мусора» также замедляет работу процедуры, и, в конце концов, придется проводить чистку памяти.

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