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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Последовательное хранение линейных списков рассмотрено во множестве источников и не составляет предмета данной статьи [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)

  ClearList

End 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 = 0

End Sub

' Присваивание виртуальному индексу virtualIndex значения realIndex

Private Sub Link(virtualIndex As Integer, realIndex As Integer)

  Refs(virtualIndex) = realIndex

End 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 = i

End Function

' освобождение места при удалении элемента из списка

Private Sub PutSpace(i As Integer)

  Link i, Refs(NullFreeSpace)

  Link NullFreeSpace, i

End 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 If

End Sub

' прочитать значение элемента из списка

' если параметр Index отсутствует или

' не является порядковым номером эелемента списка

' то возвращается значение элемента перед указателем

' в противном случае возвращается значение элемента

' с порядковым номером Index

Function 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 If

End Function

'вернуть количество элементов в списке

Function GetCount() As Integer

  GetCount = Count

End Function

' определить, есть ли свободное место в списке

Private Function IsListFull() As Boolean

  IsListFull = False

  If Refs(NullFreeSpace) = NullFreeSpace Then IsListFull = True

End 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 = True

End Function

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

Sub Test()

    Dim i As Integer

    Dim list1 As MyLinkedList

    Set list1 = New MyLinkedList

    list1.CreateLinkedList 3

    ' вывод количества элементов

    Debug.Print "count of elems = ", list1.GetCount - 1

    ' заполнение списка случайными числами

 Randomize

    For i = 1 To 5

        list1.AddItem Rnd() * 100

    Next i

    ' вывод содержимого списка

    list1.MoveFront

    Do Until list1.IsEndOfList

        Debug.Print list1.ReadItem

        list1.MoveNext

    Loop

    ' вывод количества элементов

    Debug.Print "count of elems = ", list1.GetCount - 1

    ' удаление первого элемента

    list1.MoveFront

    list1.RemoveItem

    ' вывод содержимого списка

    list1.MoveFront

    Do Until list1.IsEndOfList

        Debug.Print list1.ReadItem

        list1.MoveNext

    Loop

    ' вывод содержимого 2-го элемента

    Debug.Print list1.ReadItem(2)

End Sub

Список литературы

Д. Кнут. Искусство программирования. (3-е издание) Т.1.

А.Г. Кушниренко, Г.В. Лебедев. Программирование для математиков. М: Наука. 1988, стр. 202-210.

Для подготовки данной работы были использованы материалы с сайта http://www.rsdn.ru/