Editors Note, February 14th 2022: This project is now ABANDONED and no longer supported or updated.

asherwunk/phabstractic now implements a doubly-linked list, a common abstract data type found in computer programming.

Doubly-Linked List

I can quote Wikipedia on this one:

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes’ previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

PHP 5 actually has a ‘built-in’ version of a double-linked list called the SplDoublyLinkedList.  This is a pure PHP implementation of that construction.

Linked List Elements

In order to construct a double-linked list, we need to be able to talk about particular ‘nodes’ of that list.  This is where LinkedListElementInterface comes in (view on github):

namespace Phabstractic\Data\Types\Resource
{
    interface LinkedListElementInterface
    {
        public function &getNextElement();
        
        public function &getPreviousElement();
        
        public function setNextElement(LinkedListElementInterface &$next);
        
        public function setPreviousElement(LinkedListElementInterface &$prev);
        
        public function nullNextElement();
        
        public function nullPreviousElement();
    }   
}

When denoting previous and next elements in the list we use PHP references, so as not to mistake duplicate data.  This is much akin to using pointers in C, though not exactly.  For more information on references see the PHP documentation.

So for any given list element, we can find out what comes before (getPreviousElement()) and what comes next (getNextElement()).  Likewise, we can also set and nullify these same variables.  This allows the construction of an ‘array’ of values or elements that can be changed simply by changing an element’s next/previous element.  This allows us to ‘insert’ a value before a given element, or after a given element.  With an array, we’d have to re-index the whole thing in order to achieve this functionality, but it is simple with a double-linked list.  As well, if we wanted we could point the next element of the last element to the first element and create an unending cycle.  This is often done with such things as memory buffers.

For concrete code regarding the next and previous elements, examine the AbstractLinkedListElement (view on github):

namespace Phabstractic\Data\Types\Resource
{
    abstract class AbstractLinkedListElement implements LinkedListElementInterface 
    {
        protected $nextElement = null;
        
        protected $previousElement = null;
        
        public function &getNextElement()
        {
            return $this->nextElement;
        }
        
        public function setNextElement(LinkedListElementInterface &$next)
        {
            $this->nextElement = &$next;
        }
        
        public function nullNextElement()
        {
            // If next is a reference, unreference it
            unset($this->nextElement);
            $this->nextElement = null;
        }
        
        public function &getPreviousElement()
        {
            return $this->previousElement;
        }
        
        public function setPreviousElement(LinkedListElementInterface &$previous)
        {
            $this->previousElement = &$previous;
        }
        
        public function nullPreviousElement()
        {
            // If a reference, unreference
            unset($this->previousElement);
            $this->previousElement = null;
        }       
    }
}

Finally, let us attach a piece of data to this element in our concrete LinkedListElement (view on github):

namespace Phabstractic\Data\Types
{    
    use Phabstractic\Data\Types\Resource as TypesResource;

    class LinkedListElement extends TypesResource\AbstractLinkedListElement implements
        TypesResource\LinkedListElementInterface
    {
        private $data = null;
        
        public function getData()
        {
            return $this->data;
        }
        
        public function &getDataReference()
        {
            return $this->data;
        }
        
        public function setData($data)
        {
            $this->data = $data;
        }
        
        public function setDataReference(&$data)
        {
            $this->data = &$data;
        }
        
        public function __construct(
            &$data,
            TypesResource\LinkedListElementInterface &$previous = null,
            TypesResource\LinkedListElementInterface &$next = null
        ) {
            $this->data = &$data;
            
            if ($previous !== null) {
                $this->setPreviousElement($previous);
            }
            
            if ($next !== null) {
                $this->setNextElement($next);
            }
            
        }
    }   
}

Note in our constructor we have provided means of immediately specifying the next and previous elements of a linked list element.  However, just because we have specified them in the constructor doesn’t mean that those pointers are reciprocated in the reference elements.

There is also a static method for creating linked list elements from the class:

public static function buildElement(
    $data,
    TypesResource\LinkedListElementInterface &$previous = null,
    TypesResource\LinkedListElementInterface &$next = null
) {
    return new LinkedListElement($data, $previous, $next);
}

Linked Lists

Now that we have a list element isolated and fleshed out with some data, let’s look at keeping track of the list itself.  Let’s start with the basic operations performed by linked lists in LinkedListInterface (view on github):

namespace Phabstractic\Data\Types\Resource
{
    interface LinkedListInterface
    {
        public function &getSentinelElement();
        
        public function insertElementBefore(
            LinkedListElementInterface &$newElement,
            LinkedListElementInterface &$element = null
        );
        
        public function insertElementAfter(
            LinkedListElementInterface &$newElement,
            LinkedListElementInterface &$element = null
        );
        
        public function removeElement(LinkedListElementInterface &$element);
    }   
}

Pretty simple, get the head of the list (in this case we break with Wikipedia and don’t provide the ‘end’ of the list, we must traverse the list in order to retrieve the last element), insert before and after an element, and finally delete an element.

The real focus is what we do to ensure the proper links between the elements.  This is accomplished in AbstractLinkedList (view on github):

namespace Phabstractic\Data\Types\Resource
{
    class AbstractLinkedList implements LinkedListInterface
    {
        protected $sentinelElement = null;
        
        public function &getSentinelElement()
        {
            return $this->sentinelElement;
        }
        
        private function isElementInList(&$element)
        {
            $current = $this->getSentinelElement();
            
            if ($current !== null) {
                while ($current !== null) {
                    if ($element === $current) {
                        return true;
                    }
                    
                    $current = &$current->getNextElement();
                }
                
            }
            
            return false;
        }
        
        public function insertElementBefore(
            LinkedListElementInterface &$newElement,
            LinkedListElementInterface &$element = null
        ) {
            // avoid infinite loops
            if ($this->isElementInList($newElement)) {
                return false;
            } else {
                if ($element === null) {
                    // if $element is null, we are inserting at the beginning of the list
                    if ($this->sentinelElement === null) {
                        // this list is empty
                        $this->sentinelElement = &$newElement;
                        $this->sentinelElement->nullNextElement();
                        $this->sentinelElement->nullPreviousElement();
                    } else {
                        // we need to go BEFORE the sentinel element
                        $this->insertElementBefore($newElement, $this->sentinelElement);
                    }
                } else {
                    /* otherwise we are inserting before an actual element
                       this can be the sentinelElement (see above) */
                    if ($element->getPreviousElement() !== null) {
                        $newElement->setPreviousElement($element->getPreviousElement());
                        $element->getPreviousElement()->setNextElement($newElement);
                    } else {
                        $newElement->nullPreviousElement();
                    }
                    
                    $newElement->setNextElement($element);
                    $element->setPreviousElement($newElement);
                    if ($newElement->getPreviousElement() === null) {
                        $this->sentinelElement = &$newElement;
                    }
                }
            }
            
            return true;
        }
        
        public function insertElementAfter(
            LinkedListElementInterface &$newElement,
            LinkedListElementInterface &$element = null
        ) {
            if ($this->isElementInList($newElement)) {
                return false;
            } else {
                if ($element === null) {
                    // if element is null, we are inserting at the end of the list
                    if ($this->sentinelElement === null) {
                        // this list is empty
                        $this->sentinelElement = &$newElement;
                        $this->sentinelElement->nullNextElement();
                        $this->sentinelElement->nullPreviousElement();
                    } else {
                        // find the last element
                        $element = &$this->sentinelElement;
                        while ($element->getNextElement() !== null) {
                            $element = &$element->getNextElement();
                        }
                        
                        $this->insertElementAfter($newElement, $element);
                    }
                } else {
                    // otherwise we are inserting after an actual element
                    $newElement->setPreviousElement($element);
                    
                    if ($element->getNextElement() !== null) {
                        $newElement->setNextElement($element->getNextElement());
                        $element->getNextElement()->setPreviousElement($newElement);
                    } else {
                        $newElement->nullNextElement();
                    }
                    
                    $element->setNextElement($newElement);
                }
            }
            
            return true;
        }
        
        public function removeElement(LinkedListElementInterface &$element)
        {
            if ($this->isElementInList($element)) {
                if ($this->sentinelElement === $element) {
                    // we are removing the sentinel element
                    unset($this->sentinelElement); // dereference
                    
                    if ($element->getNextElement() !== null) {
                        $this->sentinelElement = $element->getNextElement();
                    } else {
                        $this->sentinelElement = null;
                    }
                    
                    return;
                }
                
                // otherwise, we have an element we need to get rid of
                $prev = &$element->getPreviousElement();  // might be null
                $next = &$element->getNextElement();
                
                if ($prev !== null) {
                    if ($next !== null) {
                        $prev->setNextElement($next);
                    } else {
                        $prev->nullNextElement();
                    }
                }
                
                if ($next !== null) {
                    if ($prev !== null) {
                        $next->setPreviousElement($prev);
                    } else {
                        $next->nullPreviousElement();
                    }
                }
                
                return true;
                
            } else {
                return false;
            }
        }
    }
}

As you can see each function in the linked list is concerned with modifying the list in such a way as to retain the stability of each element’s pointers.  There is different logic for instance in the insertion of an element at the beginning of the list (and thus making a new sentinel node), or for inserting an element at the end of a list.  When we remove an element we must make sure that the two elements surrounding the removal still point to each other.

This all works very well theoretically and is very useful for many programming endeavors.  But what happens when we want to treat the linked list as a list?  That is, we count how many elements are in it, or run it through a for-each loop.  This is where the concrete implementation of the linked list comes into play.  It is the class that ultimately implements \ArrayAccess, \Iterator, and \Countable so that the linked list can be used as a first-class language type (view on github):

namespace Phabstractic\Data\Types
{
    use Phabstractic\Features;
    use Phabstractic\Features\Resource as FeaturesResource;
    use Phabstractic\Data\Types\Resource as TypesResource;
    use Phabstractic\Data\Types\Exception as TypesException;
    
    class LinkedList extends TypesResource\AbstractLinkedList implements
        TypesResource\LinkedListInterface,
        \ArrayAccess,   // access the list like so: $list[indice]
        \Iterator,      // run the list through loops
        \Countable,      // tell us how many elements there are
        FeaturesResource\ConfigurationInterface
    {
        use Features\ConfigurationTrait;
        
        private $currentElement = null;
        
        // Countable Interface Methods
        
        public function count() {
            $numberOfElements = 0;
            
            if ($this->sentinelElement !== null) {
                $current = &$this->sentinelElement;
                $numberOfElements++;  // count the first element
                while ($current->getNextElement() !== null) {
                    $current = &$current->getNextElement();
                    $numberOfElements++;
                }
                
            }
            
            return $numberOfElements;
        }
        
        /* The \Iterator Interface Methods
         * 
         * These enable the LinkedList to be used in foreach loops
         *
         */
        
        public function current()
        {
            return $this->currentElement;
        }
        
        public function key()
        {
            return 'Phabstractic\\Data\\Types\\LinkedList::currentElement';
        }
        
        public function next()
        {
            $this->currentElement = &$this->currentElement->getNextElement();
        }
        
        public function rewind()
        {
            // sentinelElement is in abstract parent
            $this->currentElement = &$this->sentinelElement;
        }
        
        public function valid()
        {
            if ($this->currentElement !== null) {
                return true;
            }
            
            return false;
        }
        
        private function &getElementAtIndex($index, $strict = false)
        {
            // count from the beginning zero
            $i = 0;
            $null = null;
            
            if ($this->sentinelElement !== null) {
                $current = &$this->sentinelElement;
                while ($i != $index && $current->getNextElement() !== null) {
                    $current = &$current->getNextElement();
                    $i++;
                }
                
                if ($i != $index) {
                    if ($strict) {
                        // we're strict, so throw a range exception
                        throw new TypesException\RangeException(
                            'Phabstractic\\Data\\Types\\LinkedList->getElementAtIndex: ' .
                            'List smaller than index');
                    } else {
                        return $null;
                    }
                } else {
                    return $current;
                }
            } else {
                if ($strict) {
                    // we're strict, so throw a range exception
                    throw new TypesException\RangeException(
                        'Phabstractic\\Data\\Types\\LinkedList->getElementAtIndex: ' .
                        'LinkedList is empty');
                } else {
                    return $null;
                }
            }
        }
        
        // The ArrayAccess Functions
        
        public function offsetSet($key, $value)
        {
            // value must be a linkedlistelement
            if (!($value instanceof LinkedListElement)) {
                // exit quietly
                return false;
            }
            
            if (!$key) {
                return $this->insertElementAfter($value);
            }
            
            $current = &$this->getElementAtIndex($key);
            
            if ($current !== null) {
                // replace the current value
                $prev = $current->getPreviousElement();
                $next = $current->getNextElement();
                
                if ($prev !== null) {
                    $value->setPreviousElement($prev);
                    $prev->setNextElement($value);
                } else {
                    $value->nullPreviousElement();
                }
                
                if ($next !== null) {
                    $value->setNextElement($next);
                    $next->setPreviousElement($value);
                } else {
                    $value->nullNextElement();
                }
                
                $current->nullPreviousElement();
                $current->nullNextElement();
                
            } else {
                // exit quietly
                return false;
            }
            
            return true;
        }
        
        public function offsetGet($key) {
            return $this->getElementAtIndex($key, $this->conf->strict);
        } 
        
        public function offsetUnset($key) {
            $current = &$this->getElementAtIndex($key);
            
            if ($current !== null) {
                return $this->removeElement($current);
                return true;
            }
            
            return false;
        } 
        
        public function offsetExists($key) {
            $count = $this->count();
            
            if ($key <= $count) {
                return true;
            }
            
            return false;
        }
        
        public function __construct(
            LinkedListElement $sentinel = null,
            array $options = array()
        ) {
            $this->configure($options);
            
            if ($sentinel !== null) {
                $this->sentinelElement = &$sentinel;
            }
        }
        
        public function flatten() {
            $ret = array();
            
            // we can iterate over ourselves
            foreach ($this as $element) {
                $ret[] = $element->getData();
            }
            
            return $ret;
        }
        
        public function &findElement($data) {
            foreach ($this as $element) {
                if ($data == $element->getData()) {
                    return $element;
                }
            }
            
            return null;
        }
        
        // SPL Defined Functions For Compatibility
        
        public function add($index, LinkedListElement &$newelement) {
            try {
                $current = $this[$index];
                
                if ($current !== null) {
                    $this->insertElementBefore($newelement, $current);
                    return true;
                }
            } catch (TypesException\RangeException $e) {
                throw new TypesException\OutOfRangeException(
                    'Phabstractic\\Data\\Types\\LinkedList->add: ' .
                    'Index out of range');
            }
            
            return false;
            
        }
        
        public function bottom() {
            return $this->getSentinelElement();
        }
        
        public function &bottomReference() {
            return $this->getSentinelElement();
        }
        
        public function top() {
            $current = $this->getSentinelElement();
            
            if ($current !== null) {
                while ($current->getNextElement() !== null) {
                    $current = &$current->getNextElement();
                }
            }
            
            return $current;
        }
        
        public function &topReference() {
            $current = $this->getSentinelElement();
            
            if ($current !== null) {
                while ($current->getNextElement() !== null) {
                    $current = &$current->getNextElement();
                }
            }
            
            return $current;
        }
        
        public function isEmpty() {
            if ($this->getSentinelElement()) {
                return true;
            }
            
            return false;
        }
        
        public function pop() {
            $top = &$this->topReference();
            
            if ($top !== null) {
                $this->removeElement($top);
            }
            
            return $top;
        }
        
        public function &popReference() {
            $top = &$this->topReference();
            
            if ($top !== null) {
                $this->removeElement($top);
            }
            
            return $top;
        }
        
        public function prev()
        {
            $this->currentElement = &$this->currentElement->getPreviousElement();
        }
        
        public function push(&$element) {
            return $this->insertElementAfter($element);
        }
        
        public function shift() {
            $ret = &$this->getSentinelElement();
            
            if ($ret !== null) {
                $this->removeElement($ret);
            }
            
            return $ret;
        }
        
        public function &shiftReference() {
            $ret = &$this->getSentinelElement();
            
            if ($ret !== null) {
                $this->removeElement($ret);
            }
            
            return $ret;
        }
        
        public function unshift(&$element) {
            return $this->insertElementBefore($element);
        }
    }
}

Because our object can also act as its own iterator it’s important that we keep track of the ‘current’ element being referenced.

You’ll see above the different applicable interfaces’ methods separated out and implemented.  In order to increase compatibility between this pure PHP implementation of SplDoublyLinkedList and the real thing, some additional methods have been implemented as shown.

Because the Linked List doesn’t implement its internal list as an array structure I decided not to implement the ListInterface.  If we returned an array from ‘getList’ it would have to be of references to elements that are not really in an array.  I thought blurring these distinctions of the natures of these lists would get confusing.  Instead, I relegated this kind of functionality to a method named flatten().

Usage

Using a linked list is easy in this case, but you must remember that all operations on linked lists occur with linked list elements.  This is important, as operations expecting data to automatically be wrapped with a LinkedListElement will fail.  To illustrate:

<?php

use Phabstractic\Data\Types;

$list = new Types\LinkedList();

$element1 = Types\LinkedListElement::buildElement('data');
$element2 = 'moredata';

$list->push($element1); // append element 1 to the end of the list
$list->push($element2); // will fail, not proper element

// retrieve the first element's data:
$data = $list[0]->getData();

Conclusion

Doubly linked lists are important data structures for they enable a range of data to be stored in sequential order in memory without necessarily having to be spaced next to each other, or worry about a particular size.  There are many advantages to storing data outside of an array like this, including the dynamic nature of its allocation and flexibility of editing the order of elements (including the addition and subtraction of elements).  By pointing the last element to the first element you can create a circular structure apt for data buffering.

This is part of the Phabstractic Library.

photo credit: Linked via photopin (license)

Asher Wolfstein

Metaverse Resident

About the Author

A metaverse resident, you can find me on Second Life (kadar.talbot) and other online platforms. I write about my digital life, my musings, and my projects as a programmer, webmaster, artist, and game designer. (exist (be wunk) (use rational imagination) (import artist coder maker furry) (conditional (if (eq you asshole) (me (block you))))

View Articles