Doubly Linked List in php


Posted in: algorithms | Save to del.icio.us | 13 Jul 2009



Below is a non circular doubly linked list php implementation. I do not frequently encounter linked-list coding in practice, but doing it just for the fun of it feels nice; also helps to brush up on those data structure theories.

<?php
 
/* doublelist.class.php */
 
class ListNode {
 
    public $data;
    public $next;
    public $previous;
 
    function __construct($data) {
        $this->data = $data;
    }
 
    public function readNode() {
        return $this->data;
    }
 
}
 
 
class DoublyLinkedList {
 
    private $_firstNode;
    private $_lastNode;
    private $_count;
 
    function __construct() {
        $this->_firstNode = NULL;
        $this->_lastNode = NULL;
        $this->_count = 0;
    }
 
    public function isEmpty() {
        return ($this->_firstNode == NULL);
    }
 
    public function insertFirst($data) {
        $newLink = new ListNode($data);
 
        if($this->isEmpty()) {
            $this->_lastNode = $newLink;
        } else {
            $this->_firstNode->previous = $newLink;
        }
 
        $newLink->next = $this->_firstNode;
        $this->_firstNode = $newLink;
        $this->_count++;
    }
 
 
    public function insertLast($data) {
        $newLink = new ListNode($data);
 
        if($this->isEmpty()) {
            $this->_firstNode = $newLink;
        } else {
            $this->_lastNode->next = $newLink;
        }
 
        $newLink->previous = $this->_lastNode;
        $this->_lastNode = $newLink;
        $this->_count++;
    }
 
 
    public function insertAfter($key, $data) {
        $current = $this->_firstNode;
 
        while($current->data != $key) {
            $current = $current->next;
 
            if($current == NULL)
                return false;
        }
 
        $newLink = new ListNode($data);
 
        if($current == $this->_lastNode) {
            $newLink->next = NULL;
            $this->_lastNode = $newLink;
        } else {
            $newLink->next = $current->next;
            $current->next->previous = $newLink;
        }
 
        $newLink->previous = $current;
        $current->next = $newLink;
        $this->_count++;
 
        return true;
    }
 
 
    public function deleteFirstNode() {
 
        $temp = $this->_firstNode;
 
        if($this->_firstNode->next == NULL) {
            $this->_lastNode = NULL;
        } else {
            $this->_firstNode->next->previous = NULL;
        }
 
        $this->_firstNode = $this->_firstNode->next;
        $this->_count--;
        return $temp;
    }
 
 
    public function deleteLastNode() {
 
        $temp = $this->_lastNode;
 
        if($this->_firstNode->next == NULL) {
            $this->firtNode = NULL;
        } else {
            $this->_lastNode->previous->next = NULL;
        }
 
        $this->_lastNode = $this->_lastNode->previous;
        $this->_count--;
        return $temp;
    }
 
 
    public function deleteNode($key) {
 
        $current = $this->_firstNode;
 
        while($current->data != $key) {
            $current = $current->next;
            if($current == NULL)
                return null;
        }
 
        if($current == $this->_firstNode) {
            $this->_firstNode = $current->next;
        } else {
            $current->previous->next = $current->next;
        }
 
        if($current == $this->_lastNode) {
            $this->_lastNode = $current->previous;
        } else {
            $current->next->previous = $current->previous;
        }
 
        $this->_count--;
        return $current;
    }
 
 
    public function displayForward() {
 
        $current = $this->_firstNode;
 
        while($current != NULL) {
            echo $current->readNode() . " ";
            $current = $current->next;
        }
    }
 
 
    public function displayBackward() {
 
        $current = $this->_lastNode;
 
        while($current != NULL) {
            echo $current->readNode() . " ";
            $current = $current->previous;
        }
    }
 
    public function totalNodes() {
        return $this->_count;
    }
 
}
 
 
?>

PHPUnit Test:

<?php
 
require_once 'doublelist.class.php';
require_once 'PHPUnit/Framework.php';
 
class LinkListTest extends PHPUnit_Framework_TestCase {
 
    public function testLinkList() {
 
        $totalNodes = 100;
 
        $theList = new DoublyLinkedList();
 
        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->deleteFirstNode(); $totalNodes--;
        $this->assertEquals($totalNodes, $theList->totalNodes());
 
        $theList->deleteLastNode(); $totalNodes--;
        $this->assertEquals($totalNodes, $theList->totalNodes());
 
        /* Delete node which has a key value of '50' */
        $theList->deleteNode(50); $totalNodes--;
        $this->assertEquals($totalNodes, $theList->totalNodes());
 
        /* Insert a node at the end of the list with a value of '22' */
        $theList->insertLast(22); $totalNodes++;
        $this->assertEquals($totalNodes, $theList->totalNodes());
 
    }
}
 
?>
Download Source
File size : 1.4 kB





4 Responses

1

zahid

August 6th, 2009 at 4:37 am

THANKS

2

Jakub Vrána

August 18th, 2009 at 8:34 am

3

Fred

July 6th, 2010 at 3:44 pm

Thanks for this :)
I know this is almost a year old but on insertAfter you’re calling
new Link($data);
but it should be
new ListNode($data);

sameer

July 6th, 2010 at 8:27 pm

Thanks for the correction.

Comments are disabled for this post, but if you have spotted an error, feel free to contact me.

Get latest updates by E-mail

About this blog

This site is a digital habitat of Sameer, a freelance web developer working from Pune.More

  • Users Online

    • 9 Users Online
    • 8 Guests, 1 Bot
  • RECENT COMMENTS

    ON TWITTER