Doubly Linked Lists – Data Structures in PHP

Reading Time: 10 minutes

Read the previous article on Singly Linked Lists in PHP here!

Read the starting post of the series here!

All code in this series can be found on Github

Doubly Linked List Principles

The list consists of nodes, which contain data
Each node contains a reference or pointer to the next node, and unlike Singly Linked Lists, the node also contains a pointer to the previous node.
The first node of the list is called the head
The prev pointer in the head node points to null
the next pointer in the last node of the list (the tail) points to null

Available Methods

I took a decent amount of time to read through various array and list methods available to other languages like Java and JavaScript to help inform what additional methods would possibly be useful for a DoublyLinkedList class in PHP. Additionally, I also added some new elements to the Node class to make it more useful for future applications.

In the DoublyLinkedList class, I have implemented the following methods:

add($data) – Adds a new node to the end of the list
addAt($position, $data) – Add a new node at the specified position
addFirst($data) – Add a new node to the beginning of the list
delete($data) – Deletes all nodes with the specified data
deleteLast() – Delete the last node in the list
deleteFirst() – Delete the first node in the list
deleteAt($position) – Removes the node at the specified position
length() – Returns the length of the list (number of nodes)
get() – Returns the head node of the list
getAt($position) – Gets the node at a given position
toArray() – Return an array of all nodes in the list
clear() – Removes all nodes from the list
max() – Returns the node with the max value
min() – Returns the node with the min value
dedupe() – Returns a new LinkedList with no duplicate values
unique() – Returns a new LinkedList with only the unique values
reverse() – Returns a new list with the nodes in reverse order
contains($data) – Checks if the LinkedList contains the $data
forEach($callback) – Iterates over each node in the list with a callback
sortAsc() – Returns a new LinkedList sorted in ascending order
sortDesc() – Returns a new LinkedList sorted in descending order
sort($callback) – Returns a new LinkedList sorted using a callback
average() – Returns the average value of all nodes in the list
median() – Returns the median value of all nodes in the list
mode() – Returns the mode value of all nodes in the list
join($list) – Returns a new LinkedList with the nodes of both lists

And here’s some of the Node class’s new methods and properties:

Properties:

$data – contains the data of the node
$prev – pointer to the previous node in the list (nullable)
$next – pointer to the next node in the list (nullable)
$left – pointer to the left child node in a tree (nullable, not implemented yet)
$right – pointer to the right child node in a tree (nullable, not implemented yet)
$parent – pointer to the parent node in a tree (nullable, not implemented yet)

Methods:

getData() – returns the $data of the node
getLeft() – returns the left pointer (Node || null)
getRight() – returns the right pointer (Node || null)
getParent() – returns the parent pointer (Node || null
isStart() – returns true if the node is the start of a data structure
isEnd() – returns true if the node is the end of a data structure

Implementation

DoublyLinkedList Class

Copy Code

<?php

namespace DataStructures;

use OutOfBoundsException;

class DoublyLinkedList
{

    public Node|null $head;

    /**
     * LinkedList default constructor
     */
    public function __construct()
    {
        $this->head = null;
    }

    /**
     * add a new node to the doubly linked list
     *
     * @param $data
     * @return void
     */
    public function add($data): void
    {
        $node = new Node($data);
        if ($this->head == null) {
            $this->head = $node;
        } else {
            $current = $this->head;
            while ($current->next != null) {
                $current = $current->next;
            }
            $current->next = $node;
            $node->prev = $current;
        }
    }

    /**
     * add a new node at a specific position
     *
     * @param $position
     * @param $data
     * @return void
     */
    public function addAt($position, $data): void
    {
        $node = new Node($data);
        $current = $this->head;
        $previous = null;
        $i = 0;
        if ($position == 0) {
            $node->next = $this->head;
            $this->head = $node;
        } else {
            while ($i < $position) {
                $i++;
                $previous = $current;
                $current = $current->next;
            }
            $node->next = $current;
            $previous->next = $node;
            $node->prev = $previous;
            $current->prev = $node;
        }
    }

    /**
     * Adds a new node to the beginning of the list
     *
     * @param $data
     * @return void
     */
    public function addFirst($data): void
    {
        $node = new Node($data);
        if ($this->head != null) {
            $node->next = $this->head;
            $this->head->prev = $node;
        }
        $this->head = $node;
    }

    /**
     * Removes any node(s) with the given data from the list
     *
     * @param $data
     * @return void
     */
    public function delete($data): void
    {
        $current = $this->head;
        $previous = null;
        while ($current != null) {
            if ($current->data == $data) {
                if ($previous == null) {
                    $this->head = $current->next;
                    $this->head->prev = null;
                } else {
                    $previous->next = $current->next;
                    $current->next->prev = $previous;
                }
                return;
            }
            $previous = $current;
            $current = $current->next;
        }
    }

    /**
     * removes the last node from the list
     *
     * @return void
     */
    public function deleteLast(): void
    {
        $current = $this->head;
        $previous = null;
        while ($current->next != null) {
            $previous = $current;
            $current = $current->next;
        }
        $previous->next = null;
    }

    /**
     * removes the first node of the list
     * @return void
     */
    public function deleteFirst(): void
    {
        $this->head = $this->head->next;
        $this->head->prev = null;
    }

    /**
     * removes the node at a specific position in the linked list
     * throws an OutOfBoundsException if the position is out of bounds
     *
     * @param $position
     * @return void
     * @throws OutOfBoundsException
     */
    public function deleteAt($position): void
    {
        if ($position > ($this->length() - 1) || $position < 0) {
            throw new OutOfBoundsException("$position is out of bounds");
        } else {
            $current = $this->head;
            $previous = null;
            $i = 0;
            while ($current != null) {
                if ($i == $position) {
                    if ($previous == null) {
                        $this->head = $current->next;
                        $this->head->prev = null;
                    } else {
                        $previous->next = $current->next;
                        $current->next->prev = $previous;
                    }
                }
                $previous = $current;
                $current = $current->next;
                $i++;
            }
        }
    }

    /**
     * returns the size of the linked list as an int
     *
     * @return int
     */
    public function length(): int
    {
        $current = $this->head;
        $length = 0;
        while ($current != null) {
            $length++;
            $current = $current->next;
        }
        return $length;
    }

    /**
     * returns the head node of the linked list
     *
     * @return Node
     */
    public function get(): Node
    {
        return $this->head;
    }

    /**
     * returns the node at a specific position in the linked list
     * returns null if the node is empty
     * throws an OutOfBoundsException if the position is out of bounds
     *
     * @param $position
     * @return Node|null
     * @throws OutOfBoundsException
     */
    public function getAt($position): Node|null
    {
        if ($position > ($this->length() - 1) || $position < 0) {
            throw new OutOfBoundsException("$position is out of bounds");
        } else {
            $current = $this->head;
            $i = 0;
            while ($current != null) {
                if ($i == $position) {
                    return $current;
                }
                $i++;
                $current = $current->next;
            }
            return null;
        }
    }

    /**
     * Converts the data in the linked list to an array
     *
     * @return array
     */
    public function toArray(): array
    {
        $array = [];
        $current = $this->head;
        while ($current != null) {
            $array[] = $current->data;
            $current = $current->next;
        }
        return $array;
    }

    /**
     * unlinks all nodes in the list
     *
     * @return void
     */
    public function clear(): void
    {
        $this->head = null;
    }

    /**
     * returns the node with the maximum $data value
     *
     * @return Node|null
     */
    public function max(): Node|null
    {
        $current = $this->head;
        $max = $current;
        while ($current != null) {
            if ($current->data > $max->data) {
                $max = $current;
            }
            $current = $current->next;
        }
        return $max;
    }

    /**
     * returns the node with the minimum $data value
     *
     * @return Node|null
     */
    public function min(): Node|null
    {
        $current = $this->head;
        $min = $current;
        while ($current != null) {
            if ($current->data < $min->data) {
                $min = $current;
            }
            $current = $current->next;
        }
        return $min;
    }

    /**
     * Returns a new DoublyLinkedList with duplicate values removed
     *
     * @return DoublyLinkedList
     */
    public function dedupe(): DoublyLinkedList
    {
        $deduped = new DoublyLinkedList();
        $current = $this->head;
        while ($current != null) {
            if (!$deduped->contains($current->data)) {
                $deduped->addLast($current->data);
            }
            $current = $current->next;
        }
        return $deduped;
    }

    /**
     * Returns a new DoublyLinkedList with only the unique nodes
     *
     * @return DoublyLinkedList
     */
    public function unique(): DoublyLinkedList
    {
        $unique = new DoublyLinkedList();
        $current = $this->head;
        $array = [];
        while ($current != null) {
            if (!in_array($current->data, $array)) {
                $unique->add($current->data);
                $array[] = $current->data;
            }
            $current = $current->next;
        }
        return $unique;
    }

    /**
     * Returns a new DoublyLinkedList with the nodes in reverse order
     *
     * @return DoublyLinkedList
     */
    public function reverse(): DoublyLinkedList
    {
        $reverse = new DoublyLinkedList();
        $current = $this->head;
        while ($current != null) {
            $reverse->addFirst($current->data);
            $current = $current->next;
        }
        return $reverse;
    }

    /**
     * returns true if the linked list contains the value
     * returns false if the linked list does not contain the value
     *
     * @param $data
     * @return bool
     */
    public function contains($data): bool
    {
        $current = $this->head;
        while ($current != null) {
            if ($current->data == $data) {
                return true;
            }
            $current = $current->next;
        }
        return false;
    }

    /**
     * @param  callable  $callback
     * @return DoublyLinkedList
     */
    public function forEach(callable $callback): DoublyLinkedList
    {
        $list = new LinkedList();
        $current = $this->head;
        while ($current != null) {
            $list->add($callback($current->data));
            $current = $current->next;
        }
        return $list;
    }

    /**
     * Sorts the list in ascending order
     *
     * @return DoublyLinkedList
     */
    public function sortAsc(): DoublyLinkedList
    {
        $list = new DoublyLinkedList();
        $arr = $this->toArray();
        sort($arr);
        foreach($arr as $item) {
            $list->add($item);
        }
        return $list;
    }

    /**
     * Sorts the list in descending order
     *
     * @return DoublyLinkedList
     */
    public function sortDesc(): DoublyLinkedList
    {
        $list = new DoublyLinkedList();
        $arr = $this->toArray();
        rsort($arr);
        foreach($arr as $item) {
            $list->add($item);
        }
        return $list;
    }

    /**
     * Sorts the list using a custom callback function
     * returns the sorted list as a new DoublyLinkedList
     *
     * @param  callable  $callback
     * @return DoublyLinkedList
     */
    public function sort(callable $callback): DoublyLinkedList
    {
        $sorted = new LinkedList();
        $current = $this->head;
        $values = [];
        while ($current != null) {
            $values[] = $current->data;
            $current = $current->next;
        }
        usort($values, $callback);
        foreach ($values as $value) {
            $sorted->add($value);
        }
        return $sorted;
    }

    /**
     * Calculates the average of the data in the linked list
     * only if the data is numeric. If there is no numeric data
     * in the list, the method returns null
     *
     * @throws \Exception
     */
    public function average(): float|null
    {
        $current = $this->head;
        $sum = 0;
        $count = 0;
        while ($current != null) {
            if(is_numeric($current->data)) {
                $sum += $current->data;
                $count++;
                $current = $current->next;
            } else {
                $current = $current->next;
            }
        }
        if($count == 0) {
            return null;
        } else {
            return $sum / $count;
        }
    }

    /**
     * returns the median of the data in the linked list
     *
     * @return mixed
     */
    public function median(): mixed
    {
        $sorted = $this->sortAsc();
        $sorted = $sorted->toArray();
        $count = count($sorted);
        $middle = floor(($count - 1) / 2);
        return $sorted[$middle];
    }

    /**
     * returns the data that occurs the most in the list
     *
     * @return int|string|null
     */
    public function mode(): int|string|null
    {
        $current = $this->head;
        $array = [];
        while ($current != null) {
            $array[] = $current->data;
            $current = $current->next;
        }
        $values = array_count_values($array);
        arsort($values);
        return array_key_first($values);
    }

    /**
     * Joins two DoublyLinkedLists and returns the new list
     * with the second list added to the end of the first
     *
     * @param  DoublyLinkedList  $list
     * @return DoublyLinkedList
     */
    public function join(DoublyLinkedList $list): DoublyLinkedList
    {
        $joined = new DoublyLinkedList();
        $current = $this->head;
        while ($current != null) {
            $joined->add($current->data);
            $current = $current->next;
        }
        $current = $list->head;
        while ($current != null) {
            $joined->add($current->data);
            $current = $current->next;
        }
        return $joined;
    }
}

Node Class

Copy Code

<?php

namespace DataStructures;

class Node
{
    public mixed $data;
    public Node|null $next;
    public Node|null $prev;

    public Node|null $left;
    public Node|null $right;
    public Node|null $parent;

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

    /**
     * returns the data of the given node
     *
     * @return mixed
     */
    public function getData(): mixed
    {
        return $this->data;
    }

    /**
     * returns the left child of the given node
     *
     * @return Node|null
     */
    public function getLeft(): Node|null
    {
        return $this->left;
    }

    /**
     * returns the right child of the given node
     *
     * @return Node|null
     */
    public function getRight(): Node|null
    {
        return $this->right;
    }

    /**
     * returns the parent of the given node
     *
     * @return Node|null
     */
    public function getParent(): Node|null
    {
        return $this->parent;
    }

    /**
     * returns the next node
     *
     * @return Node|null
     */
    public function getNext(): ?Node
    {
        return $this->next;
    }

    /**
     * returns the previous node
     *
     * @return Node|null
     */
    public function getPrev(): ?Node
    {
        return $this->prev;
    }

    /**
     * returns true if the node is the end of a list
     *
     * @return bool
     */
    public function isEnd(): bool
    {
        return $this->next === null;
    }

    /**
     * returns true if the node is the start of a list
     *
     * @return bool
     */
    public function isStart(): bool
    {
        return $this->prev === null;
    }
}

Testing

I applied the same tests to this class as I did the LinkedList class, and to save on visual space here I won’t be pasting the results, but I will be demoing the implementation and testing in a later post.

But… why?

“But Garrett, why do this when you can just use arrays in PHP with the existing and available functions?” you ask…

Well, it really depends on your application. Sure, standard PHP arrays can get us where we need 90% of the time, especially when dealing with sequential data, but having the information in those lists abstracted into class structures comes with benefits that OOP offers over more functional programming approaches you might use with just arrays. Instead of an array of integers representing the student IDs on a roster, you can have a LinkedList of Student objects, and those objects can contain a linked list of Assignment objects, and those Assignment objects can have grade properties. Then, using the callback functions, you can perform operations on each assignment in each student in only a few lines of code as opposed to querying a database over and over again for each element in a standard array.

Is that a constructed hyper-specific answer to the “why” question? Yes. Yes it is. But it’s just one of an infinite number of possibilities with OOP techniques and using object representation of data.

Another aspect of the LinkedList and DoublyLinkedList vs. array question is that because LinkedLists (both singly and doubly) are classes, they are extendable. If this was a package, it might not be very useful as it, but it can provide a framework to build off of with your own classes. Maybe you build your own implementation of a student Roster that extends LinkedList and implements some unique methods that you develop. That makes your code reusable, readable, and easier to maintain than just using arrays and array methods would.

But at the end of the day, this series isn’t meant to convince you that you need to use data structures like LinkedLists instead of arrays, it’s just a side project and exploration of data structures I’m doing in my free time to reacquaint myself with the concepts in a language I have the most experience with. Maybe by the end of the series, I will abstract the classes a bit and give a larger example of the power of these data structures, but for now, it’s just a fun project that I want to share with everyone here.