Phabstractic: Linked List Data Type

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):

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 a 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):

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

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:

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):

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):

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 like 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):

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:

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.

If you appreciate my programming please help support me through my Patreon.

photo credit: Linked via photopin (license)

Liked it? Take a second to support kadar on Patreon!

kadar

I'm just a wunk, trying to enjoy life. I am a cofounder of http//originalpursuitssoc.com/ and I like computers, code, creativity, and friends.

You may also like...

Leave a Reply

%d bloggers like this: