The Spl extension contains dedicated classes for manipulating data structures. The one of the data structures i will describe in this post is the spldoublylinkedlist.
The first Spl datastructure i will talk about in this post is the SplDoublyLinkedList(DLL).
What is the linked list in general? The linked list is a list of nodes linked together in one direction. This means once i know specific node i can move to other nodes as each node has a pointer to the next node.
The DLL provides this functionality and besides it provides that i can traverse backward as well. So in the DLL i can traverse both in forward and backward which provides the functionality of the queue and stack togther.
Class Terminology
class SplDoublyLinkedList implements Iterator, ArrayAccess, Countable, Serializable {
/* Constants */
const int IT_MODE_LIFO = 2;
const int IT_MODE_FIFO = 0;
const int IT_MODE_DELETE = 1;
const int IT_MODE_KEEP = 0;
/* Methods */
public add(int $index, mixed $value): void
public bottom(): mixed
public count(): int
public current(): mixed
public getIteratorMode(): int
public pop(): mixed
public prev(): void
public push(mixed $value): void
public rewind(): void
public valid(): bool
....
....
}The above class terminology provides some of the methods on the SplDoublyLinkedList class. As you see the class implements the Iterator interface so we can iterate over the linked list nodes as an object oriented way.
Example:
$linkedList = new SplDoublyLinkedList();
Pushing items into the list using push() method:
$linkedList->push('USA');
$linkedList->push('England');
$linkedList->push('France');
$linkedList->push('Germany');
$linkedList->push('Spain');
$linkedList->push('Italy');
print_r($linkedList);The push(mixed $value) method pushes elements at the end of the doubly linked list. It accepts a single argument of any type.
Retrieving the size of the list using count() method:
echo "<br/> Number of elements in the list: " . $linkedList->count();
Pop items of the list using the pop() method:
echo $linkedList->pop(); echo "<br/>"; echo $linkedList->pop(); echo "<br/>"; echo $linkedList->pop(); // result Italy Spain Germany
The pop() method pops a node from the end of the list. So every time pop() is called it returns the last pushed node until no other nodes to pop.
The add($index, $value) method using to insert new values at specific index:
$linkedList->add(6, "Russia");
The add() method accepts the index and the value to be inserted. Here i inserted new value at end of the list.
However we can insert values at the middle of the list, in this case the the list nodes will be shuffled not overwritten like so:
$linkedList->add(2, "Poland"); print_r($linkedList); // result SplDoublyLinkedList Object ( [flags:SplDoublyLinkedList:private] => 0 [dllist:SplDoublyLinkedList:private] => Array ( [0] => USA [1] => England [2] => Poland [3] => France [4] => Germany [5] => Spain [6] => Italy [7] => Russia ) )
Note that i you tried to add a node in out of bounds index it will throw OutOfRangeException:
$linkedList->add(10, "Canada"); // Fatal error: Uncaught OutOfRangeException: SplDoublyLinkedList::add(): Argument #1 ($index) is out of range
Because the doubly linked list implements the iterator interface we can iterate over the nodes using a while or for loop.
- Using iteration mode FIFO(First in first out):
$linkedList->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
echo "<ul>";
$linkedList->rewind();
while($linkedList->valid()) {
echo '<li>' . $linkedList->current() . "</li>";
$linkedList->next();
}
echo "</ul>";As i described above that the DLL allows to iterate forward and backward. This is accomplished using the setIteratorMode() method which accepts the mode as constant like shown here.
Next to iterate i used a while loop but first i invoked the rewind() method which reset the iterator pointer to the start of the list. To get the current item value i invoked current() method.
The next() method move the iterator pointer to the next item until the valid() method return false which happens if it reaches the end of the list.
- Using iteration mode LIFO(Last in first out):
echo "<br/>";
$linkedList->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
echo "<ul>";
$linkedList->rewind();
while($linkedList->valid()) {
echo '<li>' . $linkedList->current() . "</li>";
$linkedList->next();
}
echo "</ul>";Here i set the iteration mode to be IT_MODE_LIFO which make the list to be iterated in backward. So if you view the result of this example you will notice that the list nodes is outputted in reversed order. The rest of the code is the same.
Example: ImageViewer
doubly linked lists can be applied in a real world example, it’s a minimal example that i created a simple image viewer script.
The script has two files imagehandler.php which contains the necessary functions and viewer.php which displays an html document along with the image to be displayed and some controls.
imagehandler.php
<?php
$linkedList = new SplDoublyLinkedList();
function scanImages($directory)
{
global $linkedList;
$images = glob("$directory/*.{jpg,png,gif}", GLOB_BRACE);
foreach($images as $image) {
$linkedList->push($image);
}
}
function getImagesCount()
{
global $linkedList;
return $linkedList->count();
}
function getCurrentOffset()
{
global $linkedList;
$currentOffset = isset($_REQUEST['offset']) && is_numeric($_REQUEST['offset']) ? $_REQUEST['offset'] : 0;
$currentOffset = $currentOffset >= $linkedList->count() ? $linkedList->count() - 1 : ($currentOffset < 0 ? 0 : $currentOffset);
return $currentOffset;
}
function displayImage()
{
global $linkedList;
$currentOffset = getCurrentOffset();
return $linkedList->offsetGet($currentOffset);
}
viewer.php
<?php
require_once './imagehandler.php';
scanImages("./files");
?>
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Image viewer</title>
<style>
#controls a {
border: 3px solid #ccc;
padding: 2px 23px;
background-color: aquamarine;
color: black;
text-decoration: none;
font-size: 25px;
font-weight: bold;
}
.prev {
float: left;
}
.next {
float: right;
}
#offset-wrapper {
text-align: center;
}
#offset-wrapper input[type=number] {
width: 10%;
height: 31px;
text-align: center;
}
#offset-wrapper input[type=button] {
width: 7%;
height: 38px;
}
</style>
</head>
<body>
<div style="margin: 100px 400px;">
<img src="<?= displayImage(); ?>" width="100%" height="340" />
<div id="controls">
<a class="prev" href="./viewer.php?offset=<?= getCurrentOffset() == 0 ? 0 : getCurrentOffset()-1 ?>">←</a>
<div id="offset-wrapper">
<input type="number" id="offset" value="<?= isset($_REQUEST['offset']) ? $_REQUEST['offset'] : 0 ?>" />
<input type="button" value="Go" onclick="window.location.href='./viewer.php?offset=' + document.getElementById('offset').value;" />
</span>
<a class="next" href="./viewer.php?offset=<?= getCurrentOffset() == getImagesCount() - 1 ? getImagesCount() - 1 : getCurrentOffset()+1 ?>">→</a>
</div>
</div>
</body>
</html>
In the imagehandler.php i created some functions to scan a specific images directory and store those images as a linked list. This is the scanImages() function which accepts a directory path and using glob() php function to scan all image files then loop through them and push them into the linked list.
The getImagesCount() and getCurrentOffset() returns the list size and the current offset respectively.
Then the displayImage() function displays the current node (current image path) according to the current index.
The other file viewer.php i displayed an html document which contains the image to be displayed and two buttons to navigate left and right and an input to enter the index number.
Although this is a simple example you can enhance it with javascript to disable page reload when navigating left or right.
