Linked List implementation in PHP

Data structures are one of the core elements of computer science and they are also fun to program. But being a web developer the opportunity for implementing them in any application is quite rare. But then I thought, What the heck! I can just code for the joy of it, and it will also help me brush up on my DS skills. So here it is, a single linked list implementation in PHP for whoever may care. I will be posting other data structure and algorithm implementations here, so keeping watching. The code is given below.

CODE:

<?php
 
/** 
* Title: Single linked list
* Description: Implementation of a single linked list in PHP 
* @author Sameer Borate | codediesel.com
* @version 1.0.1 Updated: 16th August 2012
*/
 
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 $count;
 
 
 
    /* List constructor */
    function __construct()
    {
        $this->firstNode = NULL;
        $this->lastNode = NULL;
        $this->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;
 
        $this->count++;
    }
 
    public function insertLast($data)
    {
        if($this->firstNode != NULL)
        {
            $link = new ListNode($data);
            $this->lastNode->next = $link;
            $link->next = NULL;
            $this->lastNode = &$link;
            $this->count++;
        }
        else
        {
            $this->insertFirst($data);
        }
    }
 
    public function deleteFirstNode()
    {
        $temp = $this->firstNode;
        $this->firstNode = $this->firstNode->next;
        if($this->firstNode != NULL)
            $this->count--;
 
        return $temp;
    }
 
    public function deleteLastNode()
    {
        if($this->firstNode != NULL)
        {
            if($this->firstNode->next == NULL)
            {
                $this->firstNode = NULL;
                $this->count--;
            }
            else
            {
                $previousNode = $this->firstNode;
                $currentNode = $this->firstNode->next;
 
                while($currentNode->next != NULL)
                {
                    $previousNode = $currentNode;
                    $currentNode = $currentNode->next;
                }
 
                $previousNode->next = NULL;
                $this->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)
         {
              if($this->count == 1)
               {
                  $this->lastNode = $this->firstNode;
               }
               $this->firstNode = $this->firstNode->next;
        }
        else
        {
            if($this->lastNode == $current)
            {
                 $this->lastNode = $previous;
             }
            $previous->next = $current->next;
        }
        $this->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 <= $this->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 $this->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;
            }
        }
    }
}
 
?>

PHPUnit test :

<?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'
           which is in the list */
        $data = $theList->readNode(50);
        $this->assertEquals(50, $data);
 
        /* Return the data stored in the node at position '450'
           which is not in the list */
        $data = $theList->readNode(450);
        $this->assertNull($data);
    }
}
 
?>

Download code



16 thoughts on “Linked List implementation in PHP

  1. Why is the count static?
    IMHO this is an attribute that belongs to an instance and not the whole class! Otherwise, you would count all nodes in all lists you have currently instantiated!

  2. hi. i learn linklist in c++ for solve the memory allocation problem.
    but why you use this in php….
    cnfuzd…

  3. Memory allocation is one small application of a linked-list. Linked lists are general data structures which can be used to define other specific data structures like hash tables, stacks, queues etc.

  4. I’m testing with windows 7 and wamp php 5.3.0
    $list = new LinkList();
    echo memory_get_usage(1)/1024 . “kB\n”;
    for($i = 0; $i small 50000; $i++) {
    $list->insertLast(10);
    }
    echo memory_get_usage(1) . “B\n”;

    This causes php cli seg. fault, i also tried on linux also seg fault,
    so there is some kind of limit if I try this it works:

    $array = array();
    for($i = 0; $i small 200000; $i++) {
    $array[] = new LinkedListNode(10);
    }

    Where/what is the limit?

  5. Hello Miha,
    The code works fine at my end on both Windows and Linux. The most probable reason for the Segmentation Fault could be one of the PHP extensions. Try running it without the memory_get_usage(1).

  6. You have a lot of mistakes in this code, mostly related to your understanding of variables and objects in PHP.

    You use &$link. In PHP5+ there is no reason to use references and its in fact considered bad practice. $link is a variable that points to the object(like a reference, but not a reference)

    An example of an error as a result of variable assignment can be seen in the deleteNode method.

    if($this->count == 1)
    {
    $this->lastNode = $this->firstNode;
    }
    $this->firstNode = $this->firstNode->next;

    Your last node points to your “original” first node and your $this->firstNode points to NULL. This in the long term could create a bug in which memory that should be released was not as you still have a variable pointing to the object

    Best Regards
    Ben

  7. When you are assigning the $this->firstNode value to $link->next in the insertFirst() function, what will be the value of $this->firstNode there ?

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>