After knowing the concepts of arrays, it’s time to learn other data-structures of PHP offered. SPL provides a set of standard data structures. They are grouped here by their underlying implementation which usually defines their general field of application.

  • Doubly Linked Lists

A Doubly Linked List (DLL) is a list of nodes linked in both directions to each other. Iterator’s operations, access to both ends, addition and removal of nodes have a cost of O (1) when the underlying structure is a DLL. It hence provides a decent implementation for stacks and queues.

Generally we can implement doubly linked list in PHP through SplDoublyLinkedList class

Introduction

The SplDoublyLinkedList class provides the main functionalities of a doubly linked list.

Notes:

  • Iteration Direction

SplDoublyLinkedList::IT_MODE_LIFO

The list will be iterated in a last in, first out order, like a stack.

SplDoublyLinkedList::IT_MODE_FIFO

The list will be iterated in a first in, first out order, like a queue.

  • Iteration Behavior

SplDoublyLinkedList::IT_MODE_DELETE

Iteration will remove the iterated elements.

SplDoublyLinkedList::IT_MODE_KEEP

Iteration will not remove the iterated elements.

Let’s do some operations on linked list….

Methods to remember:

  • SplDoublyLinkedList() -> use to create linked list
  • push() -> helps to push elements at the end of the list.
  • top() -> prints the top of the linked list.
  • bottom() -> print the first element of the LL.

File – code1.php

<?php
//FIFO and LIFO in SplDoublyLinkedList
 
$list = new SplDoublyLinkedList();
$list->push(‘a’);
$list->push(‘b’);
$list->push(‘c’);
$list->push(‘d’);
 
echo “FIFO (First In First Out) :\n”;
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current().”\n”;
}
 
echo “<br>LIFO (Last In First Out) :\n”;
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current().”\n”;
}
 
echo “<br> linked list with keys: \n “;
print_r($list);
echo “<br>top of the element in Linked list “;
echo $list->top();
echo PHP_EOL;
echo “<br> bottom(first) element on of linked list: “;
//Array first value
echo $list->bottom();
echo PHP_EOL;
 
echo “<br>linked list length: “;
echo $list->count();
?>
output

  • Stack – this data-structure work as LIFO(Last-In-first-Out) order.

The SplStack class

Introduction

The SplStack class provides the main functionalities of a stack implemented using a doubly linked list.

Methods and usage:

add() -> SplDoublyLinkedList::add — Add/insert a new value at the specified index

Description

public SplDoublyLinkedList::add(int $index, mixed $value): void

Insert the value value at the specified index, shuffling the previous value at that index (and all subsequent values) up through the list.

  • push() -> push element into top of the stack(insert from end into stack)
  • pop() -> pop element from stack.(top of the stack)
  • top() -> print the top of the stack.

File – code2.php

<?php
//SplStack Mode is LIFO (Last In First Out)
$stk = new SplStack();
 
// you can add element individually…
$stk[] = 1;
$stk[] = 20;
$stk[] = -3;
// you can also use push() method to insert element into stack from top of stack
$stk->push(42);
$stk->push(12);
$stk->push(67);
$stk->push(97);
$stk->push(500);
$stk->push(101);
 
echo ” stack is: “;
foreach ($stk as $elem)  {
    echo $elem.”\n”;
   }
 
// top of the stack is using top() method
echo “<br> top of the stack is: “;
echo $stk->top();
 
// pop operation using pop() method
$n = $stk->pop();
echo “<br> pop element is: $n”;
 
// 3 times doing pop() operation..
$stk->pop();
$stk->pop();
$stk->pop();
 
echo “<br> Now, stack is: “;
foreach ($stk as $elem)  {
    echo $elem.”\n”;
   }
 
   // adding element at specific location using add() method.
// adding value ‘420’ at index->1, value ‘560’at index->3
$stk->add(1,420);
$stk->add(3,560);
 
echo “<br> Now, stack is: “;
foreach ($stk as $elem)  {
    echo $elem.”\n”;
   }
 
?>
output

  • Queue

Queue data-structure inserts elements at FIFO order.

Introduction

The SplQueue class provides the main functionalities of a queue implemented using a doubly linked list.

Class synopsis

class SplQueue extends SplDoublyLinkedList {

/* Inherited constants */

public const int SplDoublyLinkedList::IT_MODE_LIFO;

public const int SplDoublyLinkedList::IT_MODE_FIFO;

public const int SplDoublyLinkedList::IT_MODE_DELETE;

public const int SplDoublyLinkedList::IT_MODE_KEEP;

Methods usage…

  • SplQueue() -> helps to create queue
  • enqueue() -> SplQueue::enqueue — Adds an element to the queue(insert from first-end)
  • dequeue() -> delete element from last-end.
  • count() -> helps to count length of queue.

File – code3.php

<?php
$q = new SplQueue();
 
// insert item into Queue
$q->enqueue(20);
$q->enqueue(40);
$q->enqueue(-70);
// insert item manually…
$q[]=700;
$q[]=950;
$q[]=-1050;
 
echo “Queue is: “;
foreach ($q as $item) {
    echo ” “.$item;
}
 
// dequeue() method helps to ‘dequeue’ operation…
// remove element->20
$q->dequeue();
// remove element->40
$q->dequeue();
 
echo “<br> after dequeue, Queue becomes: “;
foreach ($q as $item) {
    echo ” “.$item;
}
 
echo “<br> Queue length is: “.$q->count();
?>
output

download notes

download code.zip