Изменения

'''Связный список ''' (англ. ''List'') {{--- }} структура данных, состоящая из узловэлементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий узел элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]]. Вставка и удаление в списке работают за O(1).

Простейшай Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.[[Файл:Single linked list-1-simpleSpisok.png|center|400px]]

[[Файл:Doubly linked listtwiceSpisok.png|center|400px]]

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

[[Файл:Circurlar linked list.png (872×241)circleSpisok.png|center|400px450px]]==Операции на списке==Рассмотрим базовые операции на примере односвязного списка.===Вставка===Очевиден случай, когда необходимо добавить элемент (<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 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|center|430px]]Удаление элемента после заданного (x-<tex>thisElement</tex>key ) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект. '''function''' removeAfter(Node thisElement): '''if''' thisElement.next != k''NULL'' tmp = thisElement.next thisElement.next = thisElement.next.next '''delete''' tmp[[Файл:removeAfter.png|center|550px]] ==Поиск цикла в списке==Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц)&&на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет. '''boolean''' hasCycle(x !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>.  x = x ==Эффективная реализация===Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель <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 x;''' 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> <mathtex>pN + M < kN \Thetaleqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex> Подставив полученные значения, получим:<tex>Q = pN + M + (n1 - 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</mathtex>, так то они встретятся как может понадобиться просмотреть весь списокраз в точке <tex>A</tex>. ===Вставка=Задача про обращение списка==insertДля того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать <tex>NULL</tex>), а возвращает указатель на новую голову списка. Node reverse(kNode current, Node prev): { tmp '''if''' current == head;''NULL'' x->key = k; '''return''' prev x-> next = tmp;current.next head current.next = x;prev } Время работы вставки O'''return''' reverse(1next, current).

===Удаление===delete(k) { tmp = find(k); if (tmp != NULL) { //освобождаем память tmp = tmp->next; } }Само удаление работает за O(1)Алгоритм корректен, но если требуется сначала найти удаляемый элементпоскольку значения элементов в списке не изменяются, то на поиск + удаление потребуется а все указатели <mathtex>\Theta(n)next</mathtex> времениизменят свое направление, не нарушив связности самого списка.

* [[Массив с увеличением/уменьшением размераДинамический массив]] ==Ссылки Источники информации==http* [[wikipedia://en.wikipedia.org/wiki/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Структуры данных]]