Tag Archive for 'linked lists'

PHP Skip Lists 1: The Quickest Route Home

Published on February 4, 2014 by Bill Sanders in Binary Searches, Linked List and Skip Lists. 0 Comments Tags: , , , .

skiptownA few years ago I created a post on Skip Lists (different blog), and several people told me that it clarified the concept of skip lists for them; so I’m reproducing it here for PHP developers. Using the analogy of rail travel in the New York-Hartford-Boston area, I show how the skip list can work in the world apart from programming. Living in Bloomfield, Connecticut, I’m about halfway between Boston and New York City. Lately they’ve been talking about building a high speed rail to Hartford and on to Springfield, Massachusetts. Naturally, when thinking about such a rail system, I like to think that the really fast part of the trip would be between New York City, Hartford, and Boston. Of course they’d need an express to stop off in New Haven and Springfield. Further, lots of other towns, including Bloomfield, would need some kind of local line. Left to my own devices, I would build the following lines:

Bullet

  1. New York
  2. Hartford
  3. Boston

Express

  1. New York
  2. New Haven
  3. Hartford
  4. Springfield
  5. Boston

Local

  1. New York
  2. Stamford
  3. New Haven
  4. Middletown
  5. Hartford
  6. Bloomfield
  7. Springfield
  8. Boston

Given these choices, I know that I can easily get to Bloomfield by taking the Local at Grand Central Terminal in New York City. However, I’d really like to skip stops in Stamford, New Haven and Middletown. If I took the express, I’d have a stop in New Haven and then on to Hartford where I could get on the Local to Bloomfield. That would be faster, but it would not be the fastest route.

To determine the fastest route, assuming that I have to go in the same direction and cannot backtrack, I diagramed the three lines in Figure 1.

Figure 1: Three train lines between NYC and Boston

Figure 1: Three train lines between NYC and Boston

Looking at Figure 1, it is not too difficult to determine the quickest route between NYC and Bloomfield.

The route that skips the most stops is the quickest route.

Trace your finger from NYC to Bloomfield in Figure 1 and you can determine that route. To see if you found it, look at Figure 2 to see the fastest route highlighted in yellow.

Figure 2: The Route that Skips the Most Stops

Figure 2: The Route that Skips the Most Stops


If you traced the route highlighted in yellow in Figure 2; then you understand how skip lists work. In a similar way, the Binary Search discussed here does not start at the beginning and iterate through an entire ordered list. Rather it splits the list determining the quickest way to the search item.

From Train Lines to Linked Lists

To go to the next step, you need to understand Linked Lists which we discussed in a recent post. What I’d like to do is to transform our train lines into a linked list. The first step is to change the different towns on the lines to nodes in a linked list. Figure 3 shows the first step in this transformation:

Figure 3: From Train Stops to Nodes in a Linked List

Figure 3: From Train Stops to Nodes in a Linked List

My hunch is that if I asked you what was the quickest route to find the value “30” you’d know just what to do. However, the diagram still looks like a train dispatcher’s chart, and so we’ll update it a bit to look more like a linked list. Figure 4 shows this new diagram.

Figure 4: Linked list with multiple pointers<

Figure 4: Linked list with multiple pointers<[/caption] Figure 5: Node with multiple pointers Figure 5: Node with multiple pointers

The arrows now have balls on their tails and look like pointers—and we know that pointers hold a reference to the next node. If we have multiple pointers with some of our nodes, we can have a single linked list that includes pointers that skip certain nodes. Figure 5 shows how that might look in the first node:

Keeping in mind that the linked lists are ordered (sorted) our search for the value “30” would look something like this:

  • Starting point would be on the shortest linked list: 30 is > 25 but < 53.
  • Drop to next level down to the second shortest list: 30 is < 43.
  • Drop to next level down to the third shortest list: 30 == 30. Your search is over.

Now we’re ready to deal with coding skip lists in PHP5. We’ll have to work out the algorithms, and in the next post on skip lists we should be able to have a working skip list that we can use with an iterator pattern.

PHP Iterator Design Pattern III: Linked Lists

Published on January 15, 2014 by Bill Sanders in Iterator and Linked List. Closed Tags: , , , .

chrouslineWhy 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:
PlayAPlayBDownload

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

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.

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

?View Code PHP 
< ?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.

?View Code PHP 
< ?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:

?View Code PHP 
< ?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’