Implementing a Linked List Data Structure in PHP

0 0

Introduction

In computer science, a linked list is a linear data structure where each element (called a “node”) contains a value and a reference to the next node in the list. Linked lists are useful for implementing many algorithms and data structures, such as stacks, queues, and hash tables. In this blog, we will discuss how to implement a linked list using PHP.

Creating a Linked List

To create a linked list, we first need to define a node class that will represent the individual elements in the list. The node class should have two properties: a data property to store the value of the node, and a next property to store a reference to the next node in the list. Here is an example of a node class in PHP:

class Node {
    public $data;
    public $next;

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

The constructor function takes a value as a parameter and initializes the data property with that value. The next property is initialized to null, indicating that the node does not have a reference to any other node yet.

Next, we can create a LinkedList class that will manage the list of nodes. The LinkedList class should have a head property to store the first node in the list. If the list is empty, the head property should be null. Here is an example of a LinkedList class in PHP:

class LinkedList {
    public $head;

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

Inserting Nodes into the List

To insert a new node into the list, we first need to create a new node object with the given value. Then, we set the next property of the new node to the current head of the list, and set the head property of the list to the new node. This effectively inserts the new node at the beginning of the list. Here is an example of an insert method in the LinkedList class:

public function insert($data) {
    $newNode = new Node($data);
    $newNode->next = $this->head;
    $this->head = $newNode;
}

Traversing the List

To traverse the list, we can start at the head node and follow the next references until we reach the end of the list (when the next reference is null). We can use a while loop to accomplish this. Here is an example of a traverse method in the LinkedList class:

public function traverse() {
    $currentNode = $this->head;
    while ($currentNode !== null) {
        echo $currentNode->data . " ";
        $currentNode = $currentNode->next;
    }
}

Deleting Nodes from the List

To delete a node from the list, we need to find the node that precedes the node we want to delete. We can use a while loop to traverse the list until we find the node that precedes the target node. Then, we set the next property of the preceding node to the next node after the target node. Here is an example of a delete method in the LinkedList class:

public function delete($data) {
    if ($this->head === null) {
        return;
    }
    if ($this->head->data === $data) {
        $this->head = $this->head->next;
        return;
    }
    $currentNode = $this->head;
    while ($currentNode->next !== null) {
        if ($currentNode->next->data === $data) {
            $currentNode->next = $currentNode->next->next;
            return;
}
$currentNode = $currentNode->next;
}
}

Testing the Linked List

Now that we have implemented the basic functionality of the linked list, we can create an instance of the LinkedList class and test it out. Here is an example of how we might create a linked list, insert some nodes, traverse the list, and delete a node:
<?php

$list = new LinkedList();
$list->insert(1);
$list->insert(2);
$list->insert(3);
$list->traverse(); // output: 3 2 1
$list->delete(2);
$list->traverse(); // output: 3 1

Conclusion

In this blog, we have discussed how to implement a linked list using PHP. We have covered the creation of a node class and a LinkedList class, insertion of nodes into the list, traversal of the list, and deletion of nodes from the list. While linked lists may not be as commonly used as some other data structures, they are still an important concept to understand in computer science and can be useful in certain situations.

About Post Author

Vicky Chhetri

developer@vickychhetri.com

https://vickychhetri.com/

Happy

1 100 %

Sad

0 0 %

Excited

0 0 %

Sleepy

0 0 %

Angry

0 0 %

Surprise

0 0 %

About Author

Vicky Chhetri

See author's posts