Линейный однонаправленный список

Организация списка приведена на рис. 1.5.

Начало

Элемент 1

next

Элемент 2

next

...

Элемент N

*

Рис_.1.5. Организация однононаправленного линейного списка

Язык программирования Си позволяет описать данную структуру сле-

дующим образом:

struct node { // структура, определяющая элемент списка

// и указатель на следующий элемент

Struct element val; // значение элемента списка

struct node *next; // указатель на следующий элемент

};

struct node *first = NULL; // указатель на первый элемент списка

// (обнулен, если список пуст)

Поиск элемента. Осуществляется от указателя на первый элемент пу-

тем последовательного перебора. Завершение поиска происходит при на-

хождении элемента с заданным ключом или при достижении первого эле-

мента, ключ которого превышает искомый.

Включение. Осуществляется после завершения поиска с достижением

первого элемента, ключ которого превышает искомый. Новый элемент

включается перед найденным. Для выполнения операции включения необ-

ходимо иметь служебную переменную, в которой хранится указатель на

предшествующий элемент списка.

Удаление_. Осуществляется после успешного завершения поиска эле_-

мента с заданным ключом. Для выполнения этой операции так же необхо-

димо хранить указатель на предшествующий элемент списка.

Массовое удаление. Осуществляется путем поэлементного удаления в

цикле. При большом числе элементов в списке данный процесс может ока-

заться достаточно долгим.

Преимущества. Организация таблицы в виде динамического списка

позволяет выделять память по мере надобности. При этом используются

функции, предоставляемые операционной системой. При удалении элемента

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

систему и повторно использоваться для других целей.

Недостатки. Поиск осуществляется только последовательно, что при-

водит к снижению его эффективности. Замедляет работу и процедура выде-

ления (освобождения) памяти для элементов списка, которая осуществляется

мелкими порциями каждый раз при добавлении и удалении элементов. Мед-

ленно осуществляется массовое удаление элементов списка.