Операции над односвязным списком

В случае представления строки массивом вставка строки S1 в строку S2, начиная с позиции N, может быть выполнена следующим образом:

- часть строки S2, начиная с символа N, сдвигается вправо на длину строки S1

- строка S1 копируется в освободившееся пространство

Таким образом, операция вставки связана с физическим переме­ще­нием данных, объем которых может быть значительным. В случае использования списочной организации, операция вставки сводится к изменению нескольких указателей. На рис. 6 изображена операция вставки строки "ИЦ" в слово "КОРА" так, чтобы получилось слово "КОРИЦА". Пунктиром изобра­жены связи после выполнения операции.

Рис. 6 Вставка в список

Рассмотрим операции вставки и удаления узлов.

NODE *InsertNode(NODE *p){

// функция выполняет вставку нового узла вслед за

// узлом p и возвращает указатель на новый узел

NODE *x;

x=new NODE;

x->Next=p->Next;

p->Next=x;