Implementing a linked list in PHP with full code example

by Nathan Sebhastian

Posted on Dec 08, 2022

Reading time: 15 minutes

In this article, you will learn how to implement a singly linked list in PHP:

Let’s start by learning the basic concepts and terminology used in linked lists.

Linked list terminology and illustration

Before we dive into the implementation, it is important to understand some of the key terms and concepts used in linked lists:

Node - A node is the basic building block of a linked list. It is an object that stores a data element and a reference to the next node in the list. In a singly linked list, each node only has a single reference, pointing to the next node in the sequence.

Head - The head of a linked list is the first node in the sequence. It is the node that is accessed first when traversing the list.

Tail - The tail of a linked list is the last node in the sequence. It is the node that the last node in the list points to.

Link - A link is a reference that a node has to the next node in the sequence. In a singly linked list, each node has a single link pointing to the next node in the list.

Length - The length of a linked list is the number of nodes in the list.

Here’s an illustration of a linked list data structure:

A simple linked list example
A simple linked list example

Now that you know the basic concepts and terminology, let’s move on to the implementation of a singly linked list in PHP.

Implementing a singly linked list in PHP

First, you need to define a Node class that represents a single node in the linked list.

This class will have two properties: $data which will store the data element of the node, and $next which will store a reference to the next node in the sequence.

class Node {
    // data stored in this node
    public $data;

    // reference to the next node
    public $next;

    // initialize the node with the given data
    function __construct($data) {
        $this->data = $data;
        $this->next = null;
    }
}

Next, define a SinglyLinkedList class that represents the linked list itself.

This class will have a $head property that stores a reference to the first node in the list, and a $tail property that stores a reference to the last node in the list.

class SinglyLinkedList {
    // head of the linked list
    public $head;

    // tail of the linked list
    public $tail;

    // initialize the linked list
    function __construct() {
        $this->head = null;
        $this->tail = null;
    }
}

Now that we have defined the basic structure of our linked list, let’s move on to implementing some common operations on a linked list.

Inserting a node at the beginning of the list

The first operation that we will implement is inserting a node at the beginning of the list. This operation is commonly known as “pushing” a node onto the list.

To insert a node at the beginning of the list, we need to do the following:

  1. Create a new Node object with the given data element.
  2. Set the next property of the new node to the current head of the list.
  3. Set the head of the list to the new node.

Here is the implementation of this operation in the SinglyLinkedList class:

function push($data) {
    // create a new node with the given data
    $node = new Node($data);

    // if the list is empty, set the head and tail to the new node
    if ($this->head === null) {
      $this->head = $node;
      $this->tail = $node;
    } else {
      // set the next property of the new node to the current head
      $node->next = $this->head;

      // set the head of the list to the new node
      $this->head = $node;
    }
}

Inserting a node at the end of the list

The next operation that we will implement is inserting a node at the end of the list. This operation is commonly known as “appending” a node to the list.

To insert a node at the end of the list, you need to do the following:

  1. Create a new Node object with the given data element.
  2. Set the next property of the current tail of the list to the new node.
  3. Set the tail of the list to the new node.

Below is the implementation of this operation in the SinglyLinkedList class:

function append($data) {
    // create a new node with the given data
    $node = new Node($data);

    // if the list is empty, set the head and tail to the new node
    if ($this->head === null) {
      $this->head = $node;
      $this->tail = $node;
    } else {
      // set the next property of the current tail to the new node
      $this->tail->next = $node;

      // set the tail of the list to the new node
      $this->tail = $node;
    }
}

Removing a node from the beginning of the list

The next operation that we will implement is removing a node from the beginning of the list.

This operation is commonly known as “popping” a node from the list.

To remove a node from the beginning of the list, we need to do the following:

  1. Check if the list is empty. If it is, return null.
  2. Set the head of the list to the node next to head.
  3. Return the removed node.

The code below shows the implementation of this operation in the SinglyLinkedList class:

function pop() {
    // check if the list is empty
    if ($this->head === null) {
      return null;
    }

    // set the head of the list to the node that the current head
    $node = $this->head;
    $this->head = $node->next;
    // return the removed node
    return $node;
}

Removing a node from the end of the list

The next operation that we will implement is removing a node from the end of the list. This operation is commonly known as “unshifting” a node from the list.

To remove a node from the end of the list, we need to do the following:

  1. Check if the list is empty. If it is, return null.
  2. If the list has only one node, set the head and tail of the list to null.
  3. Traverse the list to find the node before the last node.
  4. Set the next property of the node before the last node to null.
  5. Set the tail of the list to the node before the last node.
  6. Return the removed node.

Here is the implementation of this operation in the SinglyLinkedList class:

function unshift() {
    // check if the list is empty
    if ($this->head === null) {
      return null;
    }

    // If the list has only one node, set head and tail to null
    if ($this->head === $this->tail) {
      $node = $this->head;
      $this->head = null;
      $this->tail = null;
      return $node;
    }

    // traverse the list to find the node before the last node
    $current = $this->head;
    while ($current->next !== $this->tail) {
      $current = $current->next;
    }

    // set the next property of the node before the last node to null
    $node = $current->next;
    $current->next = null;

    // set the tail of the list to the node before the last node
    $this->tail = $current;

    // return the removed node
    return $node;
}

Finding the length of the list

In addition to the basic operations, it is often useful to be able to determine the length of the linked list. To find the length of the list, we need to do the following:

  1. Initialize a length variable to 0.
  2. Traverse the list and increment the length variable by 1 for each node.
  3. Return the length variable.

Here is the implementation of this operation in the SinglyLinkedList class:

function length() {
    // initialize a length variable to 0
    $length = 0;

    // traverse the list, then and increment the length variable
    $current = $this->head;
    while ($current !== null) {
      $length++;
      $current = $current->next;
    }

    // return the length of the list
    return $length;
}

Traversing the list

Another common operation on a linked list is traversing the list. To traverse the list, we need to do the following:

  1. Initialize a $current variable to the head of the list
  2. Loop through the list until we reach the end of the list. At each iteration of the loop, do the following:
    1. Print the data property of the current node.
    2. Set the current variable to the next node.

Here is the implementation of traverse() in the SinglyLinkedList class:

function traverse() {
    // set current to the head
    $current = $this->head;

    // loop through the list
    while ($current) {
      // print the data element of the current node
      echo $current->data;

      // set the current variable to the next node
      // if not null, print an arrow
      if ($current = $current->next) {
        echo " -> ";
      }
    }
    echo "\n";
}

Searching the list

Another common operation on a linked list is searching the list for a particular data element. To search the list, we need to do the following:

  1. Initialize a $current variable to the head of the list.
  2. Loop through the list until we reach the end of the list. At each iteration of the loop, do the following:
    1. If the data property of the current node matches the search query, return that node.
    2. Set the $current variable to the next node.
  3. If the search query is not found, return null.

Here is the implementation of search() in the SinglyLinkedList class:

function search($data) {
    // initialize a current variable to the head
    $current = $this->head;

    // loop through the list until we reach the end
    while ($current) {
      // return the node that matches the search data
      if ($current->data === $data) {
        return $current;
      }

      // set current to the next node
      $current = $current->next;
    }

    // when data not found, return null
    return null;
}

Removing a node from the middle of the list

The final operation that we will implement is removing a node from the middle of the list. This operation is commonly known as “splicing” a node from the list.

To remove a node from the middle of the list, we need to do the following:

  1. Search the list for the node with the given data value. If the node is not found, return null.
  2. If the node to be removed is the head of the list, set the head of the list to the next node.
  3. If the node to be removed is the tail of the list, set the tail of the list to the previous node.
  4. if the node to be removed is neither the head nor the tail, set the next property of the previous node to the next of the current node.
  5. Return the removed node.

Here is the implementation of this splice() in the SinglyLinkedList class:

function splice($data) {
    // search the list with the given data
    $current = $this->head;
    $previous = null;
    while ($current !== null) {
      if ($current->data === $data) {
        break;
      }

      $previous = $current;
      $current = $current->next;
    }

    // if the node is not found, return null
    if ($current === null) {
      return null;
    }

    // if the node to be removed is the head, set head to the next node
    if ($previous === null) {
      $this->head = $current->next;
    } else {
      // if the node to be removed is the tail of the list, set tail before the current tail
      if ($current->next === null) {
        $this->tail = $previous;
      }

      // if the node to be removed is neither the head nor the tail
      $previous->next = $current->next;
    }

    // return the removed node
    return $current;
}

With that, you have successfully implemented a singly linked list in PHP!

The complete SinglyLinkedList class code

Here is the complete SinglyLinkedList class with all of the implemented operations:

class SinglyLinkedList {
    // head of the linked list
    public $head;

    // tail of the linked list
    public $tail;

    // initialize the linked list
    function __construct() {
        $this->head = null;
        $this->tail = null;
    }

    // inserts a node at the beginning of the list
    function push($data) {
        // create a new node with the given data
        $node = new Node($data);

        // if the list is empty, set the head and tail to the new node
        if ($this->head === null) {
            $this->head = $node;
            $this->tail = $node;
        } else {
            // set the next property of the new node to the current head
            $node->next = $this->head;

            // set the head of the list to the new node
            $this->head = $node;
        }
    }

    // inserts a node at the end of the list
    function append($data) {
        // create a new node with the given data
        $node = new Node($data);

        // if the list is empty, set the head and tail to the new node
        if ($this->head === null) {
            $this->head = $node;
            $this->tail = $node;
        } else {
            // set the next property of the current tail to the new node
            $this->tail->next = $node;

            // set the tail of the list to the new node
            $this->tail = $node;
        }
    }

    // removes a node from the beginning of the list
    function pop() {
        // check if the list is empty
        if ($this->head === null) {
            return null;
        }

        // set the head of the list to the node that the current head
        $node = $this->head;
        $this->head = $node->next;
        // return the removed node
        return $node;
    }

    // removes a node from the end of the list
    function unshift() {
        // check if the list is empty
        if ($this->head === null) {
            return null;
        }

        // If the list has only one node, set the head and tail of the list to null
        if ($this->head === $this->tail) {
            $node = $this->head;
            $this->head = null;
            $this->tail = null;
            return $node;
        }

        // traverse the list to find the node before the last node
        $current = $this->head;
        while ($current->next !== $this->tail) {
            $current = $current->next;
        }

        // set the next property of the node before the last node to null
        $node = $current->next;
        $current->next = null;

        // set the tail of the list to the node before the last node
        $this->tail = $current;

        // return the removed node
        return $node;
    }

    // finds the length of the list
    function length() {
        // initialize a length variable to 0
        $length = 0;

        // traverse the list, incrementing the length variable by 1 for each node
        $current = $this->head;
        while ($current !== null) {
            $length++;
            $current = $current->next;
        }

        // return the length of the list
        return $length;
    }

    // prints the data element of each node
    function traverse() {
        // set current to the head
        $current = $this->head;

        // loop through the list
        while ($current) {
            // print the data element of the current node
            echo $current->data;

            // set the current variable to the next node
            // if not null, print an arrow
            if ($current = $current->next) {
                echo " -> ";
            }
        }
        echo "\n";
    }

    // searches the list for the given data. Returns the node if found
    function search($data) {
        // initialize a current variable to the head
        $current = $this->head;

        // loop through the list until we reach the end
        while ($current) {
            // when the data of the current node matches the search, return the node
            if ($current->data === $data) {
                return $current;
            }

            // set current to the next node
            $current = $current->next;
        }

        // when data not found, return null
        return null;
    }

    // search, return, and remove a node
    function splice($data) {
        // search the list with the given data
        $current = $this->head;
        $previous = null;
        while ($current !== null) {
            if ($current->data === $data) {
                break;
            }

            $previous = $current;
            $current = $current->next;
        }

        // if the node is not found, return null
        if ($current === null) {
            return null;
        }

        // if the node to be removed is the head, set head to the next node
        if ($previous === null) {
            $this->head = $current->next;
        } else {
            // if the node to be removed is the tail of the list, set tail before the current tail
            if ($current->next === null) {
                $this->tail = $previous;
            }

            // if the node to be removed is neither the head nor the tail
            $previous->next = $current->next;
        }

        // return the removed node
        return $current;
    }
}

Let’s write some code to test the implementation as shown below:

$list = new SinglyLinkedList();

$list->push("A");

$list->push("B");
$list->traverse(); // B -> A

$list->append("C");
$list->traverse(); // B -> A -> C

$list->unshift();
$list->traverse(); // B -> A

$list->push("D");
$list->traverse(); // D -> B -> A

$list->splice("B");
$list->traverse(); // D -> A

echo $list->length(); // 2

Conclusion

A linked list is a data structure that consists of a sequence of nodes, where each node contains a data element and a reference to the next node in the sequence.

Linked lists are useful for storing collections of data that need to be dynamically resized and accessed in a non-contiguous manner.

We have implemented several common operations on a linked list, including:

  • Inserting a node at the beginning or end of the list
  • Removing a node from the beginning or end of the list
  • Finding the length of the list
  • Traversing the list
  • Searching the list
  • Removing a node from the middle of the list

With these operations implemented, you can use the SinglyLinkedList class to efficiently store, manipulate, and access data in a linked list.

Granted, most people prefer to use arrays rather than implementing their own linked list structure these days.

But implementing a linked list is still one of the most common code exercises in a tech bootcamp or job interview.

You’ve done a great job learning how to implement a linked list in PHP. Don’t forget to give yourself a treat! 😉

Also, feel free to use the code in this tutorial for your project.

Take your skills to the next level ⚡️

I'm sending out an occasional email with the latest tutorials on programming, web development, and statistics. Drop your email in the box below and I'll send new stuff straight into your inbox!

No spam. Unsubscribe anytime.

About

Hello! This website is dedicated to help you learn tech and data science skills with its step-by-step, beginner-friendly tutorials.
Learn statistics, JavaScript and other programming languages using clear examples written for people.

Learn more about this website

Connect with me on Twitter

Or LinkedIn

Tags

Click to see all tutorials tagged with:

Android CSS DevTools Git HTML Java JavaScript Kotlin MySQL NodeJS npm PHP Python React Sequelize Statistics