PHP one directional linked list

To create a list, we need to declare two classes, List Node and Linked List classes.

Basic PHP one directional linked list

PHP Linked list and its methods

<?php

class ListNode
{
    public $data = NULL;
    public $next = NULL;
    
    function __construct(string $data = NULL)
    {
    	$this->data = $data;
    }
}

class LinkedList
{
    private $_firstNode = NULL;
    private $_totalNodes = 0;
    
    function insert(string $data = NULL)
    {
        $newNode = new ListNode($data);
        
    	if($this->_firstNode === NULL){
    	  $this->_firstNode = &$newNode;
    	  return;
    	} 
    	
    	$curentNode = $this->_firstNode;
    	
    	while($curentNode->next !== NULL){
    	    $curentNode = $curentNode->next;
    	}
    	
    	$curentNode->next = $newNode;
    	$this->_totalNodes++;
    	return true;
    	
    }
    
    function printData(){
        $pointer = $this->_firstNode;
        if(!$pointer) return;
        
        while($pointer != NULL){
            echo $pointer->data . " <br/>";
            $pointer = $pointer->next;
        }
    }

    ... // other methods described below
}

Test list

$l = new LinkedList();
$l->insert("Wiktor");
$l->insert("Wojtuś");
$l->insert("Kubuś");

$l->printData();

Adding linked list search functionality

Adding search functionality is quite simple. To find a item with a given value, we need to iterate through all nodes of the list. Searching complexity is equal to O(n). First, we will check if the list has any nodes added. We do it by checking property _totalNodes;

    function search($data = NULL){
        if($this->_totalNodes){
            $currentNode = $this->_firstNode;
            while($currentNode !== NULL){
                if($data == $currentNode->data){
                    return $currentNode;
                }
                $currentNode = $currentNode->next;
            }  
        }
        return FALSE;
    }

Test search

...
echo ($l->search("Wiktor"))->data;

PHP Linked List – Inserting before searched element

Inserting before searched node require from us to store information about two nodes: current and previous node. While we run the first while iteration, the previous node does not exist.

We will set its value to NULL before the loop. Inside the loop, we will update previousNode to currentNodeand currentNode to currentNode->next (NOTE! The order do matter!).

This is how we will store information about both previous and current nodes. We should also check for case when the insert comes before the first node when no previusNode is set to NULL. We don’t need to worry about the last node, as we can only insert before an element we are searching for.

    function insertBefore($data = NULL, $search = NULL){
        $newNode = new ListNode($data);
        if($this->_firstNode){
            $currentNode = $this->_firstNode;
            $prevNode = NULL;
            
            while($currentNode !== NULL){
                
                // insert before first node
                if($this->_firstNode->data == $search){
                    $newNode->next = $currentNode;
                    $this->_firstNode = $newNode;
                    return;
                }
                
                // insert between nodes
                if($currentNode->data == $search){
                    $prevNode->next = $newNode;
                    $newNode->next = $currentNode;
                    return;
                }
                
                $prevNode = $currentNode;
                $currentNode = $currentNode->next;
                
            }
        }
    }
}

...
$l->insertBefore("Justyna", "Wiktor");
$l->insertBefore("Kotek", "Justyna");

$l->printData();

PHP Linked List – Inserting after searched element

This functionality will not be much different from the previous method added. But note the change of the order then assigning $currentNode = $currentNode->next; and $nextNode = $currentNode->next; which make a jump to the next node object. Without further due, lets investigate what has changed:

    function insertAfter($data = NULL, $search = NULL){
        $newNode = new ListNode($data);
        if($this->_firstNode){
            
            $nextNode = NULL;
            $currentNode = $this->_firstNode;
            
            while($currentNode !== NULL){
                            // insert as last
                if($currentNode->next == NULL){
                    $currentNode->next = $newNode;
                    
                    $this->_totalNodes++;
                    return true;
                }
            
                // insert after (between nodes)
                if($currentNode->data == $search){

                    $nextNode = $currentNode->next;
                    $newNode->next = $nextNode;
                    $currentNode->next = $newNode;
                    
                    $this->_totalNodes++;
                    return true;
                }
                
                // NOTE! The order do mater
                $currentNode = $currentNode->next;
                $nextNode = $currentNode->next;
                
            }
        }
        return false;
    }

Test

...
$l->insertAfter("Konrad", "Kubuś");

PHP Linked List – remove first element

    public function removeFirst(){
        if($this->_firstNode !== NULL){
            $this->_firstNode = $this->_firstNode->next;
            $this->_totalNodes--;
            return true;
        }else{
            return false;
        }
    }

Demo online

See interactive demo online here.

Linked list example with unit test: http://www.codediesel.com/php/linked-list-in-php/