Datastructures in PHP
Tags: php, spl, datastructures, programming
Published: 2019-12-17 12:44:59

---
title: Datastructures in PHP
published: true
description: The development process in PHP is mostly related to the receipt and processing of data from different sources. 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.
tags: php, spl, datastructures, programming
series: php
cover_image: https://thepracticaldev.s3.amazonaws.com/i/gzffk448qiime3v8y3xl.png
canonical_url: https://blog.larapulse.com/php/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.

![Linked list types, single-listed and doubly-linked lists](https://thepracticaldev.s3.amazonaws.com/i/cfaoab8hyd06emt37a4g.png)

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

```php
    $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
```

```php
    $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).

![A properly constructed heap binary tree](https://thepracticaldev.s3.amazonaws.com/i/03nfozkl973a60frsgrg.png)

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

![Read heap tree](https://thepracticaldev.s3.amazonaws.com/i/xhweb2774ba6jj5ogtxm.gif)

```php
    $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.

![Min heap and Max heap](https://thepracticaldev.s3.amazonaws.com/i/e6pai57eusmtc9or2b3l.png)

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

```php
    $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.

```php
$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)
```

```php
$storage = new \SplObjectStorage();
$object = new \stdClass();

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

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

***

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.

***

> **Interesting in reading more about PHP? Follow [this link](https://blog.larapulse.com/php) to find more articles :wink:**