Introduction to Singly Linked List and Basic Operations in PHP

Table of Contents

• About Node
• Singly 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

You can find Introduction do doubly linked list here.

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

Every non-empty linked list has a head(first node in list) and tail(last node in linked list).

A singly linked list may look like this:

About a Node

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

Here is an example of a node class in PHP:

class Node
{
  public $value;
  public $next;

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

This Node class has two fields:
1, data, which stores the element, and
2, next, which is a reference to the next node in the list.

The next field is initialized to null to indicate that the node is the last node in the list.

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

$nodeFirst = new Node(10);
$nodeNext = new Node(20);

// connect $nodeNext to nodeFirst
$nodeFirst->next = $nodeNext; // 10->20->null

// now you can receive value from second node
$nodeFirst->next->value; // 20

This code creates two nodes with data values 10 and 20, and links them together by setting the next field of nodeFirst to nodeNext. The resulting singly linked list would look like this:

$nodeFirst->$nodeNext->null

Singly Linked List

Constructor

Let's create a class that represents a 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 LinkedList
{
    public $head;
    public $tail;
    public $length;

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

The __construct takes an integer value as a parameter and creates a new node with that value. This new node is then set as both the head and tail of the list, and the length is set to 1.

NOTE: We don't have to initalize 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 singly 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.

public function printAll()
{
    $temp = $this->head;
    while ($temp != null) {
        echo $temp->value . '->';
        $temp = $temp->next;
    }
}

Basic operations:

1. Append

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

On the left is a linked list (only one node is shown in the image) and 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 last node in the linked list to the new one with $this->tail->next = $newNode and change the tail to the new one with $this->tail = $newNode.
4. we increment the count (length) of the linked list.

// add to the linked list Class
public function append($value)
{
    $newNode = new Node($value);
    if ($this->length == 0) {
        $this->head = $newNode;
        $this->tail = $newNode;
    } else {
        $this->tail->next = $newNode;
        $this->tail = $newNode;
    }
    $this->length++;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);

$l->printAll();
// 4->3->5->

2. Get

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

EXPLANATION:

1. first, we ensure that the index is within the bounds of the linked list; it should be greater than zero and less than the count of the singly linked list.
2. we assign the head of the linked list to a 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.

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;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);

$node = $l->getNode(2);
echo $node->value;
// 5

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 getNode() method to find the node at the specified index, or return null if the index is out of bounds.
2. we assign a new value to the node that was retrieved.

public function setNode($index, $value)
{
    $temp = $this->getNode($index);
    if ($temp) {
        $temp->value = $value;
    }
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->setNode(2,11); // set a value of 11 at index 2 if node exists

$l->printAll();
// 4->3->11->

4. Prepend

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

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

We need to do two things:

1, connect the new node to the head of the existing linked list.
2, change the head to the newly created node.

EXPLANATION:

1, we create a new node with a value.
2, if there are no nodes in the linked list, we assign the head and tail to the new node.
3, otherwise, we link the new node to the head with $newNode->next = $this->head and change the head to the new node with $this->head = $newNode.
4, finally, we increment the count (length) of the linked list.

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 = $newNode;
    }
    $this->length++;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->prepend(48);

$l->printAll();
// 48->4->3->5->

5. Insert

To insert a node in a 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 (3, 4, 7) and we want to insert a new node (X) between the nodes 4 and 7, the resulting linked list would look like (3, 4, X, 7).

EXPLANATION:

1. we check if the index is within the bounds of the linked 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 we want to insert the new node. We assign this node to a temporary variable.
5. we link the new node to the next node in the linked list.
6. then, we point the previous node (the one stored in the temporary variable) to the new node.
7. finally, we increment the count (length) of the linked list.

NOTE: Steps 5 and 6 have to be in that order. We cannot link temp(previous node) to the new node, because it unlinks the rest of the linked list.

public function insert($index, $value)
{
    if ($index < 0 || $index >= $this->length) {
        return null;
    }
    if ($index == 0) {
        $this->prepend($value);
        return;
    } elseif ($index == $this->length) {
        $this->append($value);
        return;
    }
    $newNode = new Node($value);
    $temp = $this->getNode($index - 1);
    $newNode->next = $temp->next;
    $temp->next = $newNode;
    $this->length++;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->insert(1,22);

$l->printAll();
// 4->22->3->5->

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's 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 to the head.
4. we then assign the head to the next node
5. and unlink $temp by changing temp->next to null.
6. we decrease the count (length) of the linked list.

public function popFirst()
{
    if ($this->length == 0) {
        return null;
    }
    if ($this->length == 1) {
        $this->head = null;
        $this->tail = null;
    } else {
        $temp = $this->head;
        $this->head = $temp->next;
        $temp->next = null;
    }
    $this->length--;
}

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->popFirst();

$l->printAll();
// 3->5->

7. Pop Last

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

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. otherwise, we need to traverse the list to the end and find a node before the last one. We can do this by creating two temporary variables called 'temp' and 'prev', where the 'temp' variable is one step ahead.
4. we loop through the entire linked list just to find the node before the last one.
5. then, we assign the tail to 'prev'.
6. we unlink the last node (the new tail's next node).
7. we decrease the count (length) of the linked list.

public function pop()
{
    if ($this->length == 0) {
        return null;
    }

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

$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->pop();

$l->printAll();
// 4->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 pop() method to remove the node at the end of the list.
3. otherwise, we need to find the node at the index immediately before the position where we want to remove the node. We assign this node to a temporary variable.
4. we update the next pointer of the previous node to point to the node after the one we want to remove. This effectively removes the node from the linked list.
5. we decrease the count (length) of the linked list.

public function remove($index)
{
    if ($index < 0 || $index >= $this->length) {
        return null;
    }
    if ($index == 0) {
        $this->popFirst();
        return;
    } elseif ($index == $this->length - 1) {
        $this->pop();
        return;
    }
    $temp = $this->getNode($index - 1);
    $temp->next = $temp->next->next;
    $this->length--;
}
$l = new LinkedList(4);
$l->append(3);
$l->append(5);
$l->remove(1);

$l->printAll();
// 4->5->

You can see the entire script here:
https://gist.github.com/matusstafura/6d7bf89bdde17e83fa39def977ffe7aa

Time Complexity

The time complexity (or "Big O") of basic operations on a singly linked list depends on the operation being performed and the position of the node being accessed.

Time complexity for some common operations:

• Accessing a node by index: O(n)
• Inserting a node at the beginning or end of the list: O(1)
• Inserting a node at a specific index: O(n)
• Removing a node from the beginning or end of the list: O(1)
• Removing a node from a specific index: O(n)

In general, singly linked lists have a time complexity of O(n) for operations that require traversing the list to find a specific node, since these operations require visiting each node in the list until the desired node is found. On the other hand, operations that do not require traversing the list, such as inserting or removing a node at the beginning or end of the list, have a time complexity of O(1).

It's important to note that these time complexities are worst-case scenarios and the actual time taken by the operation may be faster in some cases. For example, if we have a reference to the node we want to remove, we can remove it in O(1) time without traversing the list. Similarly, if we are inserting a node at a specific index and we already have a reference to the node at that index, the insertion operation will also take O(1) time.