What is a Linked List and how to implement it in PHP

A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference (or link) to the next node in the sequence. Unlike an array, which stores elements contiguously in memory, a linked list stores elements in separate nodes, and the links connect these nodes.

Here's an example implementation of a linked list in PHP:

//...

class Node {
    public $data; // Value stored in the node
    public $next; // Reference to the next node

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

//...

class LinkedList {
    private $head; // Reference to the first node

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

    // Add a new node to the end of the list
    public function append($data) {
        $newNode = new Node($data);

        if ($this->head === null) {
            $this->head = $newNode;
        } else {
            $current = $this->head;
            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
    }

    // Insert a new node at the beginning of the list
    public function prepend($data) {
        $newNode = new Node($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }

    // Remove the first node with the given value
    public function remove($data) {
        if ($this->head === null) {
            return;
        }

        if ($this->head->data === $data) {
            $this->head = $this->head->next;
            return;
        }

        $current = $this->head;
        while ($current->next !== null) {
            if ($current->next->data === $data) {
                $current->next = $current->next->next;
                return;
            }
            $current = $current->next;
        }
    }

    // Print the elements of the linked list
    public function display() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
        echo "\n";
    }
}

//...

// Usage example
$list = new LinkedList();
$list->append(10);
$list->append(20);
$list->prepend(5);
$list->append(30);
$list->display(); // Output: 5 10 20 30

$list->remove(10);
$list->display(); // Output: 5 20 30

//...

 In this example, the Node class represents a single node in the linked list. It has two properties: $data stores the value of the node, and $next is a reference to the next node in the list.

The LinkedList class represents the linked list itself. It has a private property $head, which points to the first node in the list. The class provides methods to append a new node at the end of the list append, prepend a new node at the beginning of the list prepend, remove a node with a specific value remove, and display the elements of the list display.