Список — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 9 участников)
Строка 1: Строка 1:
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]]. Вставка и удаление в списке работают за O(1).
+
'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].  
  
 
__TOC__
 
__TOC__
 
==Односвязный список ==
 
==Односвязный список ==
Простейшай реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
+
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
[[Файл:Single linked list-1-.png|center|400px]]
+
[[Файл:simpleSpisok.png|center|400px]]
 
==Двусвязный список ==
 
==Двусвязный список ==
 
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
 
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
[[Файл:Doubly linked list.png|center|400px]]
+
[[Файл:twiceSpisok.png|center|400px]]
 
===XOR-связный список ===
 
===XOR-связный список ===
XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.
+
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
 
==Циклический список==
 
==Циклический список==
 
Первый элемент является следующим для последнего элемента списка.
 
Первый элемент является следующим для последнего элемента списка.
[[Файл:Circurlar linked list.png (872×241).png|center|400px]]
+
[[Файл:circleSpisok.png|center|450px]]
==Операции в связном списке==
+
==Операции на списке==
 +
Рассмотрим базовые операции на примере односвязного списка.
 +
===Вставка===
 +
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.
 +
 
 +
  '''function''' insert(Node thatElement):
 +
    thatElement.next = thisElement.next
 +
    thisElement.next = thatElement
 +
[[Файл:insertAfter.png|center|490px]]
 +
 
 
===Поиск===
 
===Поиск===
    find(k)
+
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
    {
+
  Node search('''int''' value):
     x = head;
+
     node = head
     while ((x->key != k)&&(x != NULL))
+
     '''while''' node != ''NULL'' '''and''' value != node.value
         x = x -> next;
+
         node = node.next
     return x;
+
     '''return''' node
    }
 
  
Поиск в худшем случае выполняется за <math>\Theta(n)</math>, так как может понадобиться просмотреть весь список.
 
===Вставка===
 
    insert(k)
 
    {
 
    tmp = head;
 
    x->key = k;
 
    x->next = tmp;
 
    head = x;
 
    }
 
Время работы вставки O(1).
 
 
===Удаление===
 
===Удаление===
Само удаление работает за O(1), но если требуется сначала найти удаляемый элемент, то на поиск + удаление потребуется <math>\Theta(n)</math> времени.
+
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
 +
  '''function''' removeHead():
 +
    '''if''' head != ''NULL''
 +
        tmp = head
 +
        head = head.next
 +
        '''delete''' tmp
 +
[[Файл:removeHead.png|center|430px]]
 +
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
 +
  '''function''' removeAfter(Node thisElement):
 +
    '''if''' thisElement.next != ''NULL''
 +
        tmp = thisElement.next
 +
        thisElement.next = thisElement.next.next
 +
        '''delete''' tmp
 +
[[Файл:removeAfter.png|center|550px]]
 +
 
 +
==Поиск цикла в списке==
 +
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
 +
  '''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''
 +
Если цикла не существует, то заяц первым дойдет до конца и функция возвратит <tex>false</tex>. В другом случае, в тот момент, когда и черепаха и заяц находятся в цикле, расстояние между ними будет сокращаться на <tex>1</tex>, что гарантирует их встречу за конечное время.
 +
 
 +
==Поиск длины хвоста в списке с циклом==
 +
Так как для поиска хвоста мы должны знать, что цикл существует, воспользуемся предыдущей функцией и при выходе из неё запомним "момент встречи" зайца и черепахи. Назовем её <tex>pointMeeting</tex>.
 +
===Наивные реализации===
 +
====Реализация за <tex>O(n^2)</tex>====
 +
Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от <tex>pointMeeting</tex> вперёд указатель. Если он окажется в текущем элементе, прежде чем посетит <tex>pointMeeting</tex> снова, то точку окончания (начала) хвоста нашли.
 +
 
 +
====Реализация за <tex>O(n \log n)</tex>====
 +
Реализацию, приведенную выше можно улучшить. Для этого воспользуемся [[Целочисленный_двоичный_поиск | бинарным поиском]]. Сначала проверим голову списка, потом сделаем <tex> 2 </tex> шага вперёд, потом <tex> 4 </tex>, потом  <tex> 8 </tex> и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции {{---}} на левой границе, где мы в хвосте, и на правой {{---}} в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за <tex>O(n \log n)</tex>.
 +
 
 +
===Эффективная реализация===
 +
Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель <tex>next</tex> последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка (указатель <tex>next</tex> последнего элемента равен любому другому (не первому)). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Достаточно запустить один указатель из <tex>pointMeeting</tex>, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Сложность алгоритма {{---}} <tex>O(n)</tex>.
 +
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
 +
  '''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
 +
====Доказательство корректности алгоритма====
 +
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):
 +
 
 +
<tex>f_1(n) = L + (n-L) \bmod N</tex>
 +
 
 +
<tex>f_2(n) = L + (2n-L) \bmod N</tex>
 +
 
 +
Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.
 +
Пусть <tex>H</tex> {{---}} голова списка, <tex>X</tex> {{---}} точка встречи, <tex>A</tex> {{---}} первый элемент цикла, <tex>Q</tex> {{---}} расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:
 +
 
 +
<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex>
 +
 
 +
<tex>Q = L + (1-k) N</tex>
 +
 
 +
Пусть <tex>L = p N + M, 0 \leqslant M < N</tex>
 +
 
 +
Известно, что
 +
 
 +
<tex>L < k N \leqslant L + N</tex>
 +
 
 +
<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex>
 +
 
 +
Подставив полученные значения, получим:
 +
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.
 +
 
 +
==Задача про обращение списка==
 +
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.
 +
Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать <tex>NULL</tex>), а возвращает указатель на новую голову списка.
 +
 
 +
  Node reverse(Node current, Node prev):
 +
    '''if''' current == ''NULL''
 +
      '''return''' prev
 +
    next = current.next
 +
    current.next = prev
 +
    '''return''' reverse(next, current)
 +
 
 +
Алгоритм корректен, поскольку значения элементов в списке не изменяются, а все указатели <tex>next</tex> изменят свое направление, не нарушив связности самого списка.  
 +
 
 
==См.также==
 
==См.также==
[[Массив с увеличением/уменьшением размера]]
+
* [[Динамический массив]]
==Ссылки ==
+
 
http://en.wikipedia.org/wiki/Linked_list Linked list
+
==Источники информации==
 +
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]
 +
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]
 +
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4
 +
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0
  
==Литература ==
+
[[Категория: Дискретная математика и алгоритмы]]
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
+
[[Категория: Амортизационный анализ]]
* Д. Кнут: Искусство программирования том 1 глава 2.2
+
[[Категория: Структуры данных]]

Текущая версия на 19:28, 4 сентября 2022

Связный список (англ. 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