Доступ к ячейкам

Класс LinkedList, используемый программой LnkLst2, позволяет основной программе использовать список почти как массив. Например, подпрограмма Item, приведенная в следующем коде, возвращает значение элемента по его положению:

Function Item(ByVal position As Long) As Variant

Dim ptr As ListCell

If position < 1 Or position > m_NumItems Then

‘ Выход за границы. Вернуть NULL.

Item = Null

Exit Function

End If

‘ Найти элемент.

Set ptr = m_Sentinel

Do While position > 0

position = position - 1

Set ptr = ptr.NextCell

Loop

Item = ptr.Value

End Function

Эта процедура достаточно проста, но она не использует преимущества связной структуры списка. Например, предположим, что программе требуется последовательно перебрать все объекты в списке. Она могла бы использовать подпрограмму Item для поочередного доступа к ним, как показано в следующем коде:

Dim i As Integer

For i = 1 To LList.NumItems

‘ Выполнить какие‑либо действия с LList.Item(i).

:

Next i

При каждом вызове процедуры Item, она просматривает список в поиске следующего элемента. Чтобы найти элемент I, программа должна пропустить I‑1 элементов. Чтобы проверить все элементы в списке из N элементов, процедура пропустит 0+1+2+3+…+N-1 =N*(N-1)/2 элемента. При больших N программа потеряет много времени на пропуск элементов.

Класс LinkedList может ускорить эту операцию, используя другой метод доступа. Можно использовать частную переменную m_CurrentCell для отслеживания текущей позиции в списке. Для возвращения значения текущего положения используется подпрограмма CurrentItem. Процедуры MoveFirst, MoveNext и EndOfList позволяют основной программе управлять текущей позицией в списке.

=======34

Например, следующий код содержит подпрограмму MoveNext:

Public Sub MoveNext()

‘ Если текущая ячейка не выбрана, ничего не делать.

If Not (m_CurrentCell Is Nothing) Then _

Set m_CurrentCell = m_CurrentCell.NextCell

End Sub

При помощи этих процедур, основная программа может обратиться ко всем элементам списка, используя следующий код. Эта версия несколько сложнее, чем предыдущая, но она намного эффективнее. Вместо того чтобы пропускать N*(N-1)/2 элементов и опрашивать по очереди все N элементов списка, она не пропускает ни одного. Если список состоит из 1000 элементов, это экономит почти полмиллиона шагов.

LList.MoveFirst

Do While Not LList.EndOfList

‘ Выполнить какие‑либо действия над элементом LList.Item(i).

:

LList.MoveNext

Loop

Программа LnkList3 использует эти новые методы для управления связным списком. Она аналогична программе LnkList2, но более эффективно обращается к элементам. Для небольших списков, используемых в программе, эта разница незаметна. Для программы, которая обращается ко всем элементам большого списка, эта версия класса LinkedList более эффективна.

Разновидности связных списков

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