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.)
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.
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:
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.
Iterating through a Linked List
Because linked lists are self-directed iterators, all you need to do is to start the iteration process and use a loop to traverse from one node to the next. The Client class does just that as can be seen in the following:
ERROR_REPORTING( E_ALL | E_STRICT );
ini_set("display_errors", 1);
function __autoload($class_name)
{
include $class_name . '.php';
}
//Client.php
class Client
{
function __construct()
{
$cr="
|
You will see the following output:
Features of OOP
Dynamic dispatch
Encapsulation
Subtype polymorphism
Object inheritance
Open recursion
Loose binding
Remember, the linked list determines the traversal order.
PHP Built-in Linked List
PHP has its own built-in linked list class, SplDoublyLinkedList. It is made up of 23 methods, including next() and prev(), making it a doubly linked list—one that links to both the next and previous nodes. Another built-in method is setIteratorMode() that determines whether the iteration begins at the first or last node. For those of you who are familiar with array methods in other languages, you will find push() and pop() to act like you’d expect them to in arrays. The push() method acts just like array_push() and pop() like array_pop(). Further methods you are likely to use include, rewind() [goes to the head node], valid() [not null] and current() [content of selected node].
If you’ve ever worked with the stack in programming code, you may be familiar with LIFO–“Last In First Out.” The stack in programming works like a spring-loaded cafeteria tray-holder. The last tray placed on the tray-holder is the first one off. LIFO on the stack works like the tray-holder. It’s very efficient. For the most part, though, when data are placed in an order, we expect that the first element entered will be the first one retrieved. This is FIFO or “First In First Out.” The built-in PHP linked list iterator method can be set for either LIFO or FIFO. In the following example, you can see how the different methods in the SplDoublyLinkedList object work for entering and ordering links:
ERROR_REPORTING( E_ALL | E_STRICT );
ini_set("display_errors", 1);
class LinkedListBuiltIn
{
public function __construct()
{
$listLink = new SplDoublyLinkedList();
$listLink->push('Program');
$listLink->push('to');
$listLink->push('the');
$listLink->push('interface;');
$listLink->push('not');
$listLink->push('the');
$listLink->push('implementation');
echo "Free good advice :
|
You will see the following output:
Free good advice :
Program to the interface; not the implementation
Yoda talk: last in first out:
implementation the not interface; the to Program
The “Yoda” talk is the somewhat backward way the Star Wars character Yoda speaks. (A more informative and useful application of LIFO can be found in the PostScript and FORTH programming languages.)
Linked Lists to Skip Lists
In the next installment of the Iterator design pattern series, we’ll need to see how a linked list fits into a skip list. As you have seen, linked lists are fairly simple, and even better, we have them built right into PHP in the form of a SPL (Standard PHP Library) class. Ideally, we should be able to use the built-in Iterator interface with the built-in SplDoublyLinkedList to create a workable solution to using the fast search capacity of skip lists that work with binary search logic.
Copyright © 2014 - All Rights Reserved
0 Responses to “PHP Iterator Design Pattern III: Linked Lists”