Массив не контейнер для связанного списка. Связанный список - это список с связанными объектами , а не список с объектами, имеющими отношения. По сути, у вас есть худший из двух контейнеров. Я бы попытался преобразовать эту структуру в какой-то другой контейнер данных; реальный связанный список никогда не нужно сортировать так, как вам нужно сортировать данные.
Хороший способ - это что-то подобное. Я оставлю вам способ вставлять объекты в середину списка, это не так сложно.
<?php
class LinkedObject
{
var $value;
var $prev;
var $next;
public function __construct($value, $prev = null, $next = null)
{
$this->value = $value;
$this->prev = $prev;
$this->next = $next;
}
public function append(LinkedObject $insertee)
{
$link = $this;
while($link->next != null)
$link = $link->next;
$link->next = $insertee;
$insertee->prev = $link;
}
public function __toString()
{
$str = $this->value;
if($this->next != null)
{
$str .= " » ";
$str .= $this->next;
}
return $str;
}
}
$head = new LinkedObject("foo");
$head->append(new LinkedObject("bar"));
$head->append(new LinkedObject("baz"));
echo $head . "\n"; // gives "foo » bar » baz"
?>
Но, если по какой-то оккультной причине вы действительно нуждаетесь в них в массиве, вот что вам нужно:
<?php
function find_row($array, $id)
{
foreach($array as $current_row)
{
if($current_row['id'] === $id)
return $current_row;
}
return null;
}
function what_the_heck_sort($array)
{
$start_record = $array[0];
$working_record = $array[0];
$result = array($working_record);
while($working_record['prev'] !== null)
{
$working_record = find_row($array, $working_record['prev']);
array_unshift($result, $working_record);
}
$working_record = $start_record;
while($working_record['next'] !== null)
{
$working_record = find_row($array, $working_record['next']);
array_push($result, $working_record);
}
return $result;
}
// the test code
$test = array(
array("foo 01", 'id' => 0, 'prev' => null, 'next' => 1),
array("foo 02", 'id' => 1, 'prev' => 0, 'next' => 2),
array("foo 03", 'id' => 2, 'prev' => 1, 'next' => 3),
array("foo 04", 'id' => 3, 'prev' => 2, 'next' => 4),
array("foo 05", 'id' => 4, 'prev' => 3, 'next' => 5),
array("foo 06", 'id' => 5, 'prev' => 4, 'next' => 6),
array("foo 07", 'id' => 6, 'prev' => 5, 'next' => 7),
array("foo 08", 'id' => 7, 'prev' => 6, 'next' => 8),
array("foo 09", 'id' => 8, 'prev' => 7, 'next' => 9),
array("foo 10", 'id' => 9, 'prev' => 8, 'next' => null));
shuffle($test);
print_r(what_the_heck_sort($test));
?>
Но на самом деле, сделайте себе одолжение и составьте реальный связанный список, используя объекты, а не массивы. Приведенный выше метод сортировки, на мой взгляд, вполне приличный, зная ограничения, но он смехотворно медленный , потому что ему нужно искать массив для каждого идентификатора.