Difference between revisions of "All about Linked List"

Revision as of 19:05, 28 February 2012

Linked list

Create, to array, insertm inverse

<?php
//Everthing about linked list
//Create a List
class Node{
	public $next=null;
	public $prev=null;
	public $val;
	function __construct($v){
		$this->val=$v;
	}
	function readNode(){
        return $this->val;
    }
}
class LinkList{
	private $firstNode;
	private $lastNode;
	private $count;
	function __construct(){
		$this->firstNode=null;
		$this->lastNode=null;
		$this->count=0;
	}
	function isEmpty(){
		return ($this->firstNode === NULL);
	}
	function insert($v){
		if($this->isEmpty()){//insert first
			$link = new Node($v);
			$link->next = $this->firstNode;
			$this->firstNode = &$link;
			if($this->lastNode == NULL)
				$this->lastNode = &$link;
		}
		else{//insert last
			$link = new Node($v);
            $this->lastNode->next = $link;
            $link->next = NULL;
            $this->lastNode = &$link;
		}
        $this->count++;
	}
	public function totalNodes(){
        return $this->count;
    }
	public function readNode($nodePos){
        if($nodePos < $this->count)
        {
            $current = $this->firstNode;
            $pos = 0;
            while($pos != $nodePos)
            {
                if($current->next == NULL)
                    return null;
                else
                    $current = $current->next;
                $pos++;
            }
            return $current->val;
        }
        else
            return NULL;
    }
	public function readList()
    {
        $listData = array();
        $current = $this->firstNode;
 
        while($current != NULL)
        {
            array_push($listData, $current->val);
            $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)
                {
                    $next = $current->next;
                    $current->next = $new;
                    $new = $current;
                    $current = $next;
                }
                $this->firstNode = $new;
            }
        }
    }
	public function reverseList1(){
        $prev=$this->firstNode;//first
		$newLastNode=$this->firstNode;//construct new last node
		$pos=$this->firstNode->next;//pos start from the second node
		$newLastNode->next=null;
		$next=null;
		
		while($pos!=null){
			$next=$pos->next;
			$pos->next=$prev;
			$prev=$pos;
			$pos=$next;
		}
		// to the last node: $pos=$lastnode->next=null and $prev=$lastnode
		$this->firstNode=$prev;
		$this->lastNode=$newLastNode;
    }
}

$ls=new LinkList(0);
for($i=0;$i<20;$i+=2){
	$ls->insert($i);
}
$ls->reverseList1();
$lisrArray=$ls->readList();
var_dump($lisrArray);
?>