Doubly-Linked List, Stacks and Queues in PHP

A data structure is a way of sorting and organizing data inside memory to be used efficiently.

PHP supports a number of data structures such as Doubly-Linked lists, Stacks, Queues, and more.

This post covers the Doubly-Linked List as well as Stacks and Queues.

#Doubly Linked List

A Doubly Linked List is a data structure consisting of sequentially linked records called nodes. Each node (also called an element) knows about its neighbors -- the preceding and following elements.

In this diagram, element 99 knows about both 12 and 37.

Doubly Linked List uses these terms to deal with the list:

• push: pushes an element at the end of the list.
• unshift: prepends the list with an element.
• shift: shifts (remove) a node from the beginning of the list.
• pop: pops (remove) a node from the end of the list.

PHP supports the Doubly Linked List through the SplDoublyLinkedList class.

Here it is in practice:

$list = new SplDoublyLinkedList();

$list->push('C++');
$list->push('PHP');
$list->push('Python');
$list->push('Go');
$list->push('C');

$list->pop(); // Removes "C"
$list->shift(); // Removes "C++"

foreach ($list as $item) {
    echo $item.PHP_EOL;
}

PHP
Python
Go

You can use the array notation instead of the push method:

$list[] = 'Swift';

Use the add method to insert a new value at a specific index:

$list->add(2, 'Java');

By default, SplDoublyLinkedList works on the basis of FIFO (first in, first out). Every element you push becomes the first one when iterating over the list. This behavior can be changed to LIFO (last in, first out), which is the opposite of FIFO.

$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);

Swift
C
Go
Java
Python
PHP

You can also use IT_MODE_FIFO for the FIFO mode (the default).

To remove iterated elements, set the iterator mode to IT_MODE_DELETE:

$list = new SplDoublyLinkedList();
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_DELETE);

$list->push('PHP');
$list->push('Python');
$list->push('Go');

foreach ($list as $item) {
    echo $item . PHP_EOL;
}

// rewind has no effect here, because we already removed all the elements
$list->rewind();

// This foreach won't show anything
foreach ($list as $item) {
    echo $item . PHP_EOL;
}

Internally, the rewind method is not invoked when using IT_MODE_DELETE.

Use the top / bottom methods to get the first and last elements in the list:

$list = new SplDoublyLinkedList();
$list->push('C++');
$list->push('PHP');
$list->push('Python');

echo $list->top(); // Python
echo $list->bottom(); // C++

The SplDoublyLinkedList class extends the ArrayAccess iterator, which means you can use ArrayAccess methods such as offsetExists, offsetGet, offsetUnset.

#Stacks

A stack works on the principle of LIFO (last in, first out). The first item is at the bottom of the stack, the most recent is at the top:

$list = new SplStack();
$list->push('Go');
$list->push('PHP');
$list->push('Python');

foreach ($list as $item) {
    echo $item.PHP_EOL;
}

Python
PHP
Go

#Queues

A queue works on the principle of FIFO (first in, first out), just like the Doubly-Linked List.

Both SplStack and SplQueue extend the DoublyLinkedList class.

The queue uses its own terminology. Instead of push and offsetUnset, use the enqueue and dequeue methods:

$list = new SplQueue();

$list->enqueue('C++');
$list->enqueue('PHP');
$list->enqueue('Python');

foreach ($list as $item) {
    echo $item."\n";
}

C++
PHP
Python

#Summary

• Doubly Linked List -- a data structure where each node knows about its preceding and following neighbors, supported in PHP via SplDoublyLinkedList.
• FIFO vs LIFO -- SplDoublyLinkedList defaults to FIFO (first in, first out) but can be switched to LIFO (last in, first out) using setIteratorMode.
• Stacks -- work on the LIFO principle using SplStack, where the most recently pushed element comes out first.
• Queues -- work on the FIFO principle using SplQueue, with enqueue and dequeue methods instead of push and pop.