Part-2: Data Structures in PHP - List

Lists, also known as linked lists, are dynamic data structures used in PHP and other programming languages to store and manipulate collections of data efficiently. Lists are particularly useful when you need to manage data that can grow or shrink during runtime. In this article, we will delve into PHP lists, covering their definition, types, and practical examples of how to create and use them effectively.

Understanding Lists in PHP

A list is a linear data structure consisting of a sequence of elements, called nodes, where each node contains data and a reference (or link) to the next node in the sequence. Lists in PHP come in two primary types:

          1.) Singly Linked Lists

          2.)  Doubly Linked Lists

1.  Singly Linked Lists:

In a singly linked list, each node points to the next node in the list. It starts with a head node and ends with a null reference.

Let's start by creating a simple singly linked list in PHP. We'll implement a list of integers.

class ListNode {

    public $data;       // The data stored in the node

    public $next;       // Reference to the next node

    public function __construct($data) {

        $this->data = $data;
        $this->next = null;

    }

}

class LinkedList {

    public $head;       // Reference to the first node in the list

    public function __construct() {

        $this->head = null;

    }

    public function addNode($data) {

        $newNode = new ListNode($data);

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

            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }

    }

    public function displayList() {

        $current = $this->head;

        while ($current !== null) {
            echo $current->data . " -> ";
            $current = $current->next;
        }
        echo "null\n";
    }

}


// Create a new linked list
$myList = new LinkedList();

// Add elements to the list
$myList->addNode(1);
$myList->addNode(2);
$myList->addNode(3);

// Display the list
$myList->displayList();

In this example, we define two classes: `ListNode` to represent individual nodes and `LinkedList` to manage the list. The `addNode` method appends new nodes to the end of the list, and the `displayList` method prints the list's contents.

Output:

1 -> 2 -> 3 -> null

2.  Doubly Linked Lists:

A doubly linked list is similar to a singly linked list, but each node points to both the next and the previous nodes, making it possible to traverse the list in both directions.

Here's an example of a doubly linked list in PHP. In a doubly linked list.

class DoublyListNode {

    public $data;           // Data stored in the node
    public $next;           // Reference to the next node
    public $prev;           // Reference to the previous node

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

class DoublyLinkedList {

    public $head;           // Reference to the first node in the list

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

    public function addNode($data) {

        $newNode = new DoublyListNode($data);

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

            $current->next = $newNode;
            $newNode->prev = $current;

        }
    }

    public function displayForward() {

        $current = $this->head;

        while ($current !== null) {
            echo $current->data . " <-> ";
            $current = $current->next;
        }

        echo "null\n";

    }

    public function displayBackward() {

        $current = $this->head;

        while ($current->next !== null) {
            $current = $current->next;
        }

        while ($current !== null) {
            echo $current->data . " <-> ";
            $current = $current->prev;
        }

        echo "null\n";

    }
}



// Create a new doubly linked list
$myDoublyList = new DoublyLinkedList();

// Add elements to the list
$myDoublyList->addNode(1);

$myDoublyList->addNode(2);
$myDoublyList->addNode(3);

// Display the list forward
echo "Forward: ";
$myDoublyList->displayForward();

// Display the list backward
echo "Backward: ";
$myDoublyList->displayBackward();

In this example, we have `DoublyListNode` representing individual nodes and `DoublyLinkedList` to manage the doubly linked list. The `addNode` method appends new nodes to the end of the list while maintaining the bidirectional references. The `displayForward` method displays the list in forward order, and the `displayBackward` method displays it in reverse order.

Output:

Forward: 1 <-> 2 <-> 3 <-> null

Backward: 3 <-> 2 <-> 1 <-> null

This demonstrates the bidirectional traversal capabilities of a doubly linked list, allowing you to move both forwards and backward through the list efficiently.

Practical Examples of Lists in PHP

Lists are versatile data structures with numerous practical applications, including:

1. Task Management:  Managing a to-do list where tasks can be added or removed dynamically.

2. Undo/Redo Functionality: Implementing undo and redo functionality in applications by maintaining a list of previous states.

3. Dynamic Data Structures: Storing data that may change in size frequently, such as dynamic arrays or queues.

4. Symbol Tables: Creating symbol tables for compilers or interpreters to manage variables and their values.

Lists are essential data structures in PHP, offering dynamic and efficient ways to manage collections of data. By understanding the concept of lists and how to implement them, you can expand your programming toolkit and tackle a broader range of tasks effectively. Whether it's for managing tasks, maintaining historical data, or implementing custom data structures, lists are a valuable resource in your PHP development journey.