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

Динамический список

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

Список может быть:

1. Однонаправленный
2. Двунаправленный.

Однонаправленный список реализуется с помощью типового элемента, который содержит 2 поля:

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

Операции:

1. Выборка i-го элемента: В(i)→Аi. Чтобы вычислить Аi нужно просмотреть (i-1) элемент.

ТАi=i уо, Твыборки=(i+1) уо

2. Вставка (добавление) элемента после i-го элемента.

Tдоб.≈ (i+2)уо, Тдоб.=(n/2+2)

1. Удаление элемента из списка

Тудал.≈ (i+2)уо, Тудал.=Тдоб.=(n/2+2)

Сравнение динамического списка со списком в массиве

	Выборка	Удаление	Добавление
Статический массив		n	n+1
Динамический список	n/2 + 1	n/2 + 2	n/2 + 2

Резюме:

Из таблицы видно, что список на базе массива имеет явное преимущество в реализации операции Выборка. Но немного уступает в реализации добавления и удаления элементов. Еще одним преимуществом динамического списка является использование памяти для элементов, находящихся в списке, т.е. память выделяется по мере надобности, а в списке массивом память нужно заказывать сразу под максимальное число элементов. Особенно это необходимо, если количество элементов в списке варьируется в очень больших пределах. Недостатком динамического списка является использование большого объема памяти, т.к. хранение каждого элемента требует памяти под указатель на следующий элемент. А если учесть, что в компьютере память выделяется параграфами и при выделении памяти для каждого элемента требуется служебная информация от 4 до 8 байт, то затраты памяти могут значительно превышать объем информации.

Дата добавления: 2014-01-15