Изменения
Нет описания правки
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.
'''function''' insert(newHead):
newHead.next = head
head = newHead
[[Файл:insertHead.png|center|550px]]
Если же на нужно вставить элемент (<tex>thatElement</tex>) в определенную позицию после какого-то другого элемента (<tex>thisElement</tex>), то просто изменим соответствующие ссылки.
'''function''' insertAfter(thisElement, thatElement):
thatElement.next = thisElement.next
thisElement.next = thatElement
===Поиск===
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>.
Node Search(value):
node = head
'''while''' node != ''NULL'' '''and''' value != node.value
===Удаление===
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
'''function''' removeHead():
'''if''' head != ''NULL''
tmp = head
[[Файл:removeHead.png|center|430px]]
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
'''function''' removeAfter(thisElement):
'''if''' thisElement.next != ''NULL''
tmp = thisElement.next
==Задача на поиск цикла в списке==
Для начала необходимо уметь определять {{- --}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель(черепаха) переходит к следующему элементу списка, а второй указатель(заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет. '''boolean''' isCycle(head): firstElement tortoise = head.next secondElement hare = head.next.next '''whilerepeat''' firstElement != secondElement '''if''' secondElement hare == ''NULL'' '''or''' secondElementhare.next == ''NULL''
'''return''' ''false''
'''return''' ''true''
Возможны два варианта цикла в списке. Первый вариант {{- --}} сам список циклический(указатель next последнего элемента равен первому), а второй вариант {{--- }} цикл внутри списка(указатель next последнего элемента равен любому другому(не первому). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Для того, чтобы его найти, запомним момент, когда в предыдущей функции два указателя оказались равны друг другу. Теперь достаточно запустить один указатель из этого места списка, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла.
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
'''int''' getTail(head, pointMeeting):
firstElement = head.next
secondElement = pointMeeting.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 <= 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>.
==Задача на обращение списка==
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.
'''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 = cur
current = next
head = prev
==См.также==
