2.2 Реализация операций над связными линейными списками

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

1). Указатель текущего элемента устанавливается на начало списка. 2). Если указатель текущего элемента пустой – конец перебора. 2). Обрабатывается информационная часть текущего элемента., на который 3). из текущего элементата выбирается указатель на следующий элемент и следующий элемент становится текущим. 4). Повторяются децствия с п.2.

В двухсвязном списке возможен перебор как в прямом направлении (он выглядит точно так же,  как и перебор в односвязном списке), так  и  в обратном. 

В кольцевом  списке окончание перебора должно происходить не по признаку последнего элемента - такой признак отсутствует, а по достижению элемента,  с которого начался перебор.

Вставка элемента в список. Вставка элемента в середину  односвязного списка реализуется следующим алгоритмом. 1). Выделяется память для нового элемента и записывается его информационная часть  2). Значение указателя next предшествующего элемента переносится в поле next нового элемента. 2). В поле next предшествующего элемента заносится адрес нового элемента. Приведенные алгоритмы обеспечивают вставку в  середину списка, но не могут быть применены для вставки в начало списка.  При вставке в начало списка должен модифицироваться указатель на  начало  списка.

Удаление элемента из списка. При удалении элемента из односвязного достаточно значение из поля next удаляемого элемента перенести в поле next предыдущего элемента.

Перестановка элементов списка. Изменчивость динамических структур данных предполагает не только изменения размера структуры,  но и изменения связей между элементами. Для связных структур изменение  связей не требует пересылки данных в памяти,  а только изменения указателей в элементах связной  структуры.  В  качестве примера приведена перестановка двух соседних элементов списка.  В алгоритме перестановки в односвязном списке (рис.5.9, пример 5.5) исходили  из того,  что известен адрес элемента,  предшествующего паре, в которой производится перестановка. В приведенном алгоритме  также  не  учитывается  случай перестановки первого и второго элементов. 1). В поле next 1-го элемента пары переносится значение из поля next 2-го элемента 2). В поле next 2-го элемента пары заносится адрес 1-го элемента 3). В поле next элемента, предшествующего паре, заносится адрес 2-го элемента

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

Слияние двух списков. Операция слияния заключается в формировании из двух списков одного - она аналогична операции  сцепления  строк.  В  случае односвязного списка последний элемент первого списка содержит пустой указатель на следующий элемент,  этот указатель служит признаком конца списка. Вместо этого пустого указатель  в  последний  элемент первого списка заносится указатель на начало второго списка.  Таким образом,  второй список  становится продолжением первого.