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

18 Responses

  1. John says:

    I prefer to use “classic php arrays” for things like this…

  2. Nice, clean, and complete set of functions, and with Unit tests!

    I wrote my own implementation and found this a perfect reference to double check everything against.

  3. ramdani says:

    Do you have example of double linklist non circular for php

  4. sameer says:

    Not at present. But I’ll surely add it in coming days.

  5. My name says:

    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!

  6. sameer says:

    And you are absolutely right. Actually the above code was from a Singleton library, and hence the static modifier. You can see that my other post

    http://www.codediesel.com/algorithms/doubly-linked-list-in-php/

    does away with the static modifier for the ‘count’ variable. But I’ll make the necessary changes on this one too.

  7. usman says:

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

  8. sameer says:

    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.

  9. Miha says:

    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?

  10. sameer says:

    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).

  11. Miha says:

    http://pastie.org/840202

    I tried but still segfault, when I get to 29489 it craches.

  12. Ben says:

    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

  13. Buck says:

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

  14. Mas Ripan says:

    Building Converted Indexs:

    Problem we have :

    -how to combine Linked List with BST..
    -we have 2 dokument text (file .txt)

    ex. Doc 1 contain : car, laptop, mobile, glass
    Doc 2 contain : train, sky globe, phone

    and then we sort both of this dokument with BST and then puts

    illusstration for case like picture below..
    http://sphotos-e.ak.fbcdn.net/hphotos-ak-snc6/165402_3961720941285_1372241414_n.jpg

  15. Jovin says:

    Good example of link list in PHP. Remind me about data structure lesson in Pascal. Thanks for sharing.

  16. Ajay says:

    Thanks, Nice content and very understandable..

  17. Anita says:

    Can I please get help with the code to implement the linked lists and other data structures.. I mean implementation in real situations because this code runs bt I don’t know to make an interface where one who doesn’t know about linked lists and other data structures can use that interface u experience the functions of these data structures.. Like how they real operate in real life… Please help me out ..otherwise thank u for the code u posted

  18. sameer says:

    Honestly, in PHP there are very rare occasions where you require a linked list. It can be useful if you are building maybe a graph structure or some dynamic record structure. Anyways, it is easy to integrate it into your application as shown in the ‘PHPunit test’ section.