Поиск в односвязном списке

Если таблица задана в виде списка, то производится последовательный поиск в списке

Алгоритм:

q = nil

p = table

while (p <> nil) do

if k(p) = key then

search = p

return

endif

q = p

p = nxt(p)

endwhile

s = getnode

k(s) = key

r(s) = rec

nxt(s) = nil

if q = nil then table = s

else

nxt(q) = s

endif

search = s

return

Эффективность последовательного поиска

Эффективность любого поиска может оцениваться по количеству сравнений С аргумента поиска с ключами таблицы данных. Чем меньше количество сравнений, тем эффективнее алгоритм поиска.

Эффективность последовательного поиска в массиве

Cmin = 1, Cmax = n.

Если данные расположены равновероятно во всех ячейках массива, то

Cср ≈ (n + 1)/2.

Эффективность последовательного поиска в списке - то же самое.

Порядок эффективности последовательного поиска O (n)

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

Эффективность последовательного поиска можно увеличить.