Вступление
Связанные списки — это одна очень распространенная и удобная структура данных, которая может использоваться во многих случаях практического программирования. В этом посте мы предполагаем, что речь идет об односвязном списке. Это означает, что каждый элемент указывает на свой предыдущий элемент и, в свою очередь, указывает на следующий элемент. В этом сценарии первый элемент списка, его голова, не имеет предка, а последний элемент не имеет преемника.
Иногда из-за ошибок, плохой архитектуры или сложности приложений у нас могут возникнуть проблемы со списками. Одной из типичных проблем является наличие цикла, который вкратце означает, что некоторые элементы списка указываются дважды, как показано на рисунке ниже.
Итак, в первую очередь мы должны быть уверены, что есть петля. Тогда мы должны спросить: как мы можем сломать это?
Есть несколько алгоритмов нахождения цикла, но вот очень простой. Он известен как алгоритм Флойда или «алгоритм черепахи и зайца».
обзор
Алгоритм Флойда опирается на одну очень простую идею. Первоначально мы установили два указателя на заголовок списка.
На каждом шаге мы увеличиваем оба указателя. Но заяц увеличивается на два элемента, в то время как черепаха ходит по каждому предмету, как показано на изображениях ниже.
Заяц быстрый и прыгает сразу на пару предметов!
Черепаха, как видно из рисунка ниже, намного медленнее.
Черепаха намного медленнее зайца!
В результате, если у нас нет петли в списке, заяц попадет в конец списка; но если у нас есть петля, заяц поймает черепаху внутри петли.
Поскольку заяц быстрее и заяц и черепаха находятся в цикле, более быстрый указатель догонит черепаху!
Код
Предполагая типичное представление односвязного списка, вот пример кода на PHP.
Класс предмета
class Item
{
protected $_name = '';
protected $_key = '';
protected $_next = null;
public function __construct($key, $name)
{
$this->_key = $key;
$this->_name = $name;
}
public function setNext(&$next) { $this->_next = $next; }
public function &getNext() { return $this->_next; }
public function setKey($key) { $this->_key = $key; }
public function getKey() { return $this->_key; }
public function setName($name) { $this->_name = $name; }
public function getName() { return $this->_name; }
public function __toString()
{
return $this->_key . ' ' . $this->_name . "\n";
}
}
Класс списка
class Linked_List
{
protected $_head = null;
public function insert($item)
{
if ($this->_head == null) {
$this->_head = $item;
return;
}
$current = $this->_head;
while ($current->getNext()) {
$current = $current->getNext();
}
$current->setNext($item);
}
public function detectLoop()
{
$tortoise = $hare = $this->_head;
if ($hare->getNext() != null) {
$hare = $hare->getNext()->getNext();
} else {
return FALSE;
}
while ($hare) {
if ($hare == $tortoise) {
return $hare;
}
if ($hare->getNext()) {
$hare = $hare->getNext()->getNext();
} else {
return FALSE;
}
$tortoise = $tortoise->getNext();
}
return FALSE;
}
protected function _isReachable($a, $b)
{
$current = $b;
while ($current->getNext() != $b) {
if ($current->getNext() == $a) {
return $current;
}
$current = $current->getNext();
}
return FALSE;
}
public function breakLoop()
{
if (FALSE === ($loop = $this->detectLoop())) {
return;
}
$startOfTheLoop = $this->_head;
while (FALSE === ($lastLoopItem = $this->_isReachable($startOfTheLoop, $loop))) {
$startOfTheLoop = $startOfTheLoop->getNext();
}
$pseudoNext = null;
$lastLoopItem->setNext($pseudoNext);
}
public function __toString()
{
$current = $this->_head;
$output = '';
while ($current) {
$output .= $current->getKey() . ' ' . $current->getName() . "\n";
$current = $current->getNext();
}
return $output;
}
}
инициализация
$items = array();
$ll = new Linked_List();
for ($i = 0; $i < 100; $i++) {
$items[$i] = new Item($i, 'Item #' . $i);
$ll->insert($items[$i]);
}
// 0 Item #0
// 1 Item #1
// ...
// 99 Item #99
echo $ll;
$items = array();
$ll = new Linked_List();
for ($i = 0; $i < 100; $i++) {
$items[$i] = new Item($i, 'Item #' . $i);
$ll->insert($items[$i]);
}
// 0 Item #0
// 1 Item #1
// ...
// 99 Item #99
echo $ll;
Разорвать петлю
Чтобы разорвать цикл, нам нужно сначала проверить, доступен ли элемент из цикла. Как только мы узнаем это, мы должны вернуть последний элемент цикла, чтобы улучшить производительность следующего метода — breakLoop. Это делается с помощью следующего метода:
protected function _isReachable($a, $b)
{
$current = $b;
while ($current->getNext() != $b) {
if ($current->getNext() == $a) {
return $current;
}
$current = $current->getNext();
}
return FALSE;
}
Теперь мы можем разорвать цикл, удалив двойную ссылку на первый элемент цикла.
// member of Linked_List
public function breakLoop()
{
if (FALSE === ($loop = $this->detectLoop())) {
return;
}
$startOfTheLoop = $this->_head;
while (FALSE === ($lastLoopItem = $this->_isReachable($startOfTheLoop, $loop))) {
$startOfTheLoop = $startOfTheLoop->getNext();
}
$pseudoNext = null;
$lastLoopItem->setNext($pseudoNext);
}
сложность
Предполагая, что длина списка равна N, а длина цикла равна M, мы разорвем цикл в O ((NM) * M) по сложности времени только после того, как мы нашли цикл. Вопрос в том, как быстро мы можем найти цикл с алгоритмом выше? Хорошо, заяц довольно быстр и может проходить через некоторые элементы петли несколько раз, но черепаха последовательно проходит по всем элементам. Вопрос в том, догонит ли заяц черепаху до того, как последний доберется до конца цикла? Ответ — да, и мы можем думать об одном связанном списке без петель, где два указателя начинаются с начала списка. Тот же вопрос можно перевести на: достигнет ли более быстрый указатель конца до того, как более медленный достигнет середины списка? Ну да.
Наконец, ответом O (N) является ответ на вопрос, существует ли петля, и O (M * (NM)) прерывает ее.
Однако, хорошая новость заключается в том, что когда мы работаем со связанными списками, мы часто работаем только с указателями (как в нашем случае в этом посте). Таким образом, нам не нужна дополнительная память, что делает их очень полезными. На самом деле, мы увидим то же преимущество в следующем алгоритме — реверсирование связанного списка (более эффективное, чем реверсирование массива).