PHP Classes

File: LinkedList.php

Recommend this page to a friend!
  Classes of Oddleif Halvorsen   Double Linked List   LinkedList.php   Download  
File: LinkedList.php
Role: Class source
Content type: text/plain
Description: The linked list class
Class: Double Linked List
A double linked list similar to LinkedList in Java
Author: By
Last change: v1.2 - Made som major changes to the internal design of the class. In short head and tail changed from beeing references to the first and last node, to become nodes themselvs. The interface / functioncalls to use the class is still the same, so just replace the oldone with this.
Date: 18 years ago
Size: 6,739 bytes
 

Contents

Class file image Download
<?php

/**
 * <p>Title: Double linked list</p>
 * <p>Description: Implementation of a double linked list in PHP</p>
 * @requires ListNode.php, Iterator.php and ListIterator.php
 * @testscript LinkedListTest.php
 * @author Oddleif Halvorsen | leif-h@online.no
 * @version 1.2
 */

include_once("ListNode.php");
   
class
LinkedList{
     var
$head; // reference to the first node
 
var $tail; // reference to the last node
 
var $size; // The total number of nodes

 
function LinkedList(){
       
//head and tail only points to the head and tail of the list,
        //the list nodes does not point on head and tail! Hence, head and
        //tail are not part of the list.
       
$this->head = new ListNode();
       
$this->tail = new ListNode();
       
$this->size = 0;
  }
   
   
/**
     * Adds a new object at a specific index, pushes
     * the current further back into the list.
     * @param $index Numeric value between 0 and $this->size()-1
     * @param &$object A reference to the object that is to be inserted
     * @return TRUE == insertino ok || FALSE == index out of bounds
     */
   
function addAtPosition($index, &$object){
       
//checks if index is not out of bounds
       
if($index >= 0 && $index <= $this->size()-1){
           
$newNode = $this->getNewNode($object);
           
$nodeAtIndex = &$this->getNode($index);
           
           
//new node at head
           
if($index == 0){
               
$newNode->setNext(&$nodeAtIndex);
               
$nodeAtIndex->setPrevious(&$newNode);
               
$this->head->setNext(&$newNode);
            }
            else
//somewhere else in the list
               
$this->insertNodeInList(&$newNode, &$nodeAtIndex);

           
$this->size++;
            return
TRUE;
        }
   
        return
FALSE;
  }
   
   
/**
     * Inserts a new node into a the list on a position
     * where it has nodes bothe before an after.
     * NOT at index 0 or $this->size()-1
     * @param &$newNode A reference to the node that is inserted in the list.
     * @param &$nodeAtIndex The node it is pushing away.
     */
   
function insertNodeInList(&$newNode, &$nodeAtIndex){
       
$previousNode = &$nodeAtIndex->getPrevious();
       
       
$newNode->setPrevious(&$previousNode);
       
$newNode->setNext(&$nodeAtIndex);
       
$nodeAtIndex->setPrevious(&$newNode);
       
$previousNode->setNext(&$newNode);
    }

   
/**
     * Create a new node,
     * Appends a new node to the tail
     * @param &$element The element you want to append to the list.
     */
 
function add(&$element){
       
$newNode = $this->getNewNode(&$element);

       
//A non empty list, mostly the case.
       
if(!$this->isEmpty()){
           
$previousNode = &$this->tail->getPrevious();
           
$previousNode->setNext(&$newNode);
           
$newNode->setPrevious(&$previousNode);
        }
        else
//empty
           
$this->head->setNext(&$newNode);
       
       
$this->tail->setPrevious(&$newNode);
       
       
$this->size++;
  }
   
   
/**
     * Generates a new ListNode object.
     * @param &$object The value of the ListNode
     * @return A ListNode object
     */
   
function getNewNode(&$object){
        return new
ListNode(&$object);
    }

   
/**
     * Empties the list.
     */
 
function clear(){
       
$this->head = NULL;
       
$this->tail = NULL;
       
$this->size = 0;
  }

   
/**
     * Retrevies the object at the specified index.
     * @param $index A value between 0 and $this->size()
     * @return The object || FALSE == index out of bounds
     */
   
function get($index){
       
//if the list is noe empty, and the index is a legal number
       
if(!$this->isEmpty() && (($index >= 0) && ($index < $this->size()))){
            if(
$index < ($this->size()/2)) //searches from head
               
$tmpNode = &$this->getNode($index);
            else
//searches from tail
               
$tmpNode = &$this->getNodeReversed($index);
               
            return
$tmpNode->getNodeValue();
        }

       
//index out of bounds.
       
return FALSE;
    }
       
   
/**
     * Checks if the list is empty
     * @return TRUE == empty || FALSE == not empty
     */
   
function isEmpty(){
    return (
$this->size == 0 ? TRUE : FALSE );
    }
   
    function
removeObjectAtIndex($index){
        if(!
$this->isEmpty() && ($index>=0 && $index<=($this->size()-1))){
           
$nodeToRemove = &$this->getNode($index);
            switch(
$index){
                case
0: //removing head
                               
$nextNode = &$nodeToRemove->getNext();
                               
$nextNode->setPrevious(NULL);
                               
$this->head->setNext(&$nextNode);
                                break;
                case (
$this->size()-1):
                               
//removing tail
                               
$previousNode = &$nodeToRemove->getPrevious();
                               
$previousNode->setNext(NULL);
                               
$this->tail->setPrevious(&$previousNode);
                                break;
                default:
                               
//gets the node before and after the deleted node
                               
$previousNode = &$nodeToRemove->getPrevious();
                               
$nextNode = &$nodeToRemove->getNext();
                               
//updates the references for the before and after node.
                               
$previousNode->setNext(&$nextNode);
                               
$nextNode->setPrevious(&$previousNode);
                                break;
            }
           
//compleatly removes the node
           
$nodeToRemove->setPrevious(NULL);
           
$nodeToRemove->setNext(NULL);

           
//decreases the size of the list.
           
$this->size--;
            return
TRUE;
        }
        return
FALSE;
    }
   
   
/**
     * Retrevies a node at a spesific index
     * @param $index A value between 0 and $this->size()
     * @return The node || FALSE == index out of bounds
     */
   
function &getNode($index){
       
//the list is not empty, and the index is not out of bounds
       
if(!$this->isEmpty() && (($index >= 0) && ($index < $this->size()))){
           
$tmpNode = &$this->head;
            for(
$i=0; $i<=$index; $i++)
                   
$tmpNode = &$tmpNode->getNext();

            return
$tmpNode;
        }
        return
FALSE;
    }
   
   
/**
     * Retrevies the object from the tail of the list
     * @param $index A value between 0 and $this->size()
     * @return The node || FALSE == index out of bounds
     */
   
function &getNodeReversed($index){
       
//the list is not empty, and the index is not out of bounds
       
if(!$this->isEmpty() && (($index >= 0) && ($index < $this->size()))){
           
$tmpNode = &$this->tail;
            for(
$i=($this->size()-1); $i>=$index; $i--)
                   
$tmpNode = &$tmpNode->getPrevious();

            return
$tmpNode;
        }
        return
FALSE;
       
    }

   
/**
     * Returns the size of the list
     * @return The number of elements in the list
     */
    
   
function size(){
        return
$this->size;
    }
   
   
/**
     * Returns an iterator to use on the list
     * @return An Iterator object, tha iterator starts on the list head.
     */
   
function iterator(){
        include_once(
"Iterator.php");
        return new
Iterator(&$this->head, &$this);
    }
   
   
/**
     * Returns an ListIterator to use on the list
     * @return An ListIterator object, tha iterator starts on the list head.
     */
   
function listIterator(){
        include_once(
"ListIterator.php");
        return new
ListIterator($this->head, $this);
    }
   
    function
incSize(){
       
$this->size++;
    }
   
    function
decSize(){
       
$this->size--;
    }
}
?>