Linked Lists

A linked list is a data structure made up of nodes. Each node contains data, and a single pointer to it’s parent node. Because of the way linked lists are structured, the final node at the bottom of the list is the starting point to traverse the rest of the list.

Linked lists can be used to implement data types such as queues, stacks and lists. They are great for situations where you would need to prioritise data nodes, and they generally offer a lot more flexibility than arrays in languages like Java . On the other hand, they don’t give direct access to each node like an array does.

Arrays in PHP generally offer the same functionality as a linked list. In most languages, using a linked list would offer a performance benefit over an array. A manual linked list implementation in PHP would generally be slower than an array.

In PHP, the SPL library offers an implementation of a double linked list. In a double linked list, nodes contain pointers to both the previous and the next nodes.

Using the SPL implementation of a double linked list, we don’t have to worry about taking performance hit since SPL libraries are written in C, they would perform a lot faster than a PHP implementation.