Implement singly linked list using PHP

This article mainly introduces the use of PHP to implement a singly linked list, which has certain reference value. Now I share it with you. Friends in need can refer to it

Singly linked list, as the name suggests, is a linked data structure. It has a header, and except for the last node, all nodes have their successor nodes. As shown below.

First, we write the class of the linked list node. Each node in the singly linked list saves its data field and back-drive pointer

##[php] view plain copy

//链表节点   
class node {   
    public $id; //节点id   
    public $name; //节点名称   
    public $next; //下一节点   
     
    public function __construct($id, $name) {   
        $this->id = $id;   
        $this->name = $name;   
        $this->next = null;   
    }   
}

Copy after login

There are two particularly important methods in the linked list, insertion and deletion. Insertion requires finding the insertion position, pointing the next pointer of the previous element to the inserted node, and pointing the next pointer of the inserted node to the next node, as shown on the left side of the figure below. Deletion points the next pointer of the previous node to the next node and returns the data content of the deleted element, as shown on the right side of the figure below.

##

[php] view plain copy

1. //单链表   
   class singelLinkList {   
       private $header; //链表头节点   
        
       //构造方法   
       public function __construct($id = null, $name = null) {   
           $this->header = new node ( $id, $name, null );   
       }   
     
       //获取链表长度   
       public function getLinkLength() {   
           $i = 0;   
           $current = $this->header;   
           while ( $current->next != null ) {   
               $i ++;   
               $current = $current->next;   
           }   
           return $i;   
       }   
     
       //添加节点数据   
       public function addLink($node) {   
           $current = $this->header;   
           while ( $current->next != null ) {   
               if ($current->next->id > $node->id) {   
                   break;   
               }   
               $current = $current->next;   
           }   
           $node->next = $current->next;   
           $current->next = $node;   
       }   
     
       //删除链表节点   
       public function delLink($id) {   
           $current = $this->header;   
           $flag = false;   
           while ( $current->next != null ) {   
               if ($current->next->id == $id) {   
                   $flag = true;   
                   break;   
               }   
               $current = $current->next;   
           }   
           if ($flag) {   
               $current->next = $current->next->next;   
           } else {   
               echo "未找到id=" . $id . "的节点！<br>";   
           }   
       }  
     
       //判断连表是否为空  
       public function isEmpty(){  
               return $this->header == null;  
       }  
     
       //清空链表  
       public function clear(){  
               $this->header = null;  
       }   
     
       //获取链表   
       public function getLinkList() {   
           $current = $this->header;   
           if ($current->next == null) {   
               echo ("链表为空!");   
               return;   
           }   
           while ( $current->next != null ) {   
               echo &#39;id:&#39; . $current->next->id . &#39;   name:&#39; . $current->next->name . "<br>";   
               if ($current->next->next == null) {   
                   break;   
               }   
               $current = $current->next;   
           }   
       }   
     
       //获取节点名字   
       public function getLinkNameById($id) {   
           $current = $this->header;   
           if ($current->next == null) {   
               echo "链表为空!";   
               return;   
           }   
           while ( $current->next != null ) {   
               if ($current->id == $id) {   
                   break;   
               }   
               $current = $current->next;   
           }   
           return $current->name;   
       }   
     
       //更新节点名称   
       public function updateLink($id, $name) {   
           $current = $this->header;   
           if ($current->next == null) {   
               echo "链表为空!";   
               return;   
           }   
           while ( $current->next != null ) {   
               if ($current->id == $id) {   
                   break;   
               }   
               $current = $current->next;   
           }   
           return $current->name = $name;   
       }   
   }  
   $lists = new singelLinkList ();   
   $lists->addLink ( new node ( 5, &#39;eeeeee&#39; ) );   
   $lists->addLink ( new node ( 1, &#39;aaaaaa&#39; ) );   
   $lists->addLink ( new node ( 6, &#39;ffffff&#39; ) );   
   $lists->addLink ( new node ( 4, &#39;dddddd&#39; ) );   
   $lists->addLink ( new node ( 3, &#39;cccccc&#39; ) );   
   $lists->addLink ( new node ( 2, &#39;bbbbbb&#39; ) );   
   $lists->getLinkList ();   
   echo "<br>-----------删除节点--------------<br>";   
   $lists->delLink ( 5 );   
   $lists->getLinkList ();  
   echo "<br>-----------更新节点名称--------------<br>";   
   $lists->updateLink ( 3, "222222" );   
   $lists->getLinkList ();  
   echo "<br>-----------获取节点名称--------------<br>";   
   echo $lists->getLinkNameById ( 5 );  
   echo "<br>-----------获取链表长度--------------<br>";   
   echo $lists->getLinkLength ();

   Copy after login

相关推荐：

使用php来解析实现二级域名重定向

The above is the detailed content of Implement singly linked list using PHP. For more information, please follow other related articles on the PHP Chinese website!