Linked List In PHP

Linked lists are a fundamental class of data structure in computer science and programming. Each node in the chain of nodes has a link to the node that comes after it in the list and information about it. Linked lists are commonly used in many applications, including memory management, data storage, and algorithm implementation.

How It Works?

As heap memory is not continuous, linked lists are stored there. Memory is allocated when a node is built, and it stores data dynamically. The head of the list, where the list is started, stores the first nodes link.

Linked lists are used to manage changing list sizes. There is no set size for a linked list; if one is required, simply build a node and connect it. Unused RAM is not allocated as a result.

Here is an illustration showing how to make a linked list in PHP:

class Node {
    public $data;
    public $next;

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

class LinkedList {
        public $head;
    public $tail;

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

    public function insertAtLast($value)
    {
        $node = new Node($value);
        if (!$this->head) {
            $this->head = $node;
            $this->tail = $node;
        } else {
            $this->tail->next = $node;
            $this->tail = $node;
        }
        return $this;
    }

    public function insertAtFirst($value)
    {
        $node = new Node($value);
        $node->next = $this->head;
        $this->head = $node;

        return $this;
    }

    public function insertAtPosition($position, $value)
    {
        $newNode = new Node($value);
        $currentNode = $this->head;
        $pos = 1;

        while ($pos < $position) {
            $currentNode = $currentNode->next;
            $pos++;
        }

        $newNode->next = $currentNode->next;
        $currentNode->next = $newNode;

        return $this;
    }

    public function findOrFail($value): bool
    {
        $currentNode = $this->head;

        while ($currentNode != null) {
            if ($currentNode->data == $value) {
                return true;
            }
            $currentNode = $currentNode->next;
        }

        return false;
    }

    public function deleteFromBeg()
    {
        $this->head = $this->head->next;
        return $this;
    }

    public function deleteAtLast()
    {
        $currentNode = $this->head;
        while ($currentNode->next->next) {
            $currentNode = $currentNode->next;
        }
        $currentNode->next = null;
        $this->tail = $currentNode;
        return $this;
    }

    public function deleteFromPosition($position)
    {
        $currentNode = $this->head;
        $pos = 1;
        while ($pos < $position) {
            $currentNode = $currentNode->next;
            $pos++;
        }

        $currentNode->next = $currentNode->next->next;
        return $this;
    }

    public function printMiddleValue()
    {
        $firstNode = $this->head;
        $middleNode = $this->head;

        while ($firstNode->next && $firstNode->next->next) {
            $firstNode = $firstNode->next->next;
            $middleNode = $middleNode->next;
        }

        return $middleNode->data;
    }

    public function reverse()
    {
        $current = $this->head;
        $prev = null;
        $next = null;

        while ($current) {
            $next = $current->next;
            $current->next = $prev;
            $prev = $current;
            $current = $next; // for iteration
        }

        $this->tail = $this->head;
        $this->head = $prev;
        return $this;
    }

    public function count()
    {
        $currentNode = $this->head;
        $count = 0;

        while ($currentNode != null) {
            $currentNode = $currentNode->next;
            $count++;
        }

        return $count;
    }

    public function getValue($position)
    {
        $currentNode = $this->head;
        $currentPosition = 0;

        while ($currentPosition < $position) {
            $currentNode = $currentNode->next;
            $currentPosition++;
        }

        return $currentNode->data;
    }

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

    public function mergeInBetween($list1, $a, $b, $list2) // Leetcode 1669 no. problem.
    {
        $firstListA = $list1;
        $counter = 0;
        while ($counter <= $b) {
            $firstListA = $firstListA->next;
            $counter++;
        }

        $secondListA = $list2;
        while ($secondListA->next) {
            $secondListA = $secondListA->next;
        }
        $secondListA->next = $firstListA;

        $firstListA = $list1;
        $counter = 0;
        while ($counter < $a - 1) {
            $firstListA = $firstListA->next;
            $counter++;
        }
        $firstListA->next = $list2;

        return $list1;
    }

    public function getIntersectionNode($headA, $headB)
    {
        $nodeStack = [];

        $firstRunner = $headA;
        while ($firstRunner) {
            $nodeStack[] = $firstRunner;
            $firstRunner = $firstRunner->next;
        }

        $secondRunner = $headB;
        while ($secondRunner) {
            if (in_array($secondRunner, $nodeStack, TRUE)) {
                return $secondRunner;
            }

            $secondRunner = $secondRunner->next;
        }

        return null;
    }
}


$list = (new LinkedList())
    ->insertAtLast(10)
    ->insertAtLast(20)
    ->insertAtLast(30)
    ->insertAtLast(40)
    ->insertAtLast(50)
    ->insertAtFirst(-10)
    ->getValue(0);

print_r($list);

Linked lists are a helpful data structure for programming, storing, and organizing data, in summary.They can be easily implemented in PHP using objects, and provide a flexible and salable solution for many applications.