Linked Lists With SplDoublyLinkedList

As developers, we have times when we get to process a lot of data. Sometimes it’s a few kilobytes of data and we don’t need to worry about the performance of our algorithms because computers are so fast. When we’re looking at gigabytes or more of data we need to be aware of the performance of our algorithms or we might not even be able to complete the process in our lifetime.

In this article, we’ll discuss the linked list data structure and how to use linked lists in PHP.

What Are Data Structures?

Before we go too far into what a linked list is we need to have a small side discussion to discuss data structures.

A data structure is a way of organizing data inside a computer so we can use it effectively.

The overarching idea is that we need to be able to take data and use our code to optimize it so we can process it most efficiently. Depending on the data there are lots of different ways it can be organized but the same kinds of problems keep coming up over and over again so we have a basic set of data structures we can use to solve those problems.

Each of these data structures have different performance characteristics. We’ll use what’s known as the Big O Notation to describe the performance of the data structure with different processes like adding elements, deleting elements, and searching for a specific element as the number of elements gets very large. It can range from O(1) indicating it takes the same amount of time regardless of how many elements exist or O(n) indicating it increases linearly as the number of elements increases up to O(n!) which is something we need to strive to prevent.

There are two major types of data structures.

The first is linear data structures where elements are arranged in a sequence. Examples of this include arrays, lists, stacks, and queues.

The second is non-linear data structures where a linear structure doesn’t work because of operational complexities. Examples include graphs and trees.

Linked List In General

Now that all that background is out of the way let’s talk about Linked Lists in general

Linked lists are a linear data structure that contains elements that are linked to each other. This makes them ideal for representing a list of information that we need to access in the same order every time. Because they’re linked to each other we must access data sequentially and random access is not possible.

Elements in a linked list are named nodes and each node contains a piece of data and a pointer to the next node in the list.

The linked list keeps track of the first element in the list which is also known as the head of the list and the last element in the list, also known as the tail of the list.

When we want to insert or delete items into the list we can do so at the start of the list, the end of the list, or the middle of the list. Because we’re keeping track of the head and tail of the list adding an element there is O(1) but inserting or deleting into the middle of the list is O(n).

Because we need to look at each element, in turn, when we’re searching for an element the worst case will have us run through every element in the list so it’s O(n). This isn’t horrible but it’s not the best outcome for a search so if you’re doing a lot of searches of your data it’s best to look at alternative data structures like a tree.

An extension to linked lists is the double-linked list which operates the same way as a single-link list but each node also keeps track of the previous node in the list. This uses more memory but allows us to easily traverse the list in both directions.

Another possible extension to this logic is a Circular Linked List where the last element contains a link to the first element.

Some benefits of linked lists are that they do not require contiguous blocks of memory and therefore can help reduce memory fragmentation and they support efficient removal and addition of elements.

Linked Lists In PHP

Now that you can proudly say you’re a linked listed expert let’s talk about how to use them in PHP.

I must stress to never create your own implementation of these as it wastes time that could be used to add helpful features to your software. When I was in university I would spend a week implementing each data structure for class and if I was lucky it wouldn’t crash. I can guarantee someone has already uploaded an implementation to GitHub if it isn’t included in our language by default.

Thankfully PHP comes with an implementation of linked lists in the `SplDoublyLinkedList` class structure. It has several built-in functions including the `push()`/`pop()` functions which add or remove the tail element, `shift()`/`unshift()` functions which add or remove head elements.

It’s a doubly linked list so we can iterate through the list both forwards and backward if necessary and there are two ways to do so.

The first is using a `foreach` loop.

$list = new SplDoublyLinkedList();
$list->push("Deanna");
$list->push("Jamir");
$list->push("Essence");
foreach ($list as $value) {
echo $value, PHP_EOL;
}

The other is using some of the other public functions `SplDoublyLinkedList` brings to the party. We have the `rewind()` function to reset our iteration to the head of the list, `valid()` to see if we’ve gone off the end of the list, `current()` to access the current data, and `next()` or `prev()` to go forward or backward in the list respectively.

$list->rewind();
while($list->valid()){
echo $list->current(), PHP_EOL;
$list->next();
}

Foreach is nice for most cases and it’s less code which is generally easier to read but functions are nice if there’s a reason to go backward in the list.

What You Need to Know

• Linked Lists are a tool for keeping a linear list of items
• Good performance inserting/deleting
• Poor performance searching
• Useful for keeping track of histories

The post Linked Lists With SplDoublyLinkedList appeared first on php[architect].