What is a doubly linked list in PHP and how is it implemented?

A doubly linked list in PHP is a data structure where each node contains a reference to the next node as well as the previous node. This allows for efficient traversal in both directions. To implement a doubly linked list in PHP, you can create a Node class with properties for data, next, and prev, and a DoublyLinkedList class with methods for adding, removing, and traversing nodes. 

```php
class Node {
    public $data;
    public $next;
    public $prev;

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

class DoublyLinkedList {
    private $head;

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

    public function addNode($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;
            $newNode->prev = $current;
        }
    }

    public function removeNode($data) {
        $current = $this->head;
        while ($current !== null) {
            if ($current->data === $data) {
                if ($current->prev !== null) {
                    $current->prev->next = $current->next;
                } else {
                    $this->head = $current->next;
                }
                if ($current->next !== null) {
                    $current->next->prev = $current->prev;
                }
                return;
            }
            $current = $current->next;
        }
    }

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

// Example usage
$dll = new DoublyLinkedList();
$dll->addNode(1);
$dll->addNode(2);
$dll->addNode(3);
$dll->traverse(); // Output: 1 2 3
$dll->removeNode(2);
$dll->traverse(); // Output: 1 3

Keywords

doubly linked list PHP implementation linked list data structure

Related Questions