Implementing a linked list

A linked list is where one list contains keys that point to keys in another list. An analogy, in database terms, would be where you have a table that contains data, and a separate index that points to the data. One index might produce a list of items by ID. Another index might yield a list according to title and so on. The salient feature of the linked list is that you do not have to touch the original list of items.

For example, in the diagram shown next, the primary list contains ID numbers and the names of fruits. If you were to directly output the primary list, the fruit names would display in this order: Apple, Grape, Banana, Orange, Cherry. If you were to use the linked list as an index, on the other hand, the resulting output of fruit names would be Apple, Banana, Cherry, Grape, and Orange:

How to do it...

One of the primary uses of a linked list is to produce a display of items in a different order. One approach would be to create an iteration of key value pairs, where the key represents the new order, and the value contains the value of the key in the primary list. Such a function might look like this:
```
function buildLinkedList(array $primary,
                         callable $makeLink)
{
  $linked = new ArrayIterator();
  foreach ($primary as $key => $row) {
    $linked->offsetSet($makeLink($row), $key);
  }
  $linked->ksort();
  return $linked;
}
```
We use an anonymous function to generate the new key in order to provide extra flexibility. You will also notice that we do a sort by key (ksort()) so that the linked list iterates in key order.
All we need to do to use the linked list is to iterate through it, but produce results from the primary list, $customer in this example:
```
foreach ($linked as $key => $link) {
  $output .= printRow($customer[$link]);
}
```
Note that in no way do we touch the primary list. This allows us to generate multiple linked lists, each representing a different order, while retaining our original set of data.

Another important use of a linked list is for the purposes of filtering. The technique is similar to that shown previously. The only difference is that we expand the buildLinkedList() function, adding a filter column and filter value:

function buildLinkedList(array $primary,
                         callable $makeLink,
                         $filterCol = NULL,
                         $filterVal = NULL)
{
  $linked = new ArrayIterator();
  $filterVal = trim($filterVal);
  foreach ($primary as $key => $row) {
    if ($filterCol) {
      if (trim($row[$filterCol]) == $filterVal) {
        $linked->offsetSet($makeLink($row), $key);
      }
    } else {
      $linked->offsetSet($makeLink($row), $key);
    }
  }
  $linked->ksort();
  return $linked;
}

We only include items in the linked list where the value represented by $filterCol in the primary list matches $filterVal. The iteration logic is the same as that shown in step 2.
Finally, another form of linked list is the doubly linked list. In this case, the list is constructed in such a manner that the iteration can occur in either a forward or reverse direction. In the case of PHP, we are fortunate to have an SPL class, SplDoublyLinkedList, which neatly does the trick. Here is a function that builds a doubly linked list:
```
function buildDoublyLinkedList(ArrayIterator $linked)
{
  $double = new SplDoublyLinkedList();
  foreach ($linked as $key => $value) {
    $double->push($value);
  }
  return $double;
}
```
Note
The terminology for SplDoublyLinkedList can be misleading. SplDoublyLinkedList::top() actually points to the end of the list, whereas SplDoublyLinkedList::bottom() points to the beginning!

How it works...

Copy the code shown in the first bullet into a file, chap_10_linked_list_include.php. In order to demonstrate the use of a linked list, you will need a source of data. For this illustration, you can make use of the customer.csv file that was mentioned in earlier recipes. It is a CSV file with the following columns:

"id","name","balance","email","password","status","security_question",
"confirm_code","profile_id","level"

You can add the following functions to the include file mentioned previously to generate a primary list of customers, and to display information about them. Note that we use the first column, id as the primary key:

function readCsv($fn, &$headers)
{
  if (!file_exists($fn)) {
    throw new Error('File Not Found');
  }
  $fileObj = new SplFileObject($fn, 'r');
  $result = array();
  $headers = array();
  $firstRow = TRUE;
  while ($row = $fileObj->fgetcsv()) {
    // store 1st row as headers
    if ($firstRow) {
      $firstRow = FALSE;
      $headers = $row;
    } else {
      if ($row && $row[0] !== NULL && $row[0] !== 0) {
        $result[$row[0]] = $row;
      }
    }
  }
  return $result;
}

function printHeaders($headers)
{
  return sprintf('%4s : %18s : %8s : %32s : %4s' . PHP_EOL,
                 ucfirst($headers[0]),
                 ucfirst($headers[1]),
                 ucfirst($headers[2]),
                 ucfirst($headers[3]),
                 ucfirst($headers[9]));
}

function printRow($row)
{
  return sprintf('%4d : %18s : %8.2f : %32s : %4s' . PHP_EOL,
                 $row[0], $row[1], $row[2], $row[3], $row[9]);
}

function printCustomer($headers, $linked, $customer)
{
  $output = '';
  $output .= printHeaders($headers);
  foreach ($linked as $key => $link) {
    $output .= printRow($customer[$link]);
  }
  return $output;
}

You can then define a calling program, chap_10_linked_list_in_order.php, which includes the file defined previously, and reads customer.csv:

<?php
define('CUSTOMER_FILE', __DIR__ . '/../data/files/customer.csv');
include __DIR__ . '/chap_10_linked_list_include.php';
$headers = array();
$customer = readCsv(CUSTOMER_FILE, $headers);

You can then define an anonymous function that will produce a key in the linked list. In this illustration, define a function that breaks down column 1 (name) into first and last names:

$makeLink = function ($row) {
  list($first, $last) = explode(' ', $row[1]);
  return trim($last) . trim($first);
};

You can then call the function to build the linked list, and use printCustomer() to display the results:

$linked = buildLinkedList($customer, $makeLink);
echo printCustomer($headers, $linked, $customer);

Here is how the output might appear:

To produce a filtered result, modify buildLinkedList() as discussed in step 4. You can then add logic that checks to see whether the value of the filter column matches the value in the filter:

define('LEVEL_FILTER', 'INT');

$filterCol = 9;
$filterVal = LEVEL_FILTER;
$linked = buildLinkedList($customer, $makeLink, $filterCol, $filterVal);

There's more...

PHP 7.1 introduced the use of [ ] as an alternative to list(). If you look at the anonymous function mentioned previously, you could rewrite this in PHP 7.1 as follows:

$makeLink = function ($row) {
  [$first, $last] = explode(' ', $row[1]);
  return trim($last) . trim($first);
};

For more information, see https://wiki.php.net/rfc/short_list_syntax.

Previous Chapter

Using getters and setters

Next Chapter

Building a bubble sort

Table of Contents for PHP 7: Real World Application Development

Implementing a linked list

How to do it...

Note

How it works...

There's more...

Table of Contents for
PHP 7: Real World Application Development