钛节点

数据结构之线性表（链式存储表）

发表@2018-09-13 09:15:21

更新@2023-01-21 22:47:40

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

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

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

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

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

单链存储表比顺序存储表的好处上文已经指出过了，下面定义几个单链表的几个关键操作：
- 获取单链表长度
- 从单链表中删除某个结点
- 向单链表中添加一个结点
- 清空整个单链表
- 获取某个位置上的结点

在php代码演示中，我们使用两个class来完成单链表的一些操作。第一个是Node类，这个类就是结点的数据结构抽象。第二个就是Linked_sq类，这个类就是单链表以及单链表的操作。
```php
<?php
// 将结点抽象成一个node class，具备data和next两个属性
class Node{
  public $data = null;
  public $next = null;
  public function __construct( $data = null ){
    $this->data = $data;
  }
}
// 单链表的存储
class Linked_sq{
  private $head = null;
  public function __construct(){
    // 添加一个头结点
    $this->head = new Node(); 
  }
  /*
   * @desc : 获取单链表长度
   */
  public function get_length(){
    // 注意 头结点 不算在单链表的长度内
    $length = 0;
    $head = $this->head;
    while( $head->next ){
      $head = $head->next; 
      $length++;
    }
    return $length;
  }
  /*
   * @desc : 添加一个结点
   * @param : index
   * @param : item 
   */
  public function add_item( $index, $item ){
    $length = $this->get_length(); 
    if( $index < 0 || $index > $length ){
      return false;
    }
    // 获取头结点
    $head = $this->head;
    for( $i = 0; $i < $index; $i++){
      $head = $head->next;
    }
    // 初始化一个新结点
    $node = new Node( $item ); 
    $node->next = $head->next;
    $head->next = $node; 
    return true;
  }
  /*
   * @desc : 删除一个结点
   * @param : index
   */
  public function delete_item( $index ){
    $length = $this->get_length();
    if( $index < 0 || $index > $length ){
      return null;
    } 
    $head = $this->head; 
    // 这里循环的终止条件一定要想明白了，我要删除index位置上的结点，从0开始寻找一直到index这个结点，但是
    // 当循环终止的时候，被选中的结点是 index - 1 位置上的结点
    for( $i = 0; $i < $index; $i++ ){
      $head = $head->next; 
    }
    // 这个才是要被删除的结点
    $delete_node = $head->next;  
    $value = $delete_node->data;
    // 修改指针指向
    $head->next = $head->next->next;
    // 删除结点
    unset( $delete_node );
    return $value;
  }
  /*
   * @desc : 查找某个位置上的数值 
   * @param : index
   */
  public function get_item_by_index( $index ){
    $length = $this->get_length(); 
    if( $index < 0 || $index > $length ){
      return null;
    }
    $head = $this->head;
    // 注意这里终止条件，这里获取到的是 index-1 位置上的结点
    for( $i = 0; $i < $index; $i++ ){
      $head = $head->next;
    } 
    return $head->next->data;
  }
  /*
   * @desc : 清空整个单链表
   */
  public function truncate(){
    // 第一个结点,就是头结点
    $head = $this->head;
    while( $head->next ){
      $temp = $head->next;
      unset( $head );
      $head = $temp;
    }
    return true;
  }

}

$link = new Linked_sq();
echo '单链表初始长度为：'.$link->get_length().PHP_EOL;
// 添加一个结点
$link->add_item( 0, 9 );
echo '单链表长度为：'.$link->get_length().PHP_EOL;
$link->add_item( 1, 2 );
$link->add_item( 2, 12 );
$link->add_item( 3, 5 );
echo '单链表长度为：'.$link->get_length().PHP_EOL;
// 获取第2个位置上的数字
echo "第2个位置上的数字：".$link->get_item_by_index( 2 ).PHP_EOL;
// 删除第1个位置上的数字
echo "删除了".$link->delete_item( 1 ).PHP_EOL;
echo '单链表长度为：'.$link->get_length().PHP_EOL;
echo "第2个位置上的数字：".$link->get_item_by_index( 2 ).PHP_EOL;
```

晚安，祝大家好梦。

----