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

This site is a digital habitat of Sameer Borate, a freelance web developer working in PHP, MySQL and WordPress. I also provide web scraping services, website design and development and integration of various Open Source API's. Contact me at metapix[at]gmail.com for any new project requirements and price quotes.

15 Responses

1

John

March 31st, 2009 at 3:08 am

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

2

Artem Russakovskii

June 10th, 2009 at 1:20 am

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

June 18th, 2009 at 4:32 pm

Do you have example of double linklist non circular for php

sameer

June 18th, 2009 at 8:31 pm

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

5

My name

August 28th, 2009 at 4:39 am

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!

sameer

August 28th, 2009 at 5:36 am

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

January 3rd, 2010 at 7:36 am

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

sameer

January 3rd, 2010 at 10:21 am

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

February 23rd, 2010 at 1:31 pm

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?

sameer

February 23rd, 2010 at 9:34 pm

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

February 24th, 2010 at 2:03 am

http://pastie.org/840202

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

12

Ben

September 22nd, 2012 at 11:31 am

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

March 1st, 2013 at 3:08 am

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

April 16th, 2013 at 1:03 am

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

December 16th, 2014 at 6:25 pm

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

Your thoughts

Sign up for fresh content in your email