下午抽空去面了一家做区块链的公司，算是我朋友的一个公司吧，只不过他是做前端的，流程还是要走走。看起来公司正在极速扩张中，本来我也准备好要手撕TCP协议、基础数据结构算法之类的，但是面试的小孩子反而自己紧张地说话都发抖，一时间让我觉得特别尴尬，一定程度上我还得反过来安慰他。

    比较累，所以单链表可能会稍微水些许，不过主要内容不会拉下，见谅！

    好了，回到正路来，就是采用了链式存储的顺序表（又叫单链表），单链表的组成元素我们可以称之为结点。从逻辑上看，单链表中的结点是一个顺序的数字队伍。从物理存储角度看，这些结点则是分布在连续或者不连续的内存区域中，彼此之间依靠指针来连接。

    上一章节中说过了，少林队 VS 金刚豆腐队的门票采用了网络预约电子发售的方式进行的，这种电子票上需要记录两种信息，一个是观看者本身的个人资料信息，同时还有下一个买到票的人的名字。比如强雄的票上除了有强雄自己的个人数据外，还有下一个买到票的人的名字：酱爆。

    票就相当于是结点，一个结点往往由两部分组成，一部分是数据本身，另一部分就是指向下一个结点的指针。如果A结点往后没有结点了怎么办？不怎么办，把A结点的指向下一个结点的指针赋值为null即可。链表有一个非常重要的概念叫做头指针，一个链表必须拥有一个头指针！为什么呢？因为单链表就是靠头指针来确定的，你可以粗暴地认为没有头指针，你压根就不知道单链表在哪儿。除此之外，还有一个听起来比较朦胧的概念，叫做头结点。头结点并不是第一个结点的意思，这个东西是插在第一个结点和头指针之间的一个结点。头指针指向的是头结点，而头结点的指针区域则指向第一个结点，而头结点到数据区域中则可以存储一些比较自由的数据了，说直白点儿就是你爱存啥就存啥，没人管你。

    单链存储表比顺序存储表的好处上文已经指出过了，下面定义几个单链表的几个关键操作：

    • 获取单链表长度
    • 从单链表中删除某个结点
    • 向单链表中添加一个结点
    • 清空整个单链表
    • 获取某个位置上的结点

    在php代码演示中，我们使用两个class来完成单链表的一些操作。第一个是Node类，这个类就是结点的数据结构抽象。第二个就是Linked_sq类，这个类就是单链表以及单链表的操作。

    1. <?php
    2. // 将结点抽象成一个node class，具备data和next两个属性
    3. class Node{
    4.   public $data = null;
    5.   public $next = null;
    6.   public function __construct( $data = null ){
    7.     $this->data = $data;
    8.   }
    9. }
    10. // 单链表的存储
    11. class Linked_sq{
    12.   private $head = null;
    13.   public function __construct(){
    14.     // 添加一个头结点
    15.     $this->head = new Node(); 
    16.   }
    17.   /*
    18.    * @desc : 获取单链表长度
    19.    */
    20.   public function get_length(){
    21.     // 注意 头结点 不算在单链表的长度内
    22.     $length = 0;
    23.     $head = $this->head;
    24.     while( $head->next ){
    25.       $head = $head->next; 
    26.       $length++;
    27.     }
    28.     return $length;
    29.   }
    30.   /*
    31.    * @desc : 添加一个结点
    32.    * @param : index
    33.    * @param : item 
    34.    */
    35.   public function add_item( $index, $item ){
    36.     $length = $this->get_length(); 
    37.     if( $index < 0 || $index > $length ){
    38.       return false;
    39.     }
    40.     // 获取头结点
    41.     $head = $this->head;
    42.     for( $i = 0; $i < $index; $i++){
    43.       $head = $head->next;
    44.     }
    45.     // 初始化一个新结点
    46.     $node = new Node( $item ); 
    47.     $node->next = $head->next;
    48.     $head->next = $node; 
    49.     return true;
    50.   }
    51.   /*
    52.    * @desc : 删除一个结点
    53.    * @param : index
    54.    */
    55.   public function delete_item( $index ){
    56.     $length = $this->get_length();
    57.     if( $index < 0 || $index > $length ){
    58.       return null;
    59.     } 
    60.     $head = $this->head; 
    61.     // 这里循环的终止条件一定要想明白了，我要删除index位置上的结点，从0开始寻找一直到index这个结点，但是
    62.     // 当循环终止的时候，被选中的结点是 index - 1 位置上的结点
    63.     for( $i = 0; $i < $index; $i++ ){
    64.       $head = $head->next; 
    65.     }
    66.     // 这个才是要被删除的结点
    67.     $delete_node = $head->next;  
    68.     $value = $delete_node->data;
    69.     // 修改指针指向
    70.     $head->next = $head->next->next;
    71.     // 删除结点
    72.     unset( $delete_node );
    73.     return $value;
    74.   }
    75.   /*
    76.    * @desc : 查找某个位置上的数值 
    77.    * @param : index
    78.    */
    79.   public function get_item_by_index( $index ){
    80.     $length = $this->get_length(); 
    81.     if( $index < 0 || $index > $length ){
    82.       return null;
    83.     }
    84.     $head = $this->head;
    85.     // 注意这里终止条件，这里获取到的是 index-1 位置上的结点
    86.     for( $i = 0; $i < $index; $i++ ){
    87.       $head = $head->next;
    88.     } 
    89.     return $head->next->data;
    90.   }
    91.   /*
    92.    * @desc : 清空整个单链表
    93.    */
    94.   public function truncate(){
    95.     // 第一个结点,就是头结点
    96.     $head = $this->head;
    97.     while( $head->next ){
    98.       $temp = $head->next;
    99.       unset( $head->next );
    100.       $head = $temp;
    101.     }
    102.     return true;
    103.   }
    105. }
    107. $link = new Linked_sq();
    108. echo '单链表初始长度为：'.$link->get_length().PHP_EOL;
    109. // 添加一个结点
    110. $link->add_item( 0, 9 );
    111. echo '单链表长度为：'.$link->get_length().PHP_EOL;
    112. $link->add_item( 1, 2 );
    113. $link->add_item( 2, 12 );
    114. $link->add_item( 3, 5 );
    115. echo '单链表长度为：'.$link->get_length().PHP_EOL;
    116. // 获取第2个位置上的数字
    117. echo "第2个位置上的数字：".$link->get_item_by_index( 2 ).PHP_EOL;
    118. // 删除第1个位置上的数字
    119. echo "删除了".$link->delete_item( 1 ).PHP_EOL;
    120. echo '单链表长度为：'.$link->get_length().PHP_EOL;
    121. echo "第2个位置上的数字：".$link->get_item_by_index( 2 ).PHP_EOL;

    晚安，祝大家好梦。