How to Implement Linked List in PHP

1. Use the SplDoublyLinkedList Class to Implement Linked List in PHP
2. Use the push() Method to Insert Values in Linked List
3. Use the add() Method to Insert Values in Linked List
4. Use the pop() Method to Delete the Element in Linked List
5. Find the Top and Bottom Value From a Linked Lists

This article will introduce the implementation of a linked list in PHP.

Use the SplDoublyLinkedList Class to Implement Linked List in PHP

A linked list is a common data structure implemented in many programming languages. It is linear and contains nodes linked with each other.

Each node contains the data and the link to the adjacent node. Thus, a linked list forms a chain of nodes. There are different variations of linked lists.

1. Singly Linked List: It is unidirectional. It traverses only in the forward direction.
2. Doubly Linked List: It is bidirectional. It traverses both in the forward and backward directions.
3. Circular Linked List: It is unidirectional and circular.
4. Circular Doubly Linked List: It is bidirectional and circular.

We can perform a variety of operations in the linked list. The basic operations are:

• traversal
• insertion
• deletion
• update
• searching

PHP provides a class SplDoublyLinkedList for implementing a linked list. It is a doubly-linked list.

Use the push() Method to Insert Values in Linked List

The push() method accepts a parameter to be pushed and allows appending the values in the list. The element will be pushed to the end of the linked list.

For example, create an instance of the class SplDoublyLinkedList and assign it to a $list variable. Invoke the push() method and insert the elements.

Example Code:

$list = new SplDoublyLinkedList;

$list->push(10);
$list->push(20);
$list->push(30);
$list->push(40);
$list->push(40);

In the example below, we have appended the elements 10, 20, 30, 40 and 40 in an empty linked list. Note that the element 40 is appended twice.

We can use the following function to display the elements of the list.

function displayList($list){
  for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current()."<br>";
  }
}

The rewind() method rewinds the iterator from the start of the linked list. For example, the iterator will move to the first element of the list.

The valid() method checks whether the linked list contains more nodes, and the next() method moves to the next item of the linked list. Thus, we can use these methods as in the example above in the for loop to iterate through the elements of the linked list.

Inside the loop, the current() method denotes the current element. So, the current element will be printed.

We can call this function displayList() whenever we need to print the list elements. We will use this function multiple times in the article.

The following is the output when we call the displayList() function with $list as the argument.

Output:

10
20
30
40
40

Use the add() Method to Insert Values in Linked List

We can use the add() method to insert elements in a linked list by specifying the position. The method takes two parameters.

The first parameter is the index where the item is to be inserted, and the second parameter is the item to be inserted. For example, invoke the add() method with 4 and 50 as the parameters and call the displayList() method.

Example Code:

$list->add(4,50);
displayList($list);

The code above adds the element 50 in the fourth index of the linked list we created.

Output:

10
20
30
40
50
40

As a result, the element 50 is seen in the fourth index. The element 40, previously in the fourth index, gets shifted to the end of the linked list.

Use the pop() Method to Delete the Element in Linked List

We can use the pop() method to remove the last element from a linked list. The method takes no parameters.

As of the last output above, the list contains the following elements.

10
20
30
40
50
40

The pop() method will remove the last element (40) from the linked list.

Example Code:

$list->pop();
displayList($list);

Output:

10
20
30
40
50

Find the Top and Bottom Value From a Linked Lists

We can find the top value of the linked list using the top() method, and for the bottom value, we can use the bottom() method. The example below is also the continuation of the example above.

The list contains the following items.

10
20
30
40
50

We can invoke the top() and bottom() function with the $list object and print them using the echo function.

Example Code:

displayList($list);
echo "the top value: ".$list->top()."<br>";
echo "the bottom value: ".$list->bottom()."<br>";

As a result, the topmost item is shown as 50 and the bottommost item is shown as 10.

Output:

10
20
30
40
50
the top value: 50
the bottom value: 10