141017 PHP单链表结构

单链表结构(建议最后阅读)：

链表中的数据是以节点来表示的，每个节点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个节点的地址数据。

以“结点的序列”表示线性表称作线性链表（单链表）

单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。
因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i

1秒看懂单链结构

object(singelLinkList)#1 (1) {
  ["header":"singelLinkList":private]=>
  object(node)#2 (3) {
    ["id"]=>
    NULL
    ["name"]=>
    NULL
    ["next"]=>
    object(node)#4 (3) {
      ["id"]=>
      int(1)
      ["name"]=>
      string(6) "aaaaaa"
      ["next"]=>
      object(node)#8 (3) {
        ["id"]=>
        int(2)
        ["name"]=>
        string(6) "bbbbbb"
        ["next"]=>
        object(node)#7 (3) {
          ["id"]=>
          int(3)
          ["name"]=>
          string(6) "cccccc"
          ["next"]=>
          object(node)#6 (3) {
            ["id"]=>
            int(4)
            ["name"]=>
            string(6) "dddddd"
            ["next"]=>
            object(node)#3 (3) {
              ["id"]=>
              int(5)
              ["name"]=>
              string(6) "eeeeee"
              ["next"]=>
              object(node)#5 (3) {
                ["id"]=>
                int(6)
                ["name"]=>
                string(6) "ffffff"
                ["next"]=>
                NULL
              }
            }
          }
        }
      }
    }
  }
}

PHP理解单链表应用

//链表节点 
class node { 
public $id; //节点id 
public $name; //节点名称 
public $next; //下一节点 
public function __construct($id, $name) { 
$this->id = $id; 
$this->name = $name; 
$this->next = null; 
} 
} 
//单链表 
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 . "的节点！\n\r"; 
} 
} 
//获取链表 
public function getLinkList() { 
$current = $this->header; 
if ($current->next == null) { 
echo ("链表为空!"); 
return; 
} 
while ( $current->next != null ) { 
echo 'id:' . $current->next->id . '   name:' . $current->next->name . "\n\r"; 
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, 'eeeeee' ) ); 
$lists->addLink ( new node ( 1, 'aaaaaa' ) ); 
$lists->addLink ( new node ( 6, 'ffffff' ) ); 
$lists->addLink ( new node ( 4, 'dddddd' ) ); 
$lists->addLink ( new node ( 3, 'cccccc' ) ); 
$lists->addLink ( new node ( 2, 'bbbbbb' ) ); 
echo "\n\r-----------PHP数组--------------\n\r"; 
var_dump($lists);
echo "\n\r-----------节点列表--------------\n\r"; 
$lists->getLinkList (); 
echo "\n\r-----------删除节点--------------\n\r"; 
$lists->delLink ( 5 ); 
$lists->getLinkList (); 
echo "\n\r-----------更新节点名称--------------\n\r"; 
$lists->updateLink ( 3, "222222" ); 
$lists->getLinkList (); 
echo "\n\r-----------获取节点名称--------------\n\r"; 
echo $lists->getLinkNameById ( 5 ); 
echo "\n\r-----------获取链表长度--------------\n\r"; 
echo $lists->getLinkLength (); 

一句话

单链结构即查找数据是依据指针移动实现