Doubly Linked List in PHP

One of the weaknesses of PHP is the lack of Abstract Data Structures. 5.3 brought in a few but nothing very significant. Users of 5.2+ have none. Creating data structures in PHP is also not very simple because PHP’s garbage collection mechanism does not like recursive references. PHP bug 33595 confirms this very eloquently. This also teaches us an important lesson. Never take garbage collection for granted. Always clean up after yourself.

It all boils down to how objects in PHP are referenced. We have object identifiers and not pointers or object hashes. I did get some implementations on the web but all seemed to have forgotten about the GC issue. A large list with thousands of nodes resulted in memory errors.

To decouple my implementation from object identifiers I decided to use hash table to store my node objects. Let me explain.

In a traditional implementation I would have something like the following. A rudimentary node class with few methods shown. Also note that $_previous and $_next are object identifiers. :

class JNode
{
   private $_value;
   private $_previous;
   private $_next;

   public function __construct($value)
   {
      $this->setValue($value);
   }

public function setPrevious(JNode $previous)
   {
      $this->_previous = $previous;
   }

   public function setNext(JNode $next)
   {
      $this->_next = $next;
   }

You could use it like this:

$head = new MyNode('HEAD');
$head->setPrevious(null);

$node1 = new MyNode('NODE-1');
$node1->setPrevious($head);
$head->setNext($node1);

...
...

Rather than using object identifiers why not do it this way. I have modified the class to use UIDs. Also note that in the constructor I have setting up a new UID for the object. Now $_next and $_previous will be UIDs and not object identifiers.:

public function __construct($value)
   {
      $this->setValue($value);
      $this->setUid();
   }

   public function setUid($uid = null)
   {
      //if uid not supplied...generate
      if(empty($uid)) {
         $this->_uid = uniqid();
      } else {
         $this->_uid = $uid;
      }
   }

   public function getUid()
   {
      return $this->_uid;
   }

   public function setValue($value)
   {
      if(empty($value)) {
         throw new Exception('A value is required.');
      }
      $this->_value = $value;
   }

   public function setPrevious($previous)
   {
      if(empty($previous)) {
         throw new Exception('A unique ID is required.');
      }
      $this->_previous = $previous;
   }

   public function setNext($next)
   {
      if(empty($next)) {
         throw new Exception('A unique ID is required.');
      }
      $this->_next = $next;
   }

The use would be according to these line:

//my hashtable
//uid => object 
$myHashTable = array();

$head = new MyNode('HEAD');
$headUid = $head->getUid();
$myHashTable[$headUid] = $head;

$head->setPrevious(null);

$node1 = new MyNode('NODE-1');
$node1Uid = $node1->getUid();
$myHashTable[$node1Uid ] = $node1;

$node1->setPrevious($headUid);
$head->setNext($node1Uid);

...
...

Now rather than using the object identifier as reference to the object we use a UID to refer to the object identifier which refers to the actual object. This way there are no circular or recursive references. Also GC becomes very straightforward. Every list has an iterator. Writing one in this case also becomes very simple. Now that you have seen the concept here is the final implementation.

The final implementation can be found on Github: doubly-linked-list-php: Implementation of a doubly linked list for legacy PHP sites (5.2.X)

Please note that this is a minimum implementation. You could add many more methods such as inserting at an index, getting the size of the list, indexOf. My main intent is to show how to use UIDs as object references. Also note that in the main class I have helper classes to create, add and delete nodes.

In the following example I have included memory use statements to make sure that I clean up properly.

//instantiate the list
$ll = new JDoublyLinkedList();

//First node goes after the head.
$firstNode = $ll->createNode('First Node');
$ll->addFirst($firstNode);

//10 more nodes
for($i = 0; $i < 5; $i++) {
   $node = $ll->createNode('Node-' . $i);
   $ll->addNext($firstNode, $node);
   $firstNode = $node;
}

//and this is how we iterate...iterate
$it = new JLinkedListIterator($ll);

foreach($it as $k => $v) {
   echo '<pre>', $k, ': ', print_r($v, true), '</pre>';
}

unset($ll, $it);

echo 'Peak: ' . number_format(memory_get_peak_usage(), 0, '.', ',') .  " bytes<br>";

echo 'End: ' . number_format(memory_get_usage(), 0, '.', ',') . " bytes<br>";

The output would be something like this:

Initial: 126,360 bytes

4d7f677322b38: JNode Object
(
    [_value:private] => First Node
    [_previous:private] => 4d7f677322b06
    [_next:private] => 4d7f677322b69
    [_uid:private] => 4d7f677322b38
)

4d7f677322b69: JNode Object
(
    [_value:private] => Node-0
    [_previous:private] => 4d7f677322b38
    [_next:private] => 4d7f677322b95
    [_uid:private] => 4d7f677322b69
)

4d7f677322b95: JNode Object
(
    [_value:private] => Node-1
    [_previous:private] => 4d7f677322b69
    [_next:private] => 4d7f677322bbf
    [_uid:private] => 4d7f677322b95
)

4d7f677322bbf: JNode Object
(
    [_value:private] => Node-2
    [_previous:private] => 4d7f677322b95
    [_next:private] => 4d7f677322be8
    [_uid:private] => 4d7f677322bbf
)

4d7f677322be8: JNode Object
(
    [_value:private] => Node-3
    [_previous:private] => 4d7f677322bbf
    [_next:private] => 4d7f677322c12
    [_uid:private] => 4d7f677322be8
)

4d7f677322c12: JNode Object
(
    [_value:private] => Node-4
    [_previous:private] => 4d7f677322be8
    [_next:private] => 4d7f677322b1b
    [_uid:private] => 4d7f677322c12
)

Peak: 175,952 bytes
End: 135,080 bytes

Notice that the cleanup was not bad. If I had to create 1000 nodes then this is what the memory utilization looks like:

Initial: 126,376 bytes
Peak: 803,464 bytes
End: 192,440 bytes

That’s pretty decent in terms of GC but there is still room for improvement.

Advertisements

One thought on “Doubly Linked List in PHP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s