什么是链表

链表(Linked List)是一种常见的线性结构。它不需要一块连续的内存空间，通过指针即可将一组零散的内存块串联起来。将那种碎片内存进行合理的利用，解决空间的问题。

我们把内存块存为链表的节点，为了将所有的节点串起来，每个链表的节点除了存储数据之外，还需要记录链表的下一个节点的地址，这个记录下个节点地址的指针我们叫做后驱指针。

搜索链表需要O(N)的时间复杂度，这点和数组类似，但是链表不能像数组一样，通过索引的方式以O(1)的时间读取第n个数。

链表的优势在于能够以较高的效率在任意位置插入或者删除一个节点。

链表是线性表的一种，所谓的线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。而链表不是用顺序实现的，用指针实现，在内存中不连续。链表有很多种不同的类型：单向链表、双向链表及循环链表。

链表类别

单向链表

每个节点有一个next指针指向后一个节点，还有一个成员变量用于存储数值。

单向链表中有两个节点比较特殊，分别是头结点和尾节点。

头结点用来记录链表的基地址，知道头结点我们就可以遍历得到整条链表。尾结点的特殊在于指针指向的是一个空指针NULL。
链表的php实现 - 图1

双向链表

双向链表支持两个方向，每个节点不只有一个后驱指针next指向后面的节点，还有一个前驱指针prev指向前面的节点。
链表的php实现 - 图2

循环链表

循环链表是一种特殊的单链表，与单链表不同的是尾节点不指向空地址，指向链表的头结点。

优点是从链尾到链头比较方便，当要处理的数据具有环形结构特点是，非常适合用循环链表来处理。

链表的php实现 - 图3

优缺点

优点：动态扩容，不需要占用过多的内存

缺点：不能随机访问，如果要访问一个元素的话，不能根据索引访问，只能从头开始遍历，找到对应的元素O(n)

代码实现

单向链表

  1. <?php
  2. /**
  3.  * 定义节点类，创建节点
  4.  * Class Node
  5.  */
  6. class ListNode
  7. {
  8.     public $data;   // 节点数据
  9.     public $next;   // 下一节点
  11.     public function __construct($data)
  12.     {
  13.         $this->data = $data;
  14.     }
  15. }
  17. /**
  18.  * 单链表类
  19.  * Class SingleLinkedList
  20.  */
  21. class SingleLinkedList
  22. {
  23.     private $head = null;
  24.     private $length = 0;
  25.     private $currentNode;
  26.     private $currentPosition;
  28.     /**
  29.      * 插入一个节点
  30.      * @param string|null $data
  31.      * @return bool
  32.      * complexity O(n)
  33.      */
  34.     public function insert(string $data = null)
  35.     {
  36.         $newNode = new ListNode($data);
  38.         if ($this->head === null) {
  39.             $this->head = &$newNode;
  40.         } else {
  41.             $currentNode = $this->head;
  42.             while ($currentNode->next !== null) {
  43.                 $currentNode = $currentNode->next;
  44.             }
  46.             $currentNode->next = $newNode;
  47.         }
  49.         $this->length++;
  50.         return true;
  51.     }
  53.     /**
  54.      * 在特定节点前插入
  55.      * @param string $data
  56.      * @param string $query
  57.      * complexity O(n)
  58.      */
  59.     public function insertBefore(string $data, string $query)
  60.     {
  61.         $newNode = new ListNode($data);
  63.         if ($this->head) {
  64.             $previous = null;
  65.             $currentNode = $this->head;
  66.             while ($currentNode !== null) {
  67.                 if ($currentNode->data === $query) {
  68.                     $newNode->next = $currentNode;
  69.                     if (empty($previous)) {
  70.                         $newNode->next = $currentNode;
  71.                         $this->head = $newNode;
  72.                     } else {
  73.                         $previous->next = $newNode;
  74.                     }
  75.                     $this->length++;
  76.                     break;
  77.                 }
  79.                 $previous = $currentNode;
  80.                 $currentNode = $currentNode->next;
  81.             }
  82.         }
  83.     }
  85.     /**
  86.      * 在特定节点后插入
  87.      * @param string|null $data
  88.      * @param string|null $query
  89.      * complexity O(n)
  90.      */
  91.     public function insertAfter(string $data = null, string $query = null)
  92.     {
  93.         $newNode = new ListNode($data);
  95.         if ($this->head) {
  96.             $nextNode = null;
  97.             $currentNode = $this->head;
  99.             while ($currentNode !== null) {
  100.                 if ($currentNode->data === $query) {
  102.                     if ($nextNode !== null) {
  103.                         $newNode->next = $nextNode;
  104.                         $currentNode->next = $newNode;
  105.                         $this->length++;
  106.                         break;
  107.                     } else {
  108.                         $currentNode->next = $newNode;
  109.                         $currentNode->next = $newNode;
  110.                         $this->length++;
  111.                         break;
  112.                     }
  114.                 }
  116.                 $currentNode = $currentNode->next;
  117.                 $nextNode = $currentNode->next;
  118.             }
  119.         }
  120.     }
  122.     /**
  123.      * 在最前方插入节点
  124.      * @param string $data
  125.      * complexity O(1)
  126.      */
  127.     public function insertAtFirst(string $data)
  128.     {
  129.         $newNode = new ListNode($data);
  131.         if ($this->head === null) {
  132.             $this->head = &$newNode;
  133.         } else {
  134.             $currentFirstNode = $this->head;
  135.             $newNode->next = $currentFirstNode;
  136.             $this->head = &$newNode;
  137.         }
  139.         $this->length++;
  140.     }
  142.     /**
  143.      * 搜索一个节点
  144.      * @param string $data
  145.      * @return bool|ListNode
  146.      * complexity O(n)
  147.      */
  148.     public function search(string $data)
  149.     {
  150.         if ($this->length > 0) {
  151.             $currentNode = $this->head;
  152.             while ($currentNode !== null) {
  153.                 if ($currentNode->data === $data) {
  154.                     return $currentNode;
  155.                 }
  157.                 $currentNode = $currentNode->next;
  158.             }
  159.         }
  161.         return false;
  162.     }
  164.     /**
  165.      * 删除最前面的节点
  166.      * @return bool
  167.      * complexity O(1)
  168.      */
  169.     public function deleteFirst()
  170.     {
  171.         if ($this->head !== null) {
  172.             if ($this->head->next !== null) {
  173.                 $this->head = $this->head->next;
  174.             } else {
  175.                 $this->head = null;
  176.             }
  178.             $this->length--;
  180.             return true;
  181.         }
  183.         return false;
  184.     }
  186.     /**
  187.      * 删除最后面的节点
  188.      * @return bool
  189.      * complexity O(1)
  190.      */
  191.     public function deleteLast()
  192.     {
  193.         if ($this->head !== null) {
  194.             $currentNode = $this->head;
  196.             if ($currentNode->next !== null) {
  197.                 $previousNode = null;
  198.                 while ($currentNode->next !== null) {
  199.                     $previousNode = $currentNode;
  200.                     $currentNode = $currentNode->next;
  201.                 }
  203.                 $previousNode->next = null;
  204.             } else {
  205.                 $this->head = null;
  206.             }
  208.             $this->length--;
  209.             return true;
  210.         }
  212.         return false;
  213.     }
  215.     /**
  216.      * 删除特定节点
  217.      * @param string $query
  218.      * @return bool
  219.      * complexity O(n)
  220.      */
  221.     public function delete(string $query)
  222.     {
  223.         if ($this->head !== null) {
  224.             $currentNode = $this->head;
  225.             $previous = null;
  226.             while ($currentNode !== null) {
  228.                 if ($currentNode->data === $query) {
  229.                     if ($currentNode->next === null) {
  230.                         $previous->next = null;
  231.                     } else {
  232.                         $previous->next = $currentNode->next;
  233.                     }
  235.                     $this->length--;
  236.                     return true;
  237.                 }
  239.                 $previous = $currentNode;
  240.                 $currentNode = $currentNode->next;
  241.             }
  243.         }
  245.         return false;
  246.     }
  248.     /**
  249.      *反转链表
  250.      * complexity O(n)
  251.      */
  252.     public function reverse()
  253.     {
  254.         if ($this->head !== null) {
  255.             if ($this->head->next !== null) {
  256.                 $reveredList = null;
  257.                 $next = null;
  258.                 $currentNode = $this->head;
  260.                 while ($currentNode !== null) {
  261.                     $next = $currentNode->next;
  262.                     $currentNode->next = $reveredList;
  263.                     $reveredList = $currentNode;
  264.                     $currentNode = $next;
  265.                 }
  267.                 $this->head = $reveredList;
  268.             }
  269.         }
  271.     }
  273.     /**
  274.      * 返回特定位置的节点
  275.      * @param int $n
  276.      * @return null
  277.      * complexity O(n)
  278.      */
  279.     public function getNthNode(int $n = 0)
  280.     {
  281.         $count = 0;
  282.         if ($this->head !== null && $n <= $this->length) {
  283.             $currentNode = $this->head;
  285.             while ($currentNode !== null) {
  286.                 if ($count === $n) {
  287.                     return $currentNode;
  288.                 }
  290.                 $count++;
  291.                 $currentNode = $currentNode->next;
  292.             }
  294.         }
  295.         return false;
  296.     }
  298.     public function current()
  299.     {
  300.         return $this->currentNode->data;
  301.     }
  303.     public function next()
  304.     {
  305.         $this->currentPosition++;
  306.         $this->currentNode = $this->currentNode->next;
  307.     }
  309.     public function rewind()
  310.     {
  311.         $this->currentPosition = 0;
  312.         $this->currentNode = $this->head;
  313.     }
  315.     public function key()
  316.     {
  317.         return $this->currentPosition;
  318.     }
  320.     public function valid()
  321.     {
  322.         return $this->currentNode !== NULL;
  323.     }
  325.     public function getSize()
  326.     {
  327.         return $this->length;
  328.     }
  330.     public function display()
  331.     {
  332.         echo 'LinkList length: ' . $this->length . PHP_EOL;
  333.         $currentNode = $this->head;
  335.         while ($currentNode !== null) {
  336.             echo $currentNode->data . PHP_EOL;
  337.             $currentNode = $currentNode->next;
  338.         }
  339.     }
  341. }
  343. $linkedList = new SingleLinkedList();
  344. $linkedList->insert('China');
  345. $linkedList->insert('USA');
  346. $linkedList->insert('England');
  347. $linkedList->insert('Australia');
  348. echo '链表为：';
  349. $linkedList->display();
  350. $linkedList->reverse();
  351. echo PHP_EOL;
  352. echo '链表为：';
  353. $linkedList->display();