Data Structure: Singly Linked List in PHP

A singly linked list is a list of items, where each element has reference to the next element. Elements do not have info on the previous element. So we can only go to the next element while traversing a singly linked list.

NOTE

In this article, we are discussing in detail, the implementation of Singly Linked List in PHP.

Check the link below to check the details of Linked List and Singly Linked List-

Linked List Details

Singly Linked List Details

Implementation

Here is the detailed implementation of Singly Linked List in PHP, step-by-step –

Step #1: Node Class

The purpose of the Node class is to store information on a single node. It stores data and references to the next node.

Declare a class named “Node“. You can name this class anything based on what data are you saving in the list.

Create “constructor” and accept “data”. Set the “data” value to class property “data”.

In the constructor set a class property “next” and assign a value “null“. As initially it will be null when the node is first created and pushed at the end.

class Node {
    public ?Node $next = null;

    public function __construct(public string $data) {

    }
}

PHP

Step #2: Linked List Class

The lined list class is the place where we are implementing the actual linked list-

Create a class named “SinglyLinkedList“. You can name this class according to the purpose of the implementation.

Define a constructor.

In the constructor set – head=null, tail=null, length=0. This way we have initialized 3 properties of this class head, tail, and length.

class SinglyLinkedList {
    public ?Node $head = null;
    public ?Node $tail = null;
    public int $length = 0;

    public function __construct() {

    }
}

PHP

Step #3: Push (Node to the end)

Create the function “push” and accept “data” as a parameter.

Create a new “Node” object using “data“.

If there is no head in the current list, then make this current node as head. If there is existing data, then make this the next node of the current tail.

Finally, make this node as tail.

Increate the length by one, as a new node is added to the list.

class SinglyLinkedList {
    // ...
    
    // Push node to the end of the list
    public function push(string $data): bool {
        $node = new Node($data);

        // If the list is empty
        // then make this node as head and tail
        if ($this->head === null) {
            $this->head = $node;
        } else {
            // set the current tail's next value to new node
            $this->tail->next = $node;
        }

        // Set the tail to this new node
        $this->tail = $node;

        // Increase the length by 1
        $this->length++;

        return true;
    }
    
    // ...
}

PHP

Step #4: Pop (Last Node)

Create a function named “pop“.

If there is no element then return null.

If there are elements then start traversing from the head, and go to the second last element.

Make the second last element as the head.

Get the last element and save that in some variable.

Make the “next” pointer of that as null.

Return the last element that was saved in some variable.

class SinglyLinkedList {
    // ...
    
    // Pop the last item
    public function pop(): ?Node {
        // If there is no head
        // then the list does not exist
        if ($this->head === null) {
            return null;
        }

        $current = $this->head;
        $newTail = $current;

        // Traverse through the list
        // and get the second last item as newTail
        while ($current->next !== null) {
            $newTail = $current;
            $current = $current->next;
        }

        // Assign the newTail to the tail
        $this->tail = $newTail;

        // Delete the next pointer of the tail
        $this->tail->next = null;

        $this->length--;

        // Reset head and tail if it was the last item
        if ($this->length == 0) {
            $this->head = null;
            $this->tail = null;
        }

        // Return the popped item
        return $current;
    }
    
    // ...
}

PHP

Step #5: Traverse all Nodes

Create method “traverse”, which is responsible of going through all the linked list nodes.

Start from the HEAD and go to TAIL

Print node information one by one.

class SinglyLinkedList {
    // ...
    
    // Traverse the list
    public function traverse(): void {
        $current = $this->head;

        while ($current !== null) {
            echo $current->data . PHP_EOL;

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

PHP

Step #6: Shift Head

Create method “shift”.

Store the current head in a variable/constant.

Make the “next” node of the current head, as the head.

Decrease the “length” by one.

Return the old head(saved in some variable) at the end.

class SinglyLinkedList {
    // ...
    
    // Shift head
    // and make the second item as head
    // also return the first item
    public function shift(): ?Node {
        // If there is no head then return null
        if ($this->head === null) {
            return null;
        }

        $oldHead = $this->head;

        // Set the second item as head
        $this->head = $oldHead->next;

        // Reduce the length by one
        $this->length--;

        if ($this->length === 0) {
            $this->head = null;
            $this->tail = null;
        }

        // Return the head item
        return $oldHead;
    }
    
    // ...
}

PHP

Step #7: Unshift Head

Create method “unsihft” and accept a “value“

Create a new node from this “value“.

Set the “next” of this new node to the current head of the list.

Make this new node, the head of the list.

class SinglyLinkedList {
    // ...
    
    // Unshift head
    // Create new node and set that as head
    public function unshift($value): bool {
        // Create new Node from value
        $newHead = new Node($value);

        if ($this->head === null) {
            $this->tail = $newHead;
        } else {
            $newHead->next = $this->head;
        }

        // Set the new node as head
        $this->head = $newHead;

        // Increase length by one
        $this->length++;

        return true;
    }
    
    // ...
}

PHP

Step #8: Get Node by Index

We want to pass some index and want to get the node at that index-

Create a function named “get” and accept a parameter “index“.

If the index is out of range then return null.

If the index is in range then start from the head, and go to the node at the specified index.

Return the node at the end of the function.

class SinglyLinkedList {
    // ...
    
    // Get node by index(sequence numbers)
    // 0 based index (index starts from 0)
    public function get(int $index): ?Node {
        // Check if the index is valid
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        $selectedNode = $this->head;

        for ($i = 1; $i <= $index; $i++) {
            $selectedNode = $selectedNode->next;
        }

        return $selectedNode;
    }
    
    // ...
}

PHP

Step #9: Search by data

Here we want to search for specific data. Whichever node has the data, we want to get that index.

Create a function named “search” and accept the parameter “data“.

Start traversing the nodes one by one, starting from the HEAD.

When we find the node with that specific data, we return the index of the node.

class SinglyLinkedList {
    // ...
    
    // Search the list for specific data
    public function search(string $data): ?int {
        $current = $this->head;
        $index = 0;

        while ($current) {
            if ($current->data === $data) {
                return $index;
            }

            $current = $current->next;
            $index++;
        }

        return null;
    }
    
    // ...
}

PHP

Step #10: Set data at Node by Index

Here we want to set the data of an existing, at a specific index.

Create a function named “set”, and accept 2 parameters- “index” and “data”.

Either start from the head and go through the node one by one and get the node at the specified index. Or just use the existing “get” function, and get the index.

Set the data of the node that we got.

class SinglyLinkedList {
    // ...
    
    // Set data of a specific node at specific index
    // 0 based index(index starts from 0)
    public function set(int $index, string $data): bool {
        $nodeAtIndex = $this->get($index);

        if ($nodeAtIndex) {
            $nodeAtIndex->data = $data;
            return true;
        }

        return false;
    }
    
    // ...
}

PHP

Step #11: Insert Data at Specific Index

We want to create a new node with data, and add that to some specific index.

Create function “insert” and accept param “index” and “data“.

Create a new node from the “data“.

Get the node at the node before the “index” (at index – 1).

Set the newly created node as the next node of the (index – 1) node.

Set the node after that as the “next” of the new node.

class SinglyLinkedList {
    // ...
    
    // Insert new node at a specific index
    // 0 based index(index starts at 0)
    public function insert(int $index, string $data): bool {
        if ($index < 0 || $index > $this->length) {
            return false;
        }

        if ($index === $this->length) {
            $this->push($data);
            return true;
        }

        if ($index === 0) {
            $this->unshift($data);
            return true;
        }

        $newNode = new Node($data);
        $prevNode = $this->get($index - 1);
        $newNode->next = $prevNode->next;
        $prevNode->next = $newNode;

        // Increase length
        $this->length++;

        return true;
    }
    
    // ...
}

PHP

Step #12: Remove Item from Specific Index

Create the function “remove” and accept “index” parameter.

Go to the node which is at (index – 1).

Change the “next” pointer of the node at (index – 1), and set the pointer to the node at (index + 1).

class SinglyLinkedList {
    // ...
    
    // Remove item at index
    public function remove(int $index): ?Node {
        // Return false if index is out of range
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

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

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

        $prevNode = $this->get($index - 1);
        $removedNode = $prevNode->next;
        $prevNode->next = $prevNode->next->next;

        $this->length--;

        return $removedNode;
    }
    
    // ...
}

PHP

Step #13: Reverse a Singly Linked List

Create a function named “reverse“.

Traverse through the full list.

Change the “next” pointer of each node to the previous node.

class SinglyLinkedList {
    // ...
    
    // Reverse a linked list
    public function reverse(): self {
        $currentNode = $this->head;
        unset($this->tail);
        $prevNode = null;
        $nextNode = null;

        while ($currentNode !== null) {
            $nextNode = $currentNode->next;
            $currentNode->next = $prevNode;

            $prevNode = $currentNode;
            $currentNode = $nextNode;
        }

        $this->tail = $this->head;
        $this->head = $prevNode;
        
        return $this;
    }
    
    // ...
}

PHP

Implement Iterator

NOTE

The following implementation is not part Linked List implementation. This is just for iterating the list easily.

It is included here as the iterator implementation using the PHP Iterator interface makes it easy to iterate over the items of the list.

Create a function named “reverse“.

Traverse through the full list.

Change the “next” pointer of each node to the previous node.

use Iterator;

class SinglyLinkedList implements Iterator{

    // For Iterator implementation 
    // Not specifically related to the linked list
    private ?Node $currentNode;
    private int $currentKey = 0;

    // ... Other implementation code
    

    // Part of Iterator interface implementation
    // Get current node
    public function current(): string {
        return $this->currentNode->data;
    }

    // Part of Iterator interface implementation
    // Get current key
    public function key(): int {
        return $this->currentKey;
    }

    // Part of Iterator interface implementation
    // Move to the next item
    public function next(): void {
        $this->currentNode = $this->currentNode->next;
        $this->currentKey++;
    }

    // Part of Iterator interface implementation
    // Rewind the iterator
    public function rewind(): void {
        $this->currentKey = 0;
        $this->currentNode = $this->head;
    }

    // Part of Iterator interface implementation
    // Check is valid
    public function valid(): bool {
        return $this->currentNode !== null;
    }
    
}

PHP

Usage:

Here is how we can use the implementation of the iterator-

$bigboxList = new SinglyLinkedList();

$bigboxList->rewind();

while($bigboxList->valid()) {
    echo 'Key: ' . $bigboxList->key() . PHP_EOL;
    echo 'Value: ';
    print_r($bigboxList->current());
    echo PHP_EOL;

    $bigboxList->next();
}

PHP

Full Implementation Code

Here is the full implementation of Singly Linked List, with all the functionality.

<?php

declare(strict_types=1);

use Iterator;

class Node {
    public ?Node $next = null;

    public function __construct(public string $data) {

    }
}

class SinglyLinkedList implements Iterator{
    public ?Node $head = null;
    public ?Node $tail = null;
    public int $length = 0;

    // For Iterator implementation 
    // Not specifically related to the linked list
    private ?Node $currentNode;
    private int $currentKey = 0;


    public function __construct() {
    }

    // Push node to the end of the list
    public function push(string $data): bool {
        $node = new Node($data);

        // If the list is empty
        // then make this node as head and tail
        if ($this->head === null) {
            $this->head = $node;
        } else {
            // set the current tail's next value to new node
            $this->tail->next = $node;
        }

        // Set the tail to this new node
        $this->tail = $node;

        // Increase the length by 1
        $this->length++;

        return true;
    }

    // Pop the last item
    public function pop(): ?Node {
        // If there is no head
        // then the list does not exist
        if ($this->head === null) {
            return null;
        }

        $current = $this->head;
        $newTail = $current;

        // Traverse through the list
        // and get the second last item as newTail
        while ($current->next !== null) {
            $newTail = $current;
            $current = $current->next;
        }

        // Assign the newTail to the tail
        $this->tail = $newTail;

        // Delete the next pointer of the tail
        $this->tail->next = null;

        $this->length--;

        // Reset head and tail if it was the last item
        if ($this->length == 0) {
            $this->head = null;
            $this->tail = null;
        }

        // Return the popped item
        return $current;
    }

    // Traverse the list
    public function traverse(): void {
        $current = $this->head;

        while ($current !== null) {
            echo $current->data . PHP_EOL;

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

    // Shift head
    // and make the second item as head
    // also return the first item
    public function shift(): ?Node {
        // If there is no head then return null
        if ($this->head === null) {
            return null;
        }

        $oldHead = $this->head;

        // Set the second item as head
        $this->head = $oldHead->next;

        // Reduce the length by one
        $this->length--;

        if ($this->length === 0) {
            $this->head = null;
            $this->tail = null;
        }

        // Return the head item
        return $oldHead;
    }

    // Unshift head
    // Create new node and set that as head
    public function unshift($value): bool {
        // Create new Node from value
        $newHead = new Node($value);

        if ($this->head === null) {
            $this->tail = $newHead;
        } else {
            $newHead->next = $this->head;
        }

        // Set the new node as head
        $this->head = $newHead;

        // Increase length by one
        $this->length++;

        return true;
    }

    // Get node by index(sequence numbers)
    // 0 based index (index starts from 0)
    public function get(int $index): ?Node {
        // Check if the index is valid
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        $selectedNode = $this->head;

        for ($i = 1; $i <= $index; $i++) {
            $selectedNode = $selectedNode->next;
        }

        return $selectedNode;
    }

    // Set data of a specific node at specific index
    // 0 based index(index starts from 0)
    public function set(int $index, string $data): bool {
        $nodeAtIndex = $this->get($index);

        if ($nodeAtIndex) {
            $nodeAtIndex->data = $data;
            return true;
        }

        return false;
    }

    // Search the list for specific data
    public function search(string $data): ?int {
        $current = $this->head;
        $index = 0;

        while ($current) {
            if ($current->data === $data) {
                return $index;
            }

            $current = $current->next;
            $index++;
        }

        return null;
    }

    // Insert new node at a specific index
    // 0 based index(index starts at 0)
    public function insert(int $index, string $data): bool {
        if ($index < 0 || $index > $this->length) {
            return false;
        }

        if ($index === $this->length) {
            $this->push($data);
            return true;
        }

        if ($index === 0) {
            $this->unshift($data);
            return true;
        }

        $newNode = new Node($data);
        $prevNode = $this->get($index - 1);
        $newNode->next = $prevNode->next;
        $prevNode->next = $newNode;

        // Increase length
        $this->length++;

        return true;
    }

    // Remove item at index
    public function remove(int $index): ?Node {
        // Return false if index is out of range
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

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

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

        $prevNode = $this->get($index - 1);
        $removedNode = $prevNode->next;
        $prevNode->next = $prevNode->next->next;

        $this->length--;

        return $removedNode;
    }

    // Reverse a linked list
    public function reverse(): self {
        $currentNode = $this->head;
        unset($this->tail);
        $prevNode = null;
        $nextNode = null;

        while ($currentNode !== null) {
            $nextNode = $currentNode->next;
            $currentNode->next = $prevNode;

            $prevNode = $currentNode;
            $currentNode = $nextNode;
        }

        $this->tail = $this->head;
        $this->head = $prevNode;
        
        return $this;
    }

    // Part of Iterator interface implementation
    // Get current node
    public function current(): string {
        return $this->currentNode->data;
    }

    // Part of Iterator interface implementation
    // Get current key
    public function key(): int {
        return $this->currentKey;
    }

    // Part of Iterator interface implementation
    // Move to the next item
    public function next(): void {
        $this->currentNode = $this->currentNode->next;
        $this->currentKey++;
    }

    // Part of Iterator interface implementation
    // Rewind the iterator
    public function rewind(): void {
        $this->currentKey = 0;
        $this->currentNode = $this->head;
    }

    // Part of Iterator interface implementation
    // Check is valid
    public function valid(): bool {
        return $this->currentNode !== null;
    }
    
}

PHP

Demo

Here is the demo code for using the implemented functionality of Singly Linked List-

<?php

declare(strict_types=1);

require_once __DIR__ . '/../../../vendor/autoload.php';

use DataStructure\LinkedList\SinglyLinkedList\SinglyLinkedList;

$bigboxList = new SinglyLinkedList();

echo "\n\n----------- Singly Linked List Push example -----------\n\n";;

$bigboxList->push('Big');
$bigboxList->push('Box');
$bigboxList->push('Code');

print_r($bigboxList);


echo "\n\n----------- Singly Linked List Pop example -----------\n\n";;

echo "Popped Item: ";
print_r($bigboxList->pop());

echo "Popped Item: ";
print_r($bigboxList->pop());

echo "Popped Item: ";
print_r($bigboxList->pop());

echo "Popped Item: ";
print_r($bigboxList->pop());

// Push items again
$bigboxList->push("Big");
$bigboxList->push("Box");
$bigboxList->push("Code");

echo "\n\n----------- Singly Linked List Shift example -----------\n\n";;

echo "Shift head from list: ";
print_r($bigboxList->shift());

echo "Shift head from list: ";
print_r($bigboxList->shift());

echo "\n\n----------- Singly Linked List Unshift example -----------\n\n";;

echo "Unshift - 'Box' | Result: ";
print_r($bigboxList->unshift("Box"));

echo "Unshift - 'Big' | Result: ";
print_r($bigboxList->unshift("Big"));


echo "\n\n----------- Singly Linked List Get example -----------\n\n";;

echo "Get - at index: 0 | result:";
print_r($bigboxList->get(0));

echo "Get - at index: 2 | result:";
print_r($bigboxList->get(2));

echo "Get - at index: 99 | result:";
print_r($bigboxList->get(99));

echo "\n\n----------- Singly Linked List Set example -----------\n\n";;

echo "\nSet - 'New Val' at index: 0 | result: ";
print_r($bigboxList->set(0, "New Val"));

echo "\nSet - 'Second' at index: 2 | result: ";
print_r($bigboxList->set(2, "Second"));

echo "\nSet - 'Out bound' at index: 99 | result: ";
print_r($bigboxList->set(99, "Out bound"));


echo "\n\n----------- Singly Linked List Insert example -----------\n\n";;

echo "\nInsert - 'New Val 1' at index: 0 | result: ";
print_r($bigboxList->insert(0, "New Val 1"));

echo "\nInsert - 'New Val' at index: 2 | result: ";
print_r($bigboxList->insert(2, "New Val 2"));

echo "\nInsert - 'Out bound' at index: 99 | result: ";
print_r($bigboxList->insert(99, "Out bound"));


echo "\n\n----------- Singly Linked List Remove example -----------\n\n";;

// Reinitialize the list
$bigboxList = new SinglyLinkedList();
$bigboxList->push("Big");
$bigboxList->push("Box");
$bigboxList->push("Code");

echo "Remove - form index: 2 | result:";
print_r($bigboxList->remove(2));

echo "Remove - from index: 0 | result:";
print_r($bigboxList->remove(0));

echo "Remove - form index: 99 | result:";
print_r($bigboxList->remove(99));

echo "List value: ";
$bigboxList->traverse();

echo "\n\n----------- Singly Linked List Reverse example -----------\n\n";;

// Reinitialize the list
$bigboxList = new SinglyLinkedList();
$bigboxList->push("Big");
$bigboxList->push("Box");
$bigboxList->push("Code");
$bigboxList->push("Singly");
$bigboxList->push("Linked");
$bigboxList->push("List");

echo "List value: ";
$bigboxList->traverse();

$bigboxList->reverse();

echo "List value after reverse: ";
$bigboxList->traverse();

echo "\n\n----------- Iterator implementation for Singly Linked List -----------\n\n";;

$bigboxList->rewind();

while($bigboxList->valid()) {
    echo 'Key: ' . $bigboxList->key() . PHP_EOL;
    echo 'Value: ';
    print_r($bigboxList->current());
    echo PHP_EOL;

    $bigboxList->next();
}

PHP

Output:

Output of the demo code will look like below-

----------- Singly Linked List Push example -----------

DataStructure\LinkedList\SinglyLinkedList\SinglyLinkedList Object
(
    [head] => DataStructure\LinkedList\SinglyLinkedList\Node Object
        (
            [next] => DataStructure\LinkedList\SinglyLinkedList\Node Object
                (
                    [next] => DataStructure\LinkedList\SinglyLinkedList\Node Object
                        (
                            [next] =>
                            [data] => Code
                        )

                    [data] => Box
                )

            [data] => Big
        )

    [tail] => DataStructure\LinkedList\SinglyLinkedList\Node Object
        (
            [next] =>
            [data] => Code
        )

    [length] => 3
    [currentKey:DataStructure\LinkedList\SinglyLinkedList\SinglyLinkedList:private] => 0
)


----------- Singly Linked List Pop example -----------

Popped Item: DataStructure\LinkedList\SinglyLinkedList\Node Object
(
    [next] =>
    [data] => Code
)
Popped Item: DataStructure\LinkedList\SinglyLinkedList\Node Object
(
    [next] =>
    [data] => Box
)
Popped Item: DataStructure\LinkedList\SinglyLinkedList\Node Object
(
    [next] =>
    [data] => Big
)
Popped Item:

----------- Singly Linked List Shift example -----------

Shift head from list: DataStructure\LinkedList\SinglyLinkedList\Node Object
(
    [next] => DataStructure\LinkedList\SinglyLinkedList\Node Object
        (
            [next] => DataStructure\LinkedList\SinglyLinkedList\Node Object
                (
                    [next] =>
                    [data] => Code
                )

            [data] => Box
        )

    [data] => Big
)
Shift head from list: DataStructure\LinkedList\SinglyLinkedList\Node Object
(
    [next] => DataStructure\LinkedList\SinglyLinkedList\Node Object
        (
            [next] =>
            [data] => Code
        )

    [data] => Box
)


----------- Singly Linked List Unshift example -----------

Unshift - 'Box' | Result: 1Unshift - 'Big' | Result: 1

----------- Singly Linked List Get example -----------

Get - at index: 0 | result:DataStructure\LinkedList\SinglyLinkedList\Node Object
(
    [next] => DataStructure\LinkedList\SinglyLinkedList\Node Object
        (
            [next] => DataStructure\LinkedList\SinglyLinkedList\Node Object
                (
                    [next] =>
                    [data] => Code
                )

            [data] => Box
        )

    [data] => Big
)
Get - at index: 2 | result:DataStructure\LinkedList\SinglyLinkedList\Node Object
(
    [next] =>
    [data] => Code
)
Get - at index: 99 | result:

----------- Singly Linked List Set example -----------


Set - 'New Val' at index: 0 | result: 1
Set - 'Second' at index: 2 | result: 1
Set - 'Out bound' at index: 99 | result:

----------- Singly Linked List Insert example -----------


Insert - 'New Val 1' at index: 0 | result: 1
Insert - 'New Val' at index: 2 | result: 1
Insert - 'Out bound' at index: 99 | result:

----------- Singly Linked List Remove example -----------

Remove - form index: 2 | result:DataStructure\LinkedList\SinglyLinkedList\Node Object
(
    [next] =>
    [data] => Code
)
Remove - from index: 0 | result:DataStructure\LinkedList\SinglyLinkedList\Node Object
(
    [next] => DataStructure\LinkedList\SinglyLinkedList\Node Object
        (
            [next] =>
            [data] => Box
        )

    [data] => Big
)
Remove - form index: 99 | result:List value: Box


----------- Singly Linked List Reverse example -----------

List value: Big
Box
Code
Singly
Linked
List
List value after reverse: List
Linked
Singly
Code
Box
Big


----------- Iterator implementation for Singly Linked List -----------

Key: 0
Value: List
Key: 1
Value: Linked
Key: 2
Value: Singly
Key: 3
Value: Code
Key: 4
Value: Box
Key: 5
Value: Big

Plaintext

Testing

Let’s test the functionality using automated testing. Use the following code for testing. Following code uses Pest for testing.

<?php

use DataStructure\LinkedList\SinglyLinkedList\SinglyLinkedList;

describe("SinglyLinkedList", function () {
    describe("Push item to SinglyLinkedList", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
        });

        it("Should have correct head and tail", function () {
            // Initially head and tails should be null
            expect($this->singlyLinkedList->head)->toBeNull();
            expect($this->singlyLinkedList->tail)->toBeNull();

            $this->singlyLinkedList->push("Big");

            expect($this->singlyLinkedList->head->data)->toBe("Big");
            expect($this->singlyLinkedList->tail->data)->toBe("Big");

            $this->singlyLinkedList->push("Box");
            $this->singlyLinkedList->push("Code");

            expect($this->singlyLinkedList->head->data)->toBe("Big");
            expect($this->singlyLinkedList->tail->data)->toBe("Code");
        });

        it("Should have correct length", function () {
            expect($this->singlyLinkedList->length)->toBe(0);

            $this->singlyLinkedList->push("Big");

            expect($this->singlyLinkedList->length)->toBe(1);

            $this->singlyLinkedList->push("Box");

            expect($this->singlyLinkedList->length)->toBe(2);

            $this->singlyLinkedList->push("Code");

            expect($this->singlyLinkedList->length)->toBe(3);
        });
    });

    describe("Pop item from SinglyLinkedList", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
            $this->singlyLinkedList->push("Big");
            $this->singlyLinkedList->push("Box");
            $this->singlyLinkedList->push("Code");
        });

        it("Should pop item propertly", function () {
            $pop1 = $this->singlyLinkedList->pop();

            expect($pop1->data)->toBe("Code");

            $pop2 = $this->singlyLinkedList->pop();

            expect($pop2->data)->toBe("Box");

            $pop3 = $this->singlyLinkedList->pop();

            expect($pop3->data)->toBe("Big");

            $pop0 = $this->singlyLinkedList->pop();

            expect($pop0)->toBeNull();
        });

        it("Should have correct head and tail", function () {
            expect($this->singlyLinkedList->head->data)->toBe("Big");
            expect($this->singlyLinkedList->tail->data)->toBe("Code");

            $this->singlyLinkedList->pop();

            expect($this->singlyLinkedList->head->data)->toBe("Big");
            expect($this->singlyLinkedList->tail->data)->toBe("Box");

            $this->singlyLinkedList->pop();

            expect($this->singlyLinkedList->head->data)->toBe("Big");
            expect($this->singlyLinkedList->tail->data)->toBe("Big");

            $this->singlyLinkedList->pop();

            expect($this->singlyLinkedList->head)->toBeNull();
            expect($this->singlyLinkedList->tail)->toBeNull();
        });

        it("Should have correct length", function () {
            $pop1 = $this->singlyLinkedList->pop();

            expect($this->singlyLinkedList->length)->toBe(2);

            $pop2 = $this->singlyLinkedList->pop();

            expect($this->singlyLinkedList->length)->toBe(1);

            $pop3 = $this->singlyLinkedList->pop();

            expect($this->singlyLinkedList->length)->toBe(0);

            $pop0 = $this->singlyLinkedList->pop();

            expect($this->singlyLinkedList->length)->toBe(0);
        });
    });

    describe("Shift item from SinglyLinkedList", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
            $this->singlyLinkedList->push("Big");
            $this->singlyLinkedList->push("Box");
            $this->singlyLinkedList->push("Code");
        });

        it("Should shift head propertly", function () {
            $shift1 = $this->singlyLinkedList->shift();

            expect($shift1->data)->toBe("Big");

            $shift2 = $this->singlyLinkedList->shift();

            expect($shift2->data)->toBe("Box");

            $shift3 = $this->singlyLinkedList->pop();

            expect($shift3->data)->toBe("Code");

            $shift0 = $this->singlyLinkedList->pop();

            expect($shift0)->toBeNull();
        });

        it("Should have correct head and tail", function () {
            $this->singlyLinkedList->shift();

            expect($this->singlyLinkedList->head->data)->toBe("Box");
            expect($this->singlyLinkedList->tail->data)->toBe("Code");

            $this->singlyLinkedList->shift();

            expect($this->singlyLinkedList->head->data)->toBe("Code");
            expect($this->singlyLinkedList->tail->data)->toBe("Code");

            $this->singlyLinkedList->shift();

            expect($this->singlyLinkedList->head)->toBeNull();
            expect($this->singlyLinkedList->tail)->toBeNull();
        });

        it("Should have correct length", function () {
            $this->singlyLinkedList->shift();

            expect($this->singlyLinkedList->length)->toBe(2);

            $this->singlyLinkedList->shift();

            expect($this->singlyLinkedList->length)->toBe(1);

            $this->singlyLinkedList->shift();

            expect($this->singlyLinkedList->length)->toBe(0);

            // Try to pop one more time
            $this->singlyLinkedList->pop();

            expect($this->singlyLinkedList->length)->toBe(0);
        });
    });

    describe("Unhift item from SinglyLinkedList", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
        });

        it("Should unhift head propertly", function () {
            $unshift1 = $this->singlyLinkedList->unshift("Code");

            expect($unshift1)->not->toBeNull();

            $unshift2 = $this->singlyLinkedList->unshift("Box");

            expect($unshift2)->not->toBeNull();
        });

        it("Should have correct head and tail", function () {
            $this->singlyLinkedList->unshift("Code");

            expect($this->singlyLinkedList->head->data)->toBe("Code");
            expect($this->singlyLinkedList->tail->data)->toBe("Code");

            $this->singlyLinkedList->unshift("Box");

            expect($this->singlyLinkedList->head->data)->toBe("Box");
            expect($this->singlyLinkedList->tail->data)->toBe("Code");

            $this->singlyLinkedList->unshift("Big");

            expect($this->singlyLinkedList->head->data)->toBe("Big");
            expect($this->singlyLinkedList->tail->data)->toBe("Code");
        });

        it("Should have correct length", function () {
            $this->singlyLinkedList->unshift("Code");

            expect($this->singlyLinkedList->length)->toBe(1);

            $this->singlyLinkedList->unshift("Box");

            expect($this->singlyLinkedList->length)->toBe(2);

            $this->singlyLinkedList->unshift("Big");

            expect($this->singlyLinkedList->length)->toBe(3);
        });
    });

    describe("Get item from SinglyLinkedList by index", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
            $this->singlyLinkedList->push("Big");
            $this->singlyLinkedList->push("Box");
            $this->singlyLinkedList->push("Code");
        });

        it("Should return node at specific index", function () {
            $node0 = $this->singlyLinkedList->get(0);

            expect($node0->data)->toBe("Big");

            $node2 = $this->singlyLinkedList->get(2);

            expect($node2->data)->toBe("Code");
        });

        it("Should return null for invalid index", function () {
            $nodenve = $this->singlyLinkedList->get(-1);

            expect($nodenve)->toBeNull();

            $nodelarge = $this->singlyLinkedList->get(999999);

            expect($nodelarge)->toBeNull();
        });
    });

    describe("Search item in SinglyLinkedList", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
            $this->singlyLinkedList->push("Big");
            $this->singlyLinkedList->push("Box");
            $this->singlyLinkedList->push("Code");
        });

        it("Should return correct index of the item", function () {
            $search0 = $this->singlyLinkedList->search("Big");

            expect($search0)->toBe(0);

            $search2 = $this->singlyLinkedList->search("Code");

            expect($search2)->toBe(2);
        });

        it("Should return null for non existing item", function () {
            $searchResult = $this->singlyLinkedList->search("Non existing item");

            expect($searchResult)->toBeNull();
        });
    });

    describe("Set item to SinglyLinkedList by index", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
            $this->singlyLinkedList->push("Big");
            $this->singlyLinkedList->push("Box");
            $this->singlyLinkedList->push("Code");
        });

        it("Should set value at node properly", function () {
            $set0 = $this->singlyLinkedList->set(0, "New Val");

            expect($set0)->toBeTruthy();

            $get0 = $this->singlyLinkedList->get(0);

            expect($get0->data)->toBe("New Val");

            $set2 = $this->singlyLinkedList->set(2, "Second");

            expect($set2)->toBeTruthy();

            $get2 = $this->singlyLinkedList->get(2);

            expect($get2->data)->toBe("Second");

            $setN = $this->singlyLinkedList->set(99, "Out Bound");

            expect($setN)->toBeFalsy();
        });

        it("Should handle empty list without any exception", function () {
            $this->singlyLinkedList = new SinglyLinkedList();

            $set0 = $this->singlyLinkedList->set(0, "Out Bound");

            expect($set0)->toBeFalsy();
        });
    });

    describe("Insert item to SinglyLinkedList by index", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
        });

        it("Should insert data at index", function () {
            $insert0 = $this->singlyLinkedList->insert(0, "Big");

            expect($insert0)->toBeTruthy();

            $get0 = $this->singlyLinkedList->get(0);

            expect($get0->data)->toBe("Big");

            $insert1 = $this->singlyLinkedList->insert(1, "Code");

            expect($insert1)->toBeTruthy();

            $get1 = $this->singlyLinkedList->get(1);

            expect($get1->data)->toBe("Code");

            $insert1_1 = $this->singlyLinkedList->insert(1, "Box");

            expect($insert1_1)->toBeTruthy();

            $get1_1 = $this->singlyLinkedList->get(1);

            expect($get1_1->data)->toBe("Box");

            $get1_2 = $this->singlyLinkedList->get(2);

            expect($get1_2->data)->toBe("Code");

            $setN = $this->singlyLinkedList->insert(99, "Out Bound");

            expect($setN)->toBeFalsy();
        });

        it("Should have proper length after insert", function () {
            $this->singlyLinkedList->insert(0, "Big");

            expect($this->singlyLinkedList->length)->toBe(1);

            $this->singlyLinkedList->insert(1, "Code");

            expect($this->singlyLinkedList->length)->toBe(2);

            $this->singlyLinkedList->insert(1, "Box");

            expect($this->singlyLinkedList->length)->toBe(3);

            $this->singlyLinkedList->insert(99, "Out Bound");

            expect($this->singlyLinkedList->length)->toBe(3);
        });
    });

    describe("Remove item from SinglyLinkedList by index", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
            $this->singlyLinkedList->push("Big");
            $this->singlyLinkedList->push("Box");
            $this->singlyLinkedList->push("Code");
        });

        it("Should remove data at index", function () {
            $remove2 = $this->singlyLinkedList->remove(2);

            expect($remove2->data)->toBe("Code");

            $get2 = $this->singlyLinkedList->get(2);

            expect($get2)->toBeNull();

            $remove0 = $this->singlyLinkedList->remove(0);

            expect($remove0->data)->toBe("Big");

            $get0 = $this->singlyLinkedList->get(0);

            expect($get0->data)->toBe("Box");

            $removeN = $this->singlyLinkedList->remove(99);

            expect($removeN)->toBeFalsy();
        });

        it("Should have proper length after remove", function () {
            $this->singlyLinkedList->remove(1);

            expect($this->singlyLinkedList->length)->toBe(2);

            $this->singlyLinkedList->remove(99);

            expect($this->singlyLinkedList->length)->toBe(2);
        });
    });

    describe("Reverse SinglyLinkedList", function () {
        beforeEach(function () {
            $this->singlyLinkedList = new SinglyLinkedList();
            $this->singlyLinkedList->push("Big");
            $this->singlyLinkedList->push("Box");
            $this->singlyLinkedList->push("Code");
            $this->singlyLinkedList->push("Singly");
            $this->singlyLinkedList->push("Linked");
            $this->singlyLinkedList->push("List");
        });

        it("Should set head properly", function () {
            $this->singlyLinkedList->reverse();

            expect($this->singlyLinkedList->head->data)->toBe("List");
        });

        it("Should set tail properly", function () {
            $this->singlyLinkedList->reverse();

            expect($this->singlyLinkedList->tail->data)->toBe("Big");
        });

        it("Should set all elements properly", function () {
            $this->singlyLinkedList->reverse();

            $get1 = $this->singlyLinkedList->get(1);

            expect($get1->data)->toBe("Linked");

            $get2 = $this->singlyLinkedList->get(2);

            expect($get2->data)->toBe("Singly");

            $get4 = $this->singlyLinkedList->get(4);

            expect($get4->data)->toBe("Box");
        });

        it("Should not change the length", function () {
            $this->singlyLinkedList->reverse();

            expect($this->singlyLinkedList->length)->toBe(6);
        });
    });
});

PHP