Структуры данных и модели вычислений
Некоторые дополнительные операции со связными списками
Конкатенация. Эта операция предназначена для соединения двух списков в один результирующий. Она эффективна в тех случаях, когда обеспечен доступ к последнему элементу списка с трудоемкостью . При соединении двух списков и первый элемент списка становится преемником последнего элемента списка . При этом возникают вопросы — должен ли получившийся список иметь какое-то новое имя и должны ли сохраниться как таковые исходные списки
и ?
В рассмотренной ниже процедуре Concat, реализующей операцию "Соединить два списка", принято следующее решение. К списку
присоединяется список , список сохраняется, а результирующим является список . Следует, однако, понимать, что если в список
будут внесены изменения, они автоматически произойдут в новом списке. Трудоемкость этой операции — .
Из списка удалить элементы, удовлетворяющие некоторому условию. Предположим, что требуемое условие на элемент
проверяется предикатом condition().
Построить список,состоящий из элементов данного списка , удовлетворяющих некоторому условию. Предположим, что требуемое условие на элементпроверяется предикатом condition().
Получить списокреверсированием списка
