PHP data structure and sequential linked list, detailed explanation of the use of linked linear list

<?php

class ArrayList{

  private $list;

  private $size;

  //构造函数

  public function construct(){

   $this->list=array();

   $this->size=0;

  }

  public function initList(){

   $this->list=array();

   $this->size=0;

  }

  //删除链表

  public function destoryList(){

   if(isset($this->list)){

     unset($this->list);

    $this->size=0;

   }

  }

  //清空链表

  public function clearList(){

   if(isset($this->list)){

    unset($this->list);

   }

   $this->list=array();

   $this->size=0;

  }

  //判断链表是否为空

  public function emptyList(){

   if(isset($this->list)){

     if($this->size=0)

      return TRUE;

    else

     return FALSE;

   }

  }

  //链表长度

  public function lenghtList(){

   if(isset($this->list)){

    return $this->size;

   }

  }

  //取元素

  public function getElem($i){

   if($i<1||$i>$this->size){

    echo "溢出<br>";

    exit();

   }

   if(isset($this->list)&&is_array($this->list)){

    return $this->list[$i-1];

   }

  }

  //是否在链表中

  public function locateElem($e){

   if(isset($this->list)&&is_array($this->list)){

    for($i=0;$i<$this->size;$i++){

      if($this->list[$i]==$e){

       return $i+1;

      }

    }

    return 0;

   }

  }

  //前驱

  public function priorElem($i){

   if($i<1||$i>$this->size){

    echo "溢出";

    exit();

   }

   if($i==1){

    echo "没有前驱";

    exit();

   }

   if(isset($this->list)&&is_array($this->list)){

    return $this->list[$i-2];

   }

  }

  //后继

  public function nextElem($i){

   if($i<1||$i>$this->size){

    echo "溢出";

    exit();

   }

   if($i==$this->size){

    echo "没有后继";

    exit();

   }

   if(isset($this->list)&&is_array($this->list)){

    return $this->list[$i];

   }

  }

  //插入元素

  public function insertList($i,$e){

   if($i<1||$i>$this->size+1){

    echo "插入元素位置有误";

    exit();

   }

   if(isset($this->list)&&is_array($this->list)){

    if($this->size==0){

      $this->list[$this->size]=$e;

      $this->size++;

    }else{

      $this->size++;

      for($j=$this->size-1;$j>=$i;$j--){

       $this->list[$j]=$this->list[$j-1];

      }

      $this->list[$i-1]=$e;

    }

   }

  }

  //删除元素

  public function deleteLlist($i){

   if($i<1||$i>$this->size){

    echo "删除元素位置有误";

    exit();

   }

   if(isset($this->list)&&is_array($this->list)){

    if($i==$this->size){

      unset($this->list[$this->size-1]);

    }else{

      for($j=$i;$j<$this->size;$j++){

       $this->list[$j-1]=$this->list[$j];

      }

      unset($this->list[$this->size-1]);

     }

   $this->size--;

   }

  }

  //遍历

  public function printList(){

   if(isset($this->list)&&is_array($this->list)){

    foreach ($this->list as $value){

      echo $value." ";

    }

    echo "<br>";

   }

  }

}

?>

<?php

class LinkList {

  private $head;

  private $size;

  private $list;

  public function construct(){

   $this->head="";

   $this->size=0;

   $this->list=array();

  }

  public function initList(){

   $this->head="";

   $this->size=0;

   $this->list=array();

  }

  //删除链表

  public function destoryList(){

   if(isset($this->list)&&isset($this->head)){

    unset($this->list);

    unset($this->head);

   }

  }

  //清空链表

  public function clearList(){

   if(isset($this->list)){

    unset($this->list);

   }

   $this->list=array();

   $this->size=0;

   $this->head="";

  }

  //判断链表是否为空

  public function emptyList(){

   if(isset($this->list)){

    if($this->size==0)

      returnTRUE;

    else

      returnFALSE;

   }

  }

  //链表长度

  public function lenghtList(){

   if(isset($this->list)){

    return$this->size;

   }

  }

  //取元素

  public function getElem($i){

   if($i<1||$i>$this->size){

    echo "溢出<br>";

    exit();

   }

   if(isset($this->list)&&is_array($this->list)){

    $j=1;

    //头指针

    $tmp=$this->head;

    while($i>$j){

      if($this->list[$tmp]['next']!=null){

       $tmp=$this->list[$tmp]['next'];

       $j++;

      }

    }

    return  $this->list[$tmp]['data'];

   }

  }

  //是否在链表中

  public function locateElem($e){

   if(isset($this->list)&&is_array($this->list)){

    $tmp=$this->head;

    while($this->list[$tmp]['data']!=$e){

      if($this->list[$tmp]['next']!=null){

       $tmp=$this->list[$tmp]['next'];

      }else{

       returnFALSE;

      }

    }

    return TRUE;

   }

  }

  //前驱

  public function priorElem($i){

   if($i<1||$i>=$this->size){

    echo "溢出";

    exit();

   }

   if($i==1){

    echo "没有前驱";

    exit();

   }

   $tmp=$this->head;

   $j=1;

   while($i>$j+1){

    if($this->list[$tmp]['next']!=null){

      $j++;

      $tmp=$this->list[$tmp]['next'];

    }

   }

   return$this->list[$tmp]['data'];

  }

  //后继

  public function nextElem($i){

   if($i<1||$i>$this->size){

    echo "溢出";

    exit();

   }

   if($i==$this->size){

    echo "没有后继";

    exit();

   }

   $j=1;

   $tmp=$this->head;

   while($i>=$j){

    if($this->list[$tmp]['next']!=null){

      $j++;

      $tmp=$this->list[$tmp]['next'];

    }

   }

   return$this->list[$tmp]['data'];

  }

  //插入元素:后插法

  public function insertList($i,$e){

   if(isset($this->list)&&is_array($this->list)){

    //空表

    if($this->size==0){

      $this->head=$this->uuid();

      $this->list[$this->head]['data']=$e;

      $this->list[$this->head]['next']=NULL;

      $this->size++;

    }else{

      if($i<1||$i>$this->size){

      echo"插入元素位置有误";

      exit();

      }

      $j=1;

      $tmp=$this->head;

      while($i>$j){

       if($this->list[$tmp]['next']!=null){

         $j++;

         $tmp=$this->list[$tmp]['next'];

       }

      }

      $find=$tmp;

      $id=$this->uuid();

      if($this->list[$find]['next']==null){

       //尾部

       $this->list[$find]['next']=$id;

       $this->list[$id]['data']=$e;

       $this->list[$id]['next']=null;

       $this->size++;

      }else{

       //中间

       $this->list[$id]['next']=$this->list[$find]['next'];

       $this->list[$find]['next']=$id;

       $this->list[$id]['data']=$e;

       $this->size++;

      }

    }

   }

  }

  //删除元素

  public function deleteLlist($i){

   if($i<1||$i>$this->size){

    echo "删除元素位置有误";

    exit();

   }

   if(isset($this->list)&&is_array($this->list)){

    if($i==1){

      //删除头元素

      $this->head=$this->list[$this->head]['next'];

    }else{

      $tmp=$this->head;

      $j=1;

      while($i>$j+1){

       if($this->list[$tmp]['next']!=null){

         $j++;

         $tmp=$this->list[$tmp]['next'];

       }

      }

      //找到删除元素的前驱

      $find=$tmp;

      //删除的元素

      if($this->list[$find]['next']!=null){

       //不是最后一个元素

       $delete=$this->list[$find]['next'];

       $this->list[$find]['next']=$this->list[$delete]['next'];

      }else{

       $this->list[$tmp]['next']=null;

      }

    }

   }

  }

  public function traverstList(){

   $tmp=$this->head;

   while($this->list[$tmp]['next']!=NULL){

    $this->printList($this->list[$tmp]['data'],TRUE);

    $tmp=$this->list[$tmp]['next'];

   }

   $this->printList($this->list[$tmp]['data'],FALSE);

  }

  public function printList($str,$flag){

   if($flag){

    echo$str."->";

   }else {

    echo$str."<br>";

   }

  }

  //uuid 唯一码

  public  function uuid($prefix = '') {

  $chars =md5(uniqid(mt_rand(), true));

  $uuid = substr($chars,0,8) . '-';

  $uuid .=substr($chars,8,4) . '-';

  $uuid .=substr($chars,12,4) . '-';

  $uuid .=substr($chars,16,4) . '-';

  $uuid .= substr($chars,20,12);

  return $prefix. $uuid;

  }

}

?>