Linked List implementation in PHP

Posted by sameer
on June 24, 2008

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.

CODE:

<?php
 
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 also 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;
            }
        }
    }
}
 
?>

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

algorithms, php
Add a comment

Benchmarking PHP code

Posted by sameer
on June 24, 2008

Code tuning is an essential part of programming. But most programmers would rather try to complete the project in hand then spend time optimizing a piece of code. A well tuned and optimized code block can speedup your application by an order of magnitude or even more.

Many people confuse profiling with benchmarking. A profiler is a analysis tool that lets you measure the performance of code at runtime. Profiling an application lets you find bottlenecks in your application code. You can find which part of your code is taking most of the time, you can than optimize that part of code. For example if there are 4 functions in your application, profiling may report the following distribution:

function a: 68%
function b: 12%
function c: 1.3%
function d: 18.7%

i.e function ‘a’ accounts for about 70% of the execution time in your application; if you can optimize that function it will boost your application performance considerably. If you had executed the above code on a laptop, and than executed the same on a fast server the code may run in half the time, but the distribution will remain the same. The distribution is what is important in profiling.

Benchmarking is different. It lets you find exactly how long it takes to execute a piece of code. For example I have developed two versions of a sorting algorithm for a application : Sort1(), and Sort2(). If I’ve to find which is faster than I can use a benchmarking software for the same.

To take a contrived example, I recently implemented a Linked List class in PHP (brushing up on my data structure skills), with all the usual functions a linked-list requires - ‘deleteNode‘, ‘insertFirstNode‘, ‘insertLastNode‘, ‘reverseList‘ etc. I was quite happy with the outcome untill I ran a benchmark between two functions - ‘insertFirstNode‘ and ‘insertLastNode‘. Here is a benchmark report for the two functions for various amount of nodes, in table and graph format. The last column shows by how much the ‘insertLastNode‘ is slower than the ‘insertFirstNode‘ function.


benchmark2

As you can see from the report ‘insertLastNode‘ takes exponential time to insert nodes. For example, when inserting 3000 nodes, ‘insertLastNode‘ is 30 times slower then ‘insertFirstNode‘. The reason for this is that ‘insertLastNode‘ has to traverse the entire list to find the last node before adding a new node, while ‘insertFirstNode‘ always adds a new node at the beginning of the list. The simple solution as all you ‘data structure fans’ know is to add a pointer that points to the last node of the list; so every time you have to add a node to the end of the list you use the end node pointer. After making the necessary changes I ran the benchmark and here are the results.

benchmark3

As you can see now both the functions take an equal amount of time to insert a node. Before the code tuning ‘insertLastNode’ took more than 6 seconds to insert 3000 nodes, while after tuning less than quarter of a second.

The whole point of this exercise is to tell you that code tuning can make a tremendous difference to how your application performs.

Installation
You can download the Benchmark pacakage from here or use the pear installer like below:

c:\pear install Benchmark

Using the package:
Using the package for benchmarking is simple enough. A implementation is shown below.

<?php
 
    /* The following sample function is what we
       want to test */
 
    function someFunction()
    {
        for($i=1; $i < 1000; $i++)
            $d = sqrt($i);
    }
 
 
    /* include the PEAR::Benchmark package */
    require_once 'Benchmark/Iterate.php';
 
    $bench = new Benchmark_Iterate;
 
    /* Run the above function 100 times.
       If you want to pass parameters to the function,
       you can add it after the function name like this:
       $bench->run(100, 'someFunction', para1, para2, para n);
    */
    $bench->run(100, 'someFunction');
 
    /* Get the results */
    $result = $bench->get();
 
    /* Display the mean time the function 'someFunction'
       takes to execute */
    print $result['mean'];
 
?>

Output:

0.022045
php, tools
1 comment so far

Adding HeatMaps to your website

Posted by sameer
on May 13, 2008

ClickHeat is a wonderful PHP software that lets you add Heatmaps for your webpages. Heatmaps are visual representation of clicks on a HTML page, showing hot and cold click zones. It can be useful to see at a glance which webpage areas are getting the most clicks as this areas get redder in color while the areas receiving less clicks are white. The software has many options to tweak, and the heatmaps can be added on a per page basis.

A sample heatmap image is shown below. You can also use the clickheat class in your own PHP applications. The software doesn’t require any database, only GD graphics library must be enabled on the server, which in most cases already is.

You can view a heatmap for the index page for this site here. I’ve presently only added click log for the index page, so try clicking on the index page links to update the heatmap.

username : visitor
password: visitor

If you don’t see any changes in the heatmap, click on the “log my clicks” link in the right corner or try logging out and then logging in again.

heatmap

php, visualization
2 Comments

Which is the most popular version of PHP today

Posted by sameer
on May 9, 2008

The graphic below displays the market share of each PHP version as on march 2008. The blue graph represents the sum of all preceding versions.

PHP 5.2.5 now is the most popular version of PHP followed closely by PHP 4.4.8 and 4.4.7. This information can be helpful if you are planning on creating an Open source project or are thinking of moving past the version 4 mark in your professional career but are hesitant regarding the version 5 support on servers.
Read the rest of this entry »

php
3 Comments

Tip : PHP Mail()

Posted by sameer
on May 7, 2008

The PHP mail() function on success returns a 1 or a 0 . This is not the same thing as the email successfully being sent or received. You cannot easily test for either using PHP.

php, tip
Add a comment
Next Page