# Datastructures

## Table of Contents

- SplDoublyLinkedList
- SplStack
- SplQueue
- SplHeap
- SplMaxHeap
- SplMinHeap
- SplPriorityQueue
- SplFixedArray
- ArrayObject
- SplObjectStorage

SPL provides a set of standard datastructures. 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 or 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.

- SplDoublyLinkedList
  - SplStack
  - SplQueue

## Heaps

Heaps are tree-like structures that follow the heap-property: each node is greater than or equal to its children, when compared using the implemented compare method which is global to the heap.

- SplHeap
  - SplMaxHeap
  - SplMinHeap
- SplPriorityQueue

## Arrays

Arrays are structures that store the data in a contiguous way, accessible via indexes.

> Note: Do not confuse this with PHP's native array type. PHP arrays are in reality ordered hashtables. However, SPL provides the ArrayObject class to wrap PHP arrays into an object.

- SplFixedArray

## Map

A map is a datastructure holding key-value pairs. PHP arrays can be seen as maps from integers/strings to values. SPL provides a map from objects to data. This map can also be used as an object set.

- SplObjectStorage

`↑` and `↓` to navigate • `Enter` to select • `Esc` to close • `/` to open