Реализация связанных списков на базе массивов (стр. 1 из 2)

Реализация связанных списков на базе массивов

Чуриков Константин, Донбасский государственный технический университет

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

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

С реализациями линейных списков в императивных языках программирования могут выполняться следующие операции:

получение доступа к некоторому элементу списка для проверки и/или изменения содержимого его полей;

вставка нового элемента сразу перед или после произвольного элемента;

удаление произвольного элемента;

объединение в одном списке двух (или более) линейных списков;

разбиение линейного списка на два (или более) списка;

создание копии линейного списка;

определение количества элементов в списке;

сортировка элементов списка;

поиск элементов с заданным значением.

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

Внутреннее представление линейных списков

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

Последовательное хранение линейных списков рассмотрено во множестве источников и не составляет предмета данной статьи [1]. Также широко рассмотрено связанное хранение линейных списков, но в подавляющем большинстве случаев такая реализация основана на ссылочной реализации [2]. В то же время существует изящная, но мало известная широкому кругу молодых программистов реализация связного хранения линейных списков на базе массивов. Достаточно подробное, хотя и весьма специфическое описание такой реализации дано в [3]. Этому способу и посвящена данная статья.

ПРИМЕЧАНИЕТакая реализация встречается не так уж редко. Просто она часто скрывается за разными названиями - индексные массивы, массивы соответствия и т.п. Несмотря на разницу в названиях, используется один и тот же алгоритм. – прим.ред.

Реализация связанного списка на базе массивов

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

в начале списка (то есть перед первым элементом списка);

в конце списка (то есть за последним элементом списка);

между элементами списка.

Навигатор можно передвигать только от начала к концу списка на один элемент за раз. Кроме того, добавлять элементы списка можно только в позиции, на которую ссылается навигатор. А изменять/удалять/читать можно только элементы, которые находятся в позиции, предшествующей той, на которую ссылается навигатор, т.е. впереди по ходу его движения.

Основная идея данной реализации состоит в отделении информации о содержимом элементов списка от информации о порядке их следования. Графически эта идея представлена на рисунке 1.

Рисунок 1.

Далее ссылки будем изображать стрелками, как показано на рисунке 2.

Рисунок 2.

Естественно, что для работы со списком одних только ссылок между элементами недостаточно – надо знать, например, где расположен первый элемент списка, и отличать последний элемент от всех остальных (ведь за ним уже никаких элементов нет). Для этих целей можно было бы ввести две переменные, которые содержали бы индексы начала и конца списка. Мы, однако, этого делать не будем, а воспользуемся приёмом «сворачивания в кольцо» – «свернем» список, введя специальный воображаемый элемент NULL, который всегда будем располагать в элементе с индексом NullElem (имеющим значение 0) массива, используемого для хранения ссылок на элементы списка (назовем его Refs). На рисунке 3 показано графическое представление этой модели.

Заметьте, что теперь ссылки между элементами списка образуют кольцо, начинающееся с NullElem. Таким образом, ссылка с индексом NullElem показывает на первый элемент списка, а если очередная ссылка равна NullElem, то соответствующий элемент является в списке последним.

Рисунок 3.

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

Навигатор располагается между элементами, поэтому реализуем его в виде двух переменных BEFORE и AFTER, где AFTER содержит индекс элемента за пройденным, а BEFORE – индекс элемента еще не пройденного элемента. Положению навигатора в начале списка, таким образом, соответствует случай, когда AFTER равен NullElem, а положению в конце – когда это значение содержится в BEFORE.

Теперь связанный список сымитирован полностью. Неясными остаются только следующие вопросы:

Как определять наличие или отсутствие свободного места в массиве элементов (назовем его Elems)?

Как находить свободный элемент в массиве элементов при имитации добавления элемента к списку?

Чтобы не гадать, какие элементы Elems свободны, а какие заняты, примем решение, хранить кроме списка занятых элементов так же список свободных. Элементы этого списка так же будут соединены в кольцо, начинающееся со служебного элемента хранящегося в элементе с индексом NullFreeSpace (равным единице) массива ссылок (Refs). Графическое представление получившейся модели изображено на рисунке 4.

Таким образом, чтобы определить, есть ли в списке свободное место, надо посмотреть значение элемента Refs(NullFreeSpace). Если это значение равно NullFreeSpace (т.е. показывает на себя), то свободного места нет. В противном случае это значение указывает на первый свободный элемент массива элементов. При добавлении элемента к списку необходимо исключить индекс этого элемента из списка свободных и включить его в основной список. При удалении элемента необходимо произвести обратную операцию.

На рисунке 4 черным цветом обозначен подразумеваемый связанный список, а красным – список свободных элементов.

Рисунок 4.

В программной реализации списка присваивание ссылке с индексом virtualIndex значения realIndex выделим в отдельную подпрограмму. Кроме того, в отдельные подпрограммы выделим все действия, связанные с работой со свободным местом.

ПРИМЕЧАНИЕВ примере описывается создание списка для хранения вещественных чисел. Для создания списка элементов другого типа требуется соответствующим образом изменить объявление типа элементов массива Elems(), типа параметра element в процедуре AddItem() и типа возвращаемого значения в функции ReadItem(). Подразумевается, что приведенный код оформлен в виде отдельного модуля или класса, что предпочтительнее. Кроме того, хотя в статье рассмотрен ограниченный список, в реализации предусмотрена возможность динамического увеличения длины списка в случае необходимости.

С учетом всех вышесказанных замечаний реализация односвязного линейного списка на Visual Basic 6.0 может иметь вид, приведенный ниже.

Класс MyLinkedList:

' номер ячейки Refs, указывающей на первый элемент спискаConst NullElem = 0 ' номер ячейки Refs, указывающей на первый элемент из "свободного места"Const NullFreeSpace = 1 Dim Elems() As Double ' Массив для хранения элементов спискаDim Refs() As Integer ' Массив для хранения ссылокDim AFTER As Integer ' Указатель предыдущего элементаDim BEFORE As Integer ' Указатель следующего элементаDim Count As Integer ' Количество элементов в списке' Создание списка для хранения capacity элементов' 1-я ячейка Refs указывает на первый элемент списка' 2-я ячейка Refs указывает на 1-й элемент Х из "свободного места"' capacity - максимально допустимое количество элементов в списке.Sub CreateLinkedList(capacity As Integer) ReDim Elems(capacity + 1) ReDim Refs(capacity + 1) ClearListEnd Sub' ОчисткаспискаSub ClearList() Refs(NullElem) = NullElem 'конец списка указывает сам на себя Dim i As Integer ' Поскольку список пуст, то все ячейки массива помечаются' как "свободноеместо". For i = NullFreeSpace To UBound(Refs) - 1 Refs(i) = i + 1 Next i Refs(UBound(Refs)) = NullFreeSpace ' Закольцовываем "свободноеместо". AFTER = 0 BEFORE = 0 Count = 0End Sub' Присваиваниевиртуальномуиндексу virtualIndex значения realIndexPrivate Sub Link(virtualIndex As Integer, realIndex As Integer)Refs(virtualIndex) = realIndexEnd Sub' Выделение места для новых элементовPrivate Function GetSpace() As Integer Dim i As Integer, OldLength As Integer If IsListFull Then OldLength = UBound(Elems) ReDim Preserve Elems(OldLength * 2) 'динамическоеувеличениедлины ReDim Preserve Refs(OldLength * 2) 'списка, еслионужеполностьюзаполненFor i = OldLength + 1 To OldLength * 2 - 1 'добавляемые элементы помечаются Refs(i) = i + 1 'как свободное местоNext i Refs(NullFreeSpace) = OldLength + 1 Refs(OldLength * 2) = NullFreeSpace End If i = Refs(NullFreeSpace) Link NullFreeSpace, Refs(i) GetSpace = iEnd Function' освобождение места при удалении элемента из спискаPrivate Sub PutSpace(i As Integer) Link i, Refs(NullFreeSpace) Link NullFreeSpace, iEnd Sub' добавить element в списокSub AddItem(element As Double) Dim i As Integer i = GetSpace() ' получаемсвободноеместоLink AFTER, i ' устанавливаем его в Link i, BEFORE ' нужном месте списка BEFORE = i ' устанавливаем указатель Elems(i) = element ' добавляем элемент element в список MoveNext Count = Count + 1 ' увеличиваем счетчик количества элементовEnd Sub'удалить элемент из спискаSub RemoveItem() Dim i As Integer If Count <> 0 Then i = BEFORE BEFORE = Refs(i) Link AFTER, BEFORE PutSpace i Count = Count – 1 Else Err.Raise vbObjectError + 513, , "List is empty"End IfEnd Sub' прочитать значение элемента из списка' если параметр Index отсутствует или' не является порядковым номером эелемента списка' то возвращается значение элемента перед указателем' в противном случае возвращается значение элемента' спорядковымномеромIndexFunction ReadItem(Optional Index As Integer = -1) As Double If Not (Index >= 0 And Index < Count) Then If IsEndOfList Then ReadItem = Elems(AFTER) Else ReadItem = Elems(BEFORE) End If Else Dim i As Integer, k As Integer k = NullElem For i = 0 To Index k = Refs(k) Next i ReadItem = Elems(k)End IfEnd Function'вернуть количество элементов в спискеFunction GetCount() As Integer GetCount = CountEnd Function' определить, есть ли свободное место в спискеPrivate Function IsListFull() As Boolean IsListFull = False If Refs(NullFreeSpace) = NullFreeSpace Then IsListFull = TrueEnd Function' передвинуть указатель на один элемент спискаSub MoveNext() AFTER = BEFORE BEFORE = Refs(BEFORE)End Sub' передвинуть указатель в начало спискаSub MoveFront() AFTER = 0 BEFORE = Refs(NullElem)End Sub' определить, находится ли указатель в конце спискаFunction IsEndOfList() As Boolean IsEndOfList = False If Refs(AFTER) = NullElem Then IsEndOfList = TrueEnd Function

Пример использования данной реализации списка: