What is a singly linked list?

A singly linked list is a dynamic data structure consisting of nodes. Each node (except the last) contains data and a reference to the next node. The last node has a null reference.

Main characteristics:

• Nodes: Each node contains a value and a pointer to the next node.
• Head: Pointer to the first node of the list.
• Tail: Pointer to the last node.
• Sequence: Elements are arranged in a specific order.
• Sequential access: Access to elements is only possible sequentially, starting from the head.
• Dynamic size: The size of the list can change during program execution.

Advantages:

• Efficient insertion and deletion of elements at the beginning of the list.
• Memory savings compared to arrays when data size is unpredictable.

Disadvantages:

• Slow access to elements by index (requires traversal from the beginning).
• Requires additional memory to store pointers.

Simple implementation in PHP:

<?php

class Node {
    public $data;
    public $next;

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

class SinglyLinkedList {
    public $head;

    public function __construct() {
        $this->head = null; // List initially empty
    }

    // Add element to the beginning of the list
    public function prepend($data) {
        $newNode = new Node($data, $this->head);
        $this->head = $newNode;
    }

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

// Usage example
$list = new SinglyLinkedList();
$list->prepend(10);
$list->prepend(20);
$list->prepend(30);

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

Used in various algorithms and data structures, such as stacks and queues.