Datastructures in PHP

The development process in PHP is mostly related to the receipt and processing of data from different sources, such as databases, local files, remote APIs, etc. Developers spend a lot of time organizing data, getting, moving and processing it. The most used structure for representing data in PHP is an array. However, in some cases, arrays are not suitable for solving problems due to insufficient performance and excessive memory consumption, and therefore more appropriate data structures are required.

Usage of the Standard PHP Library, SPL and knowledge of its composition is an area whose possession can confirm the competence of the PHP developer.

SPL is like patterns, but purely for data. Mostly it doesn't simplify writing of code, but simplify its understanding by others (or by yourself after a while). Of course, if you used it well and right.

Doubly-linked lists

SplDoublyLinkedList - Doubly-linked lists are a variation on "standard" linked lists where each node has a pointer to the previous node as well as a pointer to the next node.

Imagine that you are in the queue at the bank and at the same time you can see only the person in front of you and behind you. This is an analogy of the relationship between the elements in the SplDoublyLinkedList. Inserting an item into the list corresponds to the situation when someone climbed into the queue, and you suddenly forgot who was standing in front of you (and this someone forgot about you). A doubly-linked list allows you to efficiently bypass and add large data sets without re-hashing.

• SplDoublyLinkedList
  • SplStack
  • SplQueue

SplQueue and SplStack are very similar to SplDoublyLinkedList. Both these structures, in fact, are doubly linked lists with different iterator flags (IT_MODE_LIFO - Last In First Out, and IT_MODE_FIFO - First In First Out), which regulate the order of node processing and what to do with these elements after they have been processed. Another difference between these structures is that the SplQueue interface contains more intuitive enqueue() and dequeue() methods, unlike the push() and pop() methods of SplStack.

    $stack = new SplStack();

    // add items to the stack
    $stack->push('1'); 
    $stack->push('2');
    $stack->push('3');

    echo $stack->count();       // 3
    echo $stack->top();         // 3
    echo $stack->bottom();      // 1
    echo $stack->serialize();   // i:6;:s:1:"1";:s:1:"2";:s:1:"3";

    // retrieve items from the stack
    echo $stack->pop(); // 3
    echo $stack->pop(); // 2
    echo $stack->pop(); // 1

    $queue = new SplQueue();

    $queue->setIteratorMode(SplQueue::IT_MODE_DELETE);

    $queue->enqueue('one');
    $queue->enqueue('two');
    $queue->enqueue('three');

    $queue->dequeue();
    $queue->dequeue();

    echo $queue->top(); // three

Stacks are widely used in the analysis or processing of nested data structures, in particular in the calculation of mathematical expressions.Queues could be used when processing the lists of "jobs" or some tasks, as parsing the text input in the form of a list of individual elements, normalizing it in one cycle, and then process the normalized list in the other.

Heaps

Heaps are complete binary tree structures, that should satisfy heap-order property: each node is greater than or equal to the data stored in its children. Each level of a tree is completely filled, except possibly the bottom level (at this level it is filled from left to right).

• SplHeap
  • SplMaxHeap
  • SplMinHeap
• SplPriorityQueue

SplHeap is a heap represented as a binary tree, each node of which has no more than two child nodes. This is an abstract class that requires an implementation of the compare() method, which allows real-time sorting while inserting new nodes into a tree.

    $heap = new SplMaxHeap();
    $heap->insert('111');
    $heap->insert('222');
    $heap->insert('333');

    echo $heap->extract(); // 333
    echo $heap->extract(); // 222
    echo $heap->extract(); // 111
    echo $heap->extract(); // Exception: Can't extract from an empty heap

    $heap = new SplMinHeap();
    $heap->insert('111');
    $heap->insert('222');
    $heap->insert('333');

    echo $heap->extract(); // 111
    echo $heap->extract(); // 222
    echo $heap->extract(); // 333
    echo $heap->extract(); // Exception: Can't extract from an empty heap

SplMaxHeap and SplMinHeap are concrete implementations of the abstract class SplHeap. SplMaxHeap implements the compare() method so that the tree is sorted in descending order of node values, and SplMinHeap is in ascending order of values.

SplPriorityQueue is a queue similar to SplHeap, but unlike SplHeap, sorting based on the value of the priority property assigned to each node.

    $queue = new SplPriorityQueue();
    $queue->setExtractFlags(SplPriorityQueue::EXTR_DATA); // extract only values of elements

    $queue->insert('Q', 1);
    $queue->insert('W', 2);
    $queue->insert('E', 3);
    $queue->insert('R', 4);
    $queue->insert('T', 5);
    $queue->insert('Y', 6);

    $queue->top(); 

    while ($queue->valid()) { 
        echo $queue->current(); 
        $queue->next(); 
    }
    //YTREWQ

Arrays

SplFixedArray is an array of fixed length, the indixes of which can be only integers (which are greater than or equals 0). These restrictions provide a higher processing speed of the array, which is achieved, due to the fact that in SplFixedArray there is no hashing of the keys of the elements when they are added (in contrast to the usual arrays). The length could be changed, but this is a costly operation.

Map

SplObjectStorage is an object storage, that provides an interface for mapping objects to data, or can be used as a container for multiple objects. Allows you to use an object as a key of associative array and associate it with some data.

$storage = new SplObjectStorage();

$o1 = new StdClass;
$o2 = new StdClass;

$storage->attach($o1);

var_dump($storage->contains($o1)); // bool(true)
var_dump($storage->contains($o2)); // bool(false)

$storage->detach($o1);

var_dump($storage->contains($o1)); // bool(false)
var_dump($storage->contains($o2)); // bool(false)

$storage = new SplObjectStorage();
$object = new StdClass;

$storage[$object] = "data from object";

echo $storage[$object]; // data from object

TL;DR: Conclusion

PHP isn't C. That’s all you should remember while working with data. You can't expect that a super dynamic language like PHP has the same highly efficient memory usage that C has. But if you do want to save memory you could consider using an SPL for large, static arrays.