Список

Связный список (англ. List) — структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.

Односвязный список

Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.

Двусвязный список

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

XOR-связный список

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

Циклический список

Первый элемент является следующим для последнего элемента списка.

Операции на списке

Рассмотрим базовые операции на примере односвязного списка.

Вставка

Очевиден случай, когда необходимо добавить элемент ([math]newHead[/math]) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

 function insert(newHead):
   newHead.next = head
   head = newHead 

Если же на нужно вставить элемент ([math]thatElement[/math]) в определенную позицию после какого-то другого элемента ([math]thisElement[/math]), то просто изменим соответствующие ссылки.

 function insertAfter(thisElement, thatElement):
   thatElement.next = thisElement.next 
   thisElement.next = thatElement

Поиск

Для того, чтобы найти элемент по значению ([math]value[/math]), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем [math]NULL[/math].

 Node Search(value):
   node = head
   while node != NULL and value != node.value
       node = node.next
   return node

Удаление

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

 function removeHead():
   if head != NULL
       tmp = head
       head = head.next
       delete tmp

Удаление элемента после заданного ([math]thisElement[/math]) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.

 function removeAfter(thisElement):
   if thisElement.next != NULL
       tmp = thisElement.next
       thisElement.next = thisElement.next.next
       delete tmp

Задача на поиск цикла в списке

Для начала необходимо уметь определять — список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель(черепаха) переходит к следующему элементу списка, а второй указатель(заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.

 boolean isCycle(head):
   tortoise = head
   hare = head
   repeat
     if hare == NULL or hare.next == NULL 
       return false
     tortoise = tortoise.next
     hare = hair.next.next
   until tortoise != hare
   return true

Возможны два варианта цикла в списке. Первый вариант — сам список циклический(указатель next последнего элемента равен первому), а второй вариант — цикл внутри списка(указатель next последнего элемента равен любому другому(не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.

 int getTail(head, pointMeeting):
   firstElement = head.next
   secondElement = pointMeeting.next
   lengthTail = 1
   while firstElement != secondElement
     firstElement = firstElement.next
     secondElement = secondElement.next
     lengthTail = lenghtTail + 1
   return lengthTail

Доказательство корректности алгоритма

Рассмотрим цикл длиной [math]N[/math] с хвостом длины [math]L[/math]. Напишем функции для обоих указателей в зависимости от шага [math]n[/math]. Очевидно, что встреча не может произойти при [math]n \leqslant L[/math], так как в этом случае [math]2n\gt n[/math] для любого [math]n\gt 0[/math]. Тогда положения указателей зададутся следующими функциями (при [math]n\gt L[/math]):

[math]f_1(n) = L + (n-L) \bmod N[/math]

[math]f_2(n) = L + (2n-L) \bmod N[/math]

Приравнивая, получим [math]n \bmod N = 0[/math], или [math]n = k N, n \gt L[/math]. Пусть [math]H[/math] - голова списка, [math]X[/math] - точка встречи, [math]A[/math] - первый элемент цикла, [math]Q[/math] - расстояние от [math]X[/math] до [math]A[/math]. Тогда в точку [math]A[/math] можно прийти двумя путями: из [math]H[/math] в [math]A[/math] длиной [math]L[/math] и из [math]H[/math] через [math]X[/math] в [math]A[/math] длиной [math]L + N = X + Q[/math], то есть:

[math]Q = L + N - X[/math], но так как [math]X = kN[/math]

[math]Q = L + (1-k) N[/math]

Пусть [math]L = p N + M, 0 \lt = M \lt N[/math]

Известно, что

[math]L \lt k N \leqslant L + N[/math]

[math]pN + M \lt kN \leqslant (p+1)N + M[/math] откуда [math]k = p + 1[/math]

Подставив полученные значения, получим: [math]Q = pN + M + (1 - p - 1)N = M = L \bmod N[/math], откуда следует, что если запустить указатели с одной скоростью из [math]H[/math] и [math]X[/math], то они встретятся через [math]L[/math] шагов в точке [math]A[/math]. К этому времени вышедший из [math]H[/math] пройдёт ровно [math]L[/math] шагов и остановится в [math]A[/math], вышедший из [math]X[/math] накрутит по циклу [math][L/N][/math] шагов и пройдёт ещё [math]Q = L \bmod N[/math] шагов. Поскольку [math]L = [L/N] + L \bmod N[/math], то они встретятся как раз в точке [math]A[/math].

Задача про обращение списка

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

 function reverse(head):
   if head == NULL or head.next == NULL
     return
   current = head
   prev = NULL
   while current != NULL
      next = current.next
      current.next = prev
      prev = current
      current = next
   head = prev

См.также

• Динамический массив

Источники информации

• Wikipedia — Linked list
• Википедия — Список
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — Глава 11.2. — ISBN 5-8489-0857-4
• Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы — 2-е изд. — М.: «Вильямс», 2012. — Глава 2.2. — ISBN 0-201-89685-0