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:

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:

- Create a new
`Node`

object with the given data element. - Set the
`next`

property of the new node to the current head of the list. - 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:

- Create a new
`Node`

object with the given data element. - Set the
`next`

property of the current`tail`

of the list to the new node. - 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:

- Check if the list is empty. If it is, return
`null`

. - Set the
`head`

of the list to the node next to head. - 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:

- Check if the list is empty. If it is, return
`null`

. - If the list has only one node, set the
`head`

and`tail`

of the list to`null`

. - Traverse the list to find the node before the last node.
- Set the
`next`

property of the node before the last node to`null`

. - Set the
`tail`

of the list to the node before the last node. - 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:

- Initialize a
`length`

variable to 0. - Traverse the list and increment the
`length`

variable by 1 for each node. - 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:

- Initialize a
`$current`

variable to the head of the list - Loop through the list until we reach the end of the list. At each iteration of the loop, do the following:
- Print the
`data`

property of the current node. - Set the current variable to the next node.

- Print the

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:

- Initialize a
`$current`

variable to the`head`

of the list. - Loop through the list until we reach the end of the list. At each iteration of the loop, do the following:
- If the
`data`

property of the current node matches the search query, return that node. - Set the
`$current`

variable to the next node.

- If the
- 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:

- Search the list for the node with the given
`data`

value. If the node is not found, return`null`

. - If the node to be removed is the
`head`

of the list, set the head of the list to the next node. - If the node to be removed is the
`tail`

of the list, set the tail of the list to the previous node. - 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. - 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.