<?php

/** 
* Title: Single linked list
* Description: Implementation of a single linked list in PHP 
* @author Sameer Borate | codediesel.com
* @version 1.0 20th June 2008
*/

class ListNode
{
    /* Data to hold */
    public $data;
    
    /* Link to next node */
    public $next;
    
    
    /* Node constructor */
    function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
    
    function readNode()
    {
        return $this->data;
    }
}


class LinkList
{
    /* Link to the first node in the list */
    private $firstNode;
    
    /* Link to the last node in the list */
    private $lastNode;
    
    /* Total nodes in the list */
    private static $count;
    
    
    /* List constructor */
    function __construct()
    {
        $this->firstNode = NULL;
        $this->lastNode = NULL;
        self::$count = 0;
    }

    public function isEmpty()
    {
        return ($this->firstNode == NULL);
    }
    
    public function insertFirst($data)
    {
        $link = new ListNode($data);
        $link->next = $this->firstNode;
        $this->firstNode = &$link;
        
        /* If this is the first node inserted in the list
           then set the lastNode pointer to it.
        */
        if($this->lastNode == NULL)
            $this->lastNode = &$link;
            
        self::$count++;
    }
    
    public function insertLast($data)
    {
        if($this->firstNode != NULL)
        {
            $link = new ListNode($data);
            $this->lastNode->next = $link;
            $link->next = NULL;
            $this->lastNode = &$link;
            self::$count++;
        }
        else
        {
            $this->insertFirst($data);
        }
    }
    
    public function deleteFirstNode()
    {
        $temp = $this->firstNode;
        $this->firstNode = $this->firstNode->next;
        if($this->firstNode != NULL)
            self::$count--;
            
        return $temp;
    }
    
    public function deleteLastNode()
    {
        if($this->firstNode != NULL)
        {
            if($this->firstNode->next == NULL)
            {
                $this->firstNode = NULL;
                self::$count--;
            }
            else
            {
                $previousNode = $this->firstNode;
                $currentNode = $this->firstNode->next;
                
                while($currentNode->next != NULL)
                {
                    $previousNode = $currentNode;
                    $currentNode = $currentNode->next;
                }
                
                $previousNode->next = NULL;
                self::$count--;
            }
        }
    }
    
    public function deleteNode($key)
    {
        $current = $this->firstNode;
        $previous = $this->firstNode;
        
        while($current->data != $key)
        {
            if($current->next == NULL)
                return NULL;
            else
            {
                $previous = $current;
                $current = $current->next;
            }
        }
        
        if($current == $this->firstNode)
            $this->firstNode = $this->firstNode->next;
        else
            $previous->next = $current->next;
            
        self::$count--;   
    }
    
    public function find($key)
    {
        $current = $this->firstNode;
        while($current->data != $key)
        {
            if($current->next == NULL)
                return null;
            else
                $current = $current->next;
        }
        return $current;
    }
    
    public function readNode($nodePos)
    {
        if($nodePos <= self::$count)
        {
            $current = $this->firstNode;
            $pos = 1;
            while($pos != $nodePos)
            {
                if($current->next == NULL)
                    return null;
                else
                    $current = $current->next;
                    
                $pos++;
            }
            return $current->data;
        }
        else
            return NULL;
    }
    
    public function totalNodes()
    {
        return self::$count;
    }
    
    public function readList()
    {
        $listData = array();
        $current = $this->firstNode;
        
        while($current != NULL)
        {
            array_push($listData, $current->readNode());
            $current = $current->next;
        }
        return $listData;
    }
    
    public function reverseList()
    {
        if($this->firstNode != NULL)
        {
            if($this->firstNode->next != NULL)
            {
                $current = $this->firstNode;
                $new = NULL;
                
                while ($current != NULL)
                {
                    $temp = $current->next;
                    $current->next = $new;
                    $new = $current;
                    $current = $temp;
                }
                $this->firstNode = $new;
            }
        }
    }
}

?>


Test Case

<?php

require_once 'linklist.class.php';
require_once 'PHPUnit/Framework.php';

class LinkListTest extends PHPUnit_Framework_TestCase
{
    public function testLinkList()
    {
        
        $totalNodes = 100;
        
        $theList = new LinkList();
    
        for($i=1; $i <= $totalNodes; $i++)
        {
            $theList->insertLast($i);
        }
        
        $this->assertEquals($totalNodes, $theList->totalNodes());
        
        for($i=1; $i <= $totalNodes; $i++)
        {
            $theList->insertFirst($i);
        }
	
        $totalNodes = $totalNodes * 2;
        $this->assertEquals($totalNodes, $theList->totalNodes());
        
        $theList->reverseList();
        $this->assertEquals($totalNodes, $theList->totalNodes());
        
        $theList->deleteFirstNode();
        $this->assertEquals($totalNodes - 1, $theList->totalNodes());
        
        $theList->deleteLastNode();
        $this->assertEquals($totalNodes - 2, $theList->totalNodes());
        
        /* Delete node which has a value of '5' */
        $theList->deleteNode(5);
        $this->assertEquals($totalNodes - 3, $theList->totalNodes());
        
        /* Insert a node at the end of the list with a value of '22' */
        $theList->insertLast(22);
        $this->assertEquals($totalNodes - 2, $theList->totalNodes());
        
        /* Find a node with a value of '25' (is in the list) */
        $found = $theList->find(25);
        $this->assertEquals(25, $found->data);

        /* Find a node with a value of '125' (is not in the list) */
        $found = $theList->find(125);
        $this->assertNull($found);
        
        /* Return the data stored in the node at position '50' */
        $data = $theList->readNode(50);
        $this->assertEquals(50, $data);
        
        /* Return the data stored in the node at position '450' */
        $data = $theList->readNode(450);
        $this->assertNull($data);
    }
}

?>