How to sort a linked list in PHP?

Question

$arr[] = array(...,'id'=1,'prev'=>2,'next'=>null);
$arr[] = array(...,'id'=2,'prev'=>3..,'next'=>1);
$arr[] = array(...,'id'=3,'prev'=>4,'next'=>2);
..

The order of each record can be arbitary.

How to sort this kind of array so that record with prev's value null is first,and the one with null next is last?

Answer 1

Hmm, so you want to get your array into something like:

$array[] = array('id'=>1324, 'prev'=>null, 'next'=>15834);
$array[] = array('id'=>15834, 'prev'=>1324, 'next'=>1023);
$array[] = array('id'=>1023, 'prev'=>15834, 'next'=>12482);
$array[] = array('id'=>12482, 'prev'=>1023, 'next'=>null);

no matter what order they started in? Well, that won't be a basic sort pattern, so I'd go with something like:

// Find the first entry
foreach($arr as $index => $row) {
  if ($row['prev'] == null) {
    // This is the first row
    $cur_row = $row;
    break; // Jump out of the foreach loop
  }
}
$sorted = array();
$sorted[] = $cur_row;
while ($cur_row['next'] != null) {
  // Find the next row
  foreach($arr as $index => $row) {
    if ($row['id'] = $cur_row['next']) {
      // This is the next row
      $sorted[] = $row;
      $cur_row = $row;
      break; // Jump out of the foreach loop
    }
  }
}
print_r($sorted); // $sorted now has your sorted array

Answer 2

I strongly believe you're doing this terribly wrong. An array is not a container for linked lists. A linked list is a list with linked objects, not a list with objects that have relationships. Basically, what you've got is the worst of the two containers, all in one package. You really need to read about data containers and how they work. A real linked list never needs to be sorted the way you need to sort them.

The good way would involve something like that. I'll leave to you the way to insert objects in the middle of the list, it's not that hard.

<?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"
?>

But, if for some occult reason you really, really need them in an array, here is what you would need:

<?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));
?>

But really, do yourself and the whole world a favor, and do a real linked list, using objects and not arrays. The sorting method above is, in my opinion, quite decent knowing the constraints, but it's ridiculously slow because it needs to look up the array for each id.

Answer 3

I believe the built in usort will work nicely for the data structure you described.

edit: This doesn't work correctly. Please un-accept so I can delete it.

<?php
//$arr = your array as described

usort($arr, 'subkey_compare_next');

function subkey_compare_next($a, $b) {
    $a = $a['next'];
    $b = $b['next'];
    if($a === null) {
        return -1;
    }
    if ($a == $b) {
        return 0;
    }
    return ($a < $b) ? -1 : 1;

}
?>

Answer 4

I would do first a round with putting the id's as array keys. At the same moment recording the first element.

$newArray = array():
$firstElement = null;
foreach( $array as $row ) {
    $newArray[$row['id']] = $row;
    if( $row['prev'] == null ) $firstElement = $row['id'];
}

After that you can iterate over the list like this:

$curId = $firstElement;
while($curId != null) {
    do_something($newArray[ $curId ])
    $curId = $newArray[ $curId ]['next'];
}

For efficiency you might considering looking at your data hydrator (the function that get's the data from the database in the array) to see or it can add the id as array-key inmediately. Also you could with query sort order make sure that the first element is always the first element in the original array, making it easy to find that id.

Btw, don't call this a linkedlist implementation, as a linked list is characterized by an object reference to the next element (not an index).

Edit: One thing I didn't mention yet. If you want to have the sorted list in an array, then replace do_something($newArray[ $curId ]); with $array[] = $newArray[ $curId ];.

I believe this solution is much more transparent / quicker then most other solutions as this is costing two rounds over the whole array, or if you can integrate the first part in your hydration method without cost, only one iteration through the array.