Introduction to Doubly Linked List and Basic Operations in PHP

Doubly linked list is similar to singly linked list where
a singly linked list has a single link to the next element. A doubly linked list has two links: one to the next element and one to the previous element.

You can read more about singly linked list in the previous article:
https://dev.to/matusstafura/introduction-to-singly-linked-list-and-basic-operations-in-php-1d71

Table of Contents

• About Node
• Doubly Linked List
• Constructor
• Print all nodes
• 1. Append
• 2. Get
• 3. Set
• 4. Prepend
• 5. Insert
• 6. Pop First
• 7. Pop Last
• 8. Remove
• Time Complexity

About a Node

In a doubly linked list, a node is a basic unit that stores a piece of data and a reference to the next and previous node in the list.

Here is an example of a node class in doubly linked list in PHP:

class Node
{
    public $value;
    public $next;
    public $prev;

    public function __construct($value)
    {
        $this->value = $value;
        $this->prev = null;
        $this->next = null;
    }
}

This Node class has three fields:
1, data, which stores a value of the element,
2, next, which is a reference to the next node in the list
3, prev, which is a reference to the previous node in the list

Here is an example of how to create a node and link it to another node:

$nodeFirst = new Node(7);
$nodeSecond = new Node(3);

// connect $nodeFirst to nodeSecond with `next`
$nodeFirst->next = $nodeSecond;
// connect $nodeFirst to nodeSecond with `prev` (1)
$nodeSecond->prev = $nodeFirst;
// null<-7<=>3->null

// now you can receive value from second node
$nodeFirst->next->value; // 3
// and get previous value like this
$nodeSecond->prev->value; // 7

NOTICE: This is very similar to singly linked list, we only add reference prev (1) to make it doubly linked list.

This code creates two nodes with data values 7 and 3, and links them together by setting the next field of nodeFirst to nodeSecond and prev of nodeSecond to nodeFirst.

Doubly Linked List

Constructor

Let's create a class that represents a doubly linked list data structure.

This LinkedList class has three instance variables:

• $head: a reference to the first node in the list,
• $tail: a reference to the last node in the list,
• $length: an integer that counts the number of nodes in the list.

NOTICE: If there is only one Node in the list, head and tail points to the same Node.

class DoublyLinkedList
{
    public $head;
    public $tail;
    public $length;

    public function __construct(public $value)
    {
        $newNode = new Node($value);
        $this->head = $newNode;
        $this->tail = $newNode;
        $this->length = 1;
    }
}

NOTE #1: We don't have to initialize a new node in the constructor, but it's convenient to do for this explanation.
NOTE #2: In this article I use integers as data type as a node value.

Print all nodes

Before we move to basic operations, let's create a helper method to print all nodes in the doubly linked list.

EXPLANATION:

In the method printAll() we define a local variable $temp and assigns it the value of $this->head, which is a reference to the first node in the list.

It then enters a while loop that continues until $temp is not null, meaning there is no more next node.

After echoing the value, the function assigns $temp the value of $temp->next, which moves $temp to the next node in the list, to continue the loop.

    // add to DoublyLinkedList class
    public function printAll()
    {
        $temp = $this->head;
        while ($temp != null) {
            echo $temp->value;
            $temp = $temp->next;
        }
        echo PHP_EOL;
    }

1. Append

To append a node means to add a new node at the end of a doubly linked list.

On the left side, we have an example of a doubly linked list with a single node. On the right is the node we want to append. The resulting linked list would look like the one shown at the bottom of the image.

EXPLANATION:

1. we create a new node with a value.
2. if the linked list is empty, we assign the head and tail to the new node because it is the only node in the list.
3. otherwise, we link the new node to the tail with the prev attribute.
4. we link the tail node to the new node with the next attribute.
5. we change the tail reference to the new node.
6. we increase the count (length) of the doubly linked list.

// add to DoublyLinkedList class
    public function append($value)
    {
        $newNode = new Node($value);

        if ($this->length == 0) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->prev = $this->tail;
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }

        $this->length++;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->printAll();
// 2 7 3 9

2. Get

To get a node means to retrieve a node at a certain index in the doubly linked list. The method returns a node object, not just the value of the node.

EXPLANATION:

1. first, we make sure that the index is within the bounds of the doubly linked list; it should be greater than zero and less than the count(length) of the doubly linked list.
2. we assign the head of the list to a temporary variable temp so that we can track our position as we traverse the list.
3. then we loop through the list until we reach the desired index.
4. the method returns the node at the specified index.

// add to DoublyLinkedList class
    public function getNode($index)
    {
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        $temp = $this->head;
        for ($i = 0; $i < $index; $i++) {
            $temp = $temp->next;
        }

        return $temp;
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$node = $dll->getNode(1);
echo $node->value; 
// 7

The script looks like one for a singly linked list and works fine. But we can make it even better because we track the prev node as well.

Why?

Let's say we have a million nodes in the list and we want to get the 999,998th one (the last but one, because the index starts at 0). Instead of looping through almost the entire list, we can traverse from the tail and get it way faster.

There are many ways we can optimize this. This is one approach where we check if the index is in the first half or the second half of the list.

If it is in the first half (from the beginning), we traverse the way we did in the previous example. If it is in the second half, we traverse from the tail. Instead of using the next reference, we use prev.

Like this:

// add to DoublyLinkedList class
    public function getNodeOptimized($index)
    {
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        if ($index < $this->length / 2) {
            $temp = $this->head;
            for ($i = 0; $i < $index; $i++) {
                $temp = $temp->next;
            }
        } else {
            $temp = $this->tail;
            for ($i = $this->length - 1; $i > $index; $i--) {
                $temp = $temp->prev;
            }
        }

        return $temp;
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->getNodeOptimized(3)->value; // one loop from tail instead of three loops from head
$dll->printAll();
// 9

3. Set

To set a node is to replace a value of an existing node at certain index with a new value.

EXPLANATION:

1. we use the existing method getNode() to find the node at the specified index, or return null if the index is out of bound.
2. we assign a new value to the node that was retrieved.

// add to DoublyLinkedList class
    public function setNode($index, $value)
    {
        $temp = $this->getNode($index);
        if ($temp) {
            $temp->value = $value;
        }
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->setNode(1,54); // replaces value at index 1 with value 54
$dll->printAll();
// 2 54 3 9

4. Prepend

To prepend a node means to add a new node at the beginning of a linked list.

On the left is a node we want to prepend and on the left is an existing doubly linked list. The resulting linked list would look like the one shown at the bottom of the image.

EXPLANATION:

1. we create a node.
2. if there are no nodes in the list, we assign the head and tail to the new node.
3. otherwise, we link the new node to the head first.
4. we link the head with the prev attribute to the new node.
5. we change the head reference to the new node.
6. we increment the count (length) of the doubly linked list.

// add to DoublyLinkedList class
    public function prepend($value)
    {
        $newNode = new Node($value);
        if ($this->length == 0) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->next = $this->head;
            $this->head->prev = $newNode;
            $this->head = $newNode;
        }

        $this->length++;
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->prepend(15); // adds a node with value 15 at the beginning
$dll->printAll();
// 15 2 7 3 9

5. Insert

To insert a node in a doubly linked list means to add a new node to the list at a specific position, shifting any subsequent nodes to the right to make room for the new node. For example, if we have a linked list with three nodes(2, 7, 3) and we want to insert a new node (X) between 7 and 3, the resulting linked list would look like (2, 7, X, 3).

EXPLANATION:

1. we check if the index is within the bounds of the list.
2. if the index is 0, we do not need to traverse the list and can use the existing prepend($value) method to insert the new node at the beginning of the list. If the index is the last position in the list (where the index is equal to the length of the list), we can use the append($value) method to insert the new node at the end of the list.
3. otherwise, we create a new node with the given value.
4. we need to find the node at the index immediately before the position where we want to insert the new node. We assign this node to a temporary variable called 'before'.
5. we also need to track the node after the index where we want to insert the new node. We assign this node to a temporary variable called 'after'.
6. we link the new node with the prev attribute to the 'before' node and the next attribute to the 'after' node.
7. we link the before node to the new one (using the next attribute) and we link the after node to the new one (using the prev attribute).
8. finally, we increment the count (length) of the linked list.

// add to DoublyLinkedList class
    public function insert($index, $value)
    {
        if ($index < 0 || $index > $this->length) {
            return null;
        }

        if ($index == 0) {
            $this->prepend($value);
            return;
        }

        if ($index == $this->length) {
            $this->append($value);
            return;
        }

        $newNode = new Node($value);
        $before = $this->getNode($index - 1);
        $after = $before->next;

        $newNode->prev = $before;
        $newNode->next = $after;
        $before->next = $newNode;
        $after->prev = $newNode;

        $this->length++;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->insert(2, 77); // inserts a node with value 77 at index 2
$dll->printAll();
// 2 7 77 3 9

6. Pop First

To pop first means to remove the node at the beginning of the linked list.

EXPLANATION:

1. we check if the linked list is not empty.
2. if there is only one node in the list, we just reset the head and tail to null.
3. otherwise, we create a temporary variable called $temp and assign it the head.
4. we then assign the head to the next node.
5. we reset the prev attribute of the head to null.
6. and unlink $temp by changing temp->next to null.
7. we decrease the count (length) of the linked list.

// add to DoublyLinkedList class
    public function popFirst()
    {
        if ($this->length == 0) {
            return null;
        }

        $temp = $this->head;
        if ($this->length == 1) {
            $this->head = null;
            $this->tail = null;
        } else {
            $this->head = $this->head->next;
            $this->head->prev = null;
            $temp->next = null;
        }

        $this->length--;
        return $temp;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->popFirst(); // removes first node
$dll->printAll();
// 7 3 9

7. Pop Last

To pop last node is to remove the last node in the linked list.

It is faster and easier to remove the last node in a doubly linked list than it is in a singly linked list. We do not need to traverse the entire list to get to the end; we use the existence of the tail and the prev reference.

EXPLANATION:

1. we check if the linked list is not empty.
2. if there is only one node in the linked list, we reset the head and tail to null.
3. we assign the tail to the previous node.
4. we unlink the last node next and prev to null.
5. we decrease the count (length) of the linked list.

// add to DoublyLinkedList class
    public function popLast()
    {
        if ($this->length == 0) {
            return null;
        }
        $temp = $this->tail;
        if ($this->length == 1) {
            $this->head = null;
            $this->tail = null;
        } else {
            $this->tail = $this->tail->prev;
            $this->tail->next = null;
            $temp->prev = null;
        }

        $this->length--;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->popLast(); // removes last node
$dll->printAll();
// 2 7 3

8. Remove

To remove a node from a linked list means to remove it from the list at a certain index and update the next pointers of the surrounding nodes to maintain the integrity of the list.

It is the opposite of the insertion.

EXPLANATION:

1. we check if the index is within the bounds of the linked list.
2. if the index is 0, we can use the popFirst() method to remove the node at the beginning of the list. If the index is the last position in the list (where the index is equal to the length of the list), we can use the popLast() method to remove the node at the end of the list.
3. else, we find the node with existing method getNode().
4. we link the node before and after the node we want to remove.
5. we unlink temp(node to remove) from the list by assigning null to prev and next.
6. we decrease the count (length) of the linked list.

// add to DoublyLinkedList class
    public function remove($index)
    {
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        if ($index == 0) {
            return $this->popFirst();
        }

        if ($index == $this->length - 1) {
            return $this->popLast();
        }

        $temp = $this->getNode($index);

        $temp->next->prev = $temp->prev;
        $temp->prev->next = $temp->next;
        $temp->next = null;
        $temp->prev = null;

        $this->length--;
        return $temp;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->remove(2); // removes node at index 2
$dll->printAll();
// 2 7 9

You can find the full script here: https://gist.github.com/matusstafura/c53bf80421d0b312a9b42193f68ac5ea

Time Complexity

The time complexity for common operations on a doubly linked list is as follows:

• Insertion at the beginning: O(1)
• Insertion at the end: O(1)
• Insertion after a given node: O(1)
• Deletion at the beginning: O(1)
• Deletion at the end: O(1)
• Deletion of a given node: O(1)
• Search: O(n)
• Access: O(n)

Note: these time complexities applies for the doubly linked list with a head and a tail pointer, which allow for efficient insertion and deletion at the beginning and end of the list. Without these pointers, the time complexity for insertion and deletion at the beginning and end of the list would be O(n).