Singly Linked Lists – Data Structures in PHP

Reading Time: 5 minutes

All code in this series can be found on GitHub

Linked Lists are where we start our journey in PHP Data Structures. Simply put, a linked list is data that is sequentially organized in which the start of the list (head) contains a reference to the next item (node) in the list. A one-way link like this (start to next, next to end) is called a singly linked list. One way of thinking of it is a list of letters in a word. There is only one correct order to read the letters (nodes) in to form the word (list): start to finish.

Singly Linked List Principles

A list consists of nodes
Each node contains a reference or pointer to the next node in the list
Each node contains data
The first node is called the head
The last node in the list has a reference or pointer that is null

Available Methods:

To make the most of the singly linked list, we want to have some useful methods available. I will implement the following methods:

add() – adds a node to the end of the list
addAt() – adds a node at a given position
addFirst() – replaces the current head with a new node and shifts the list
delete($data) – removes all nodes with the given $data
deleteFirst() – removes the first node from the list
deleteLast() – removes the last node from the list
deleteAt() – removes a node at a given position
length() – returns the number of nodes in the list
get() – gets the node at the end of the list
getAt() – gets a node at a given position in the list
toArray() – converts the list to a standard PHP array

Additionally, since the get() method only returns the node, not necessarily the data in the node, we can define some methods on the Node class, including methods for the next Data Structure, the Doubly Linked List:

getData() – returns the data contained in the node
getNext() – returns the next node in the list
getPrev() – returns true if the node is the last in the list, false otherwise
isStart() – returns true if the given node is the first in a structure
isEnd() – returns true if the given node is the last in a structure

Implementation

LinkedList Class

Copy Code

<?php
namespace DataStructures;
use OutOfBoundsException;
/**
 * LinkedList
 */
class LinkedList
{
    public Node|null $head;
    /**
     * LinkedList default constructor
     */
    public function __construct()
    {
        $this->head = null;
    }
    /**
     * Add a new node with $data to the end of the list
     *
     * @param $data
     */
    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;
        }
    }
    /**
     * Add a new node with $data 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;
        }
    }
    /**
     * Add a node with $data at 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 = $node;
    }
    /**
     * Remove the last node 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;
                } else {
                    $previous->next = $current->next;
                }
                return;
            }
            $previous = $current;
            $current = $current->next;
        }
    }
    /**
     * remove the last node from the list
     */
    public function deleteLast(): void
    {
        $current = $this->head;
        $previous = null;
        while ($current->next != null) {
            $previous = $current;
            $current = $current->next;
        }
        $previous->next = null;
    }
    /**
     * Remove the first node from the list
     *
     * @return void
     */
    public function deleteFirst(): void
    {
        $this->head = $this->head->next;
    }
    /**
     * Remove a node at a given position
     *
     * @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;
                    } else {
                        $previous->next = $current->next;
                    }
                    return;
                }
                $previous = $current;
                $current = $current->next;
                $i++;
            }
        }
    }
    /**
     * returns the length of the list as an int
     *
     * @return int
     */
    public function length(): int
    {
        $current = $this->head;
        $length = 0;
        while ($current != null) {
            $length++;
            $current = $current->next;
        }
        return $length;
    }
    /**
     * Gets the head node of the list
     *
     * @return Node
     */
    public function get(): Node
    {
        return $this->head;
    }
    /**
     * returns the node at a given position
     *
     * @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;
                }
                $current = $current->next;
                $i++;
            }
            return null;
        }
    }
    /**
     * returns the linked list as a standard array
     *
     * @return array
     */
    public function toArray(): array
    {
        $array = [];
        $current = $this->head;
        while ($current != null) {
            $array[] = $current->data;
            $current = $current->next;
        }
        return $array;
    }
    /**
     * Clears all nodes from the list
     *
     * @return void
     */
    public function clear(): void
    {
        $this->head = null;
    }
}

Node Class

Copy Code

Node
<?php
namespace DataStructures;
class Node
{
    public mixed $data;
    public Node|null $next;
    public Node|null $prev;
    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 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 used the PHP Artisan Console to run some basic tests on the class above:

Copy Code

>>> $list = new LinkedList();
>>> $list->add(1);
>>> $list->add(2);
>>> $list->add(3);
>>> $list->add(4);
>>> $list->add(5);
>>> $list->toArray();
=> [
     1,
     2,
     3,
     4,
     5,
     6,
   ]
>>> $list->delete(6);
>>> $list->deleteAt(0);
>>> $list->toArray();
=> [
     2,
     3,
     4,
     5,
   ]
$list->addFirst(1);
$list->addFirst(0);
>>> $list->toArray();
=> [
     0,
     1,
     2,
     3,
     4,
     5,
   ]
$list->getAt(1)->getData();
1
$list->getAt(4)->getData();
4

Because PHP lets us chain methods, I can call a method getAt() on $list and then call data() on the Node instance within List.

I think this is a good start for a singly linked list! And with the ability to add nodes in places other than the end of the list, this class is behaving more like a Deque, but that will be covered in a later post.