Monthly Archive for January, 2014

Why Linked Lists?

Up to this point, the discussion of iteration has been limited to one kind of data storage—the array. You will find advantages and disadvantages to linked lists versus arrays, but my purpose here is not to convert you to linked lists away from arrays. Rather, linked lists are required for skip lists, and to understand skip lists, you must first understand both the binary search and linked lists. Future posts in the Iterator series will show how an Iterator pattern can be used in both an iteration through a skip list and an array. (The example in Design Patterns: Elements of Reusable Objet-Oriented Software by Gamma, et al [Gang of Four] uses skip lists to show the utility of the Iterator design pattern.)

PHP has a built-in linked list class (SplDoublyLinkedList), but before discussing that class, linked list built from scratch in PHP will help understand exactly what a linked list is. To get started play the two PHP linked list examples and download the files:

What is a Linked List?

A linked list is made up of a number of nodes connected by reference to one another. Each node contains two fields: a “data” field and a “next” field. The data field can contain any kind of data you want and the the “next” field is a pointer to the next linked node. A doubly linked list has pointers to both the next and previous nodes. Take a look at Figure 1 that shows the basic make-up of a linked list:

Figure 1: Basic linked list

One way to think about linked lists is as self-linking lists. Content can be anything you want, including other objects, numbers or strings. It is important to understand that linked lists are not necessarily ordered lists but rather each node controls the next and/or previous link.

Implementing the Linked List in PHP

If you search on the Internet, you can find several different kinds of linked list examples in PHP. The one in this post is most likely different because each node is a separate object (class). Figure 2 shows the class diagram for this particular implementation of a linked list:

Figure 2: Class diagram for implementation of a linked list.

The LinkedList interface includes the two basic requirements for a linked list: content (data) and a pointer to the next node. Like all interface methods, they are abstract by default (without the ‘abstract’ label.)

< ?php
interface LinkedList
{
    function contents();
    function nextUp();
}
?>

With the kind of interface used, the implementations are pretty wide open. Like an array, you can add any kind of data that you want, but you can also include calculated fields returning the results. The nodes for the linked list can easily return different kinds of “cargo” from simple strings as is shown in this example, to numbers, calculated results or just about anything else you might want to throw in. In this particular list, I used different strings with characteristics of OOP programming and languages.

< ?php
class AlphaNode implements LinkedList
{
    function contents()
    {
        return "Dynamic dispatch";
    }
 
    function nextUp()
    {
        return new BetaNode();
    }
}
?>

All of the other nodes are pretty much the same as AlphaNode. Their methods return content or a pointer to the next node. However, on the last node, known as the “terminal node” or the “tail,” you must return a null value. You can have a separate null node that returns null for content and the next node, but all your really need is a termination “next” returning a null value as shown in the “tail” node in this example:

< ?php
class ZetaNode implements LinkedList
{
    function contents()
    {
        return "Loose binding";
    }
    function nextUp()
    {
        return null;
    }
}
?>

Usually you’ll see a “null node” in most implementations, and if you want you can add a separate null node after ZetaNode.
Continue reading ‘PHP Iterator Design Pattern III: Linked Lists’