Список

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Односвязный список[править]

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

SimpleSpisok.png

Двусвязный список[править]

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

TwiceSpisok.png

XOR-связный список[править]

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

Циклический список[править]

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

CircleSpisok.png

Операции на списке[править]

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

Вставка[править]

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

 function insert(Node thatElement):
   thatElement.next = thisElement.next 
   thisElement.next = thatElement
InsertAfter.png

Поиск[править]

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

 Node search(int 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
RemoveHead.png

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

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

Поиск цикла в списке[править]

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

 boolean hasCycle(Node head):
   tortoise = head
   hare = head
   repeat
     if hare == NULL or hare.next == NULL 
       return false
     tortoise = tortoise.next
     hare = hare.next.next
   until tortoise == hare
   return true

Если цикла не существует, то заяц первым дойдет до конца и функция возвратит [math]false[/math]. В другом случае, в тот момент, когда и черепаха и заяц находятся в цикле, расстояние между ними будет сокращаться на [math]1[/math], что гарантирует их встречу за конечное время.

Поиск длины хвоста в списке с циклом[править]

Так как для поиска хвоста мы должны знать, что цикл существует, воспользуемся предыдущей функцией и при выходе из неё запомним "момент встречи" зайца и черепахи. Назовем её [math]pointMeeting[/math].

Наивные реализации[править]

Реализация за [math]O(n^2)[/math][править]

Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от [math]pointMeeting[/math] вперёд указатель. Если он окажется в текущем элементе, прежде чем посетит [math]pointMeeting[/math] снова, то точку окончания (начала) хвоста нашли.

Реализация за [math]O(n \log n)[/math][править]

Реализацию, приведенную выше можно улучшить. Для этого воспользуемся бинарным поиском. Сначала проверим голову списка, потом сделаем [math] 2 [/math] шага вперёд, потом [math] 4 [/math], потом [math] 8 [/math] и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции — на левой границе, где мы в хвосте, и на правой — в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за [math]O(n \log n)[/math].

Эффективная реализация[править]

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

 int getTail(Node head, Node 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 \leqslant 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].

Задача про обращение списка[править]

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

 Node reverse(Node current, Node prev):
   if current == NULL
     return prev
   next = current.next
   current.next = prev
   return reverse(next, current)

Алгоритм корректен, поскольку значения элементов в списке не изменяются, а все указатели [math]next[/math] изменят свое направление, не нарушив связности самого списка.

См.также[править]

Источники информации[править]

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