All about Linked List

From Hawk Wiki
Revision as of 22:49, 3 April 2012 by Hall (Talk | contribs) (Linked list)

Jump to: navigation, search

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); ?>