Изменения
Нет описания правки
===XOR-связный список ===
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
==Циклический список==
Первый элемент является следующим для последнего элемента списка.
'''delete''' tmp
[[Файл:removeAfter.png|center|550px]]
==Задача на поиск цикла в списке==
Для начала необходимо уметь определять - список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель(черепаха) переходит к следующему элементу списка, а второй указатель(заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
'''boolean''' isCycle(head)
firstElement = head.next
secondElement = head.next.next
'''while''' firstElement != secondElement
'''if''' secondElement == ''NULL'' '''or''' secondElement.next == ''NULL''
'''return''' ''false''
firstElement = firstElement.next
secondElement = secondElement.next.next
'''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
==См.также==
* [[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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
