链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链表。
链表分为单链表、双链表、循环链表。
一、单链表
插入：链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点(前驱)，使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点（见下图）。
由上图可知，B、C之间插入D，三者之间的关系为
current为插入节点的前驱节点current->next = new // B节点指向新节点Dnew->next = current->next // 新节点D指向B的后继节点C
删除：从链表中删除一个元素，将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null，元素就删除成功了（见下图）。
由上图可知，A、C之间删除B，三者之间的关系为
current为要删除节点的前驱节点current->next = current->next->next // A节点指向C节点
具体代码如下：
1 data = $data; 9 $this->next = NULL; 10 } 11 } 12 // 单链表类 13 class SingleLinkedList { 14 private $header; // 头节点 15 16 function __construct($data) { 17 $this->header = new Node($data); 18 } 19 // 查找节点 20 public function find($item) { 21 $current = $this->header; 22 while ($current->data != $item) { 23 $current = $current->next; 24 } 25 return $current; 26 } 27 // （在节点后）插入新节点 28 public function insert($item, $new) { 29 $newNode = new Node($new); 30 $current = $this->find($item); 31 $newNode->next = $current->next; 32 $current->next = $newNode; 33 return true; 34 } 35 36 // 更新节点 37 public function update($old, $new) { 38 $current = $this->header; 39 if ($current->next == null) { 40 echo "链表为空！"; 41 return; 42 } 43 while ($current->next != null) { 44 if ($current->data == $old) { 45 break; 46 } 47 $current = $current->next; 48 } 49 return $current->data = $new; 50 } 51 52 // 查找待删除节点的前一个节点 53 public function findPrevious($item) { 54 $current = $this->header; 55 while ($current->next != null && $current->next->data != $item) { 56 $current = $current->next; 57 } 58 return $current; 59 } 60 61 // 从链表中删除一个节点 62 public function delete($item) { 63 $previous = $this->findPrevious($item); 64 if ($previous->next != null) { 65 $previous->next = $previous->next->next; 66 } 67 } 68 69 // findPrevious和delete的整合 70 public function remove($item) { 71 $current = $this->header; 72 while ($current->next != null && $current->next->data != $item) { 73 $current = $current->next; 74 } 75 if ($current->next != null) { 76 $current->next = $current->next->next; 77 } 78 } 79 80 // 清空链表 81 public function clear() { 82 $this->header = null; 83 } 84 85 // 显示链表中的元素 86 public function display() { 87 $current = $this->header; 88 if ($current->next == null) { 89 echo "链表为空！"; 90 return; 91 } 92 while ($current->next != null) { 93 echo $current->next->data . " "; 94 $current = $current->next; 95 } 96 } 97 } 98 99 $linkedList = new SingleLinkedList('header');100 $linkedList->insert('header', 'China');101 $linkedList->insert('China', 'USA');102 $linkedList->insert('USA','England');103 $linkedList->insert('England','Australia');104 echo '链表为：';105 $linkedList->display();106 echo "";107 echo '-----删除节点USA-----';108 echo "";109 $linkedList->delete('USA');110 echo '链表为：';111 $linkedList->display();112 echo "";113 echo '-----更新节点England为Japan-----';114 echo "";115 $linkedList->update('England', 'Japan');116 echo '链表为：';117 $linkedList->display();118 //echo "";119 //echo "-----清空链表-----";120 //echo "";121 //$linkedList->clear();122 //$linkedList->display();123 124 // 输出：125 链表为：China USA England Australia 126 -----删除节点USA-----127 链表为：China England Australia 128 -----更新节点England为Japan-----129 链表为：China Japan Australia 130 131 PHP实现单链表
二、双链表
单链表从链表的头节点遍历到尾节点很简单，但从后向前遍历就没那么简单了。它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
插入：插入一个节点时，需要指出该节点正确的前驱和后继。
修改待插入节点的 前驱节点的next属性，使其指向新加入的节点，而新插入的节点的next属性则指向原来前驱指向的节点，同时将原来前驱指向的节点的previous属性指向新节点，而新加入节点的previous属性指向它前驱节点（见下图）。
由上图可知，B、C之间插入D，三者之间的关系为
current为插入节点的前驱节点current->next = new // B的next属性指向新节点Dnew->next = current->next // 新节点D的next属性指向B的后继节点Ccurrent->next->previous = new // B的后继节点C的previous属性指向新节点D（原先是C的previous属性指向B）
删除：双向链表的删除操作比单向链表的效率更高，因为不需要再查找前驱节点了。
首先需要在链表中找出存储待删除数据的节点，然后设置该节点前驱的 next 属性，使其指向待删除节点的后继;设置该节点后继的 previous 属性，使其指向待删除节点的前驱。
由上图可知，B、C之间删除D，三者之间的关系为
current为要删除的节点current->previous->next = current->next // B的前驱节点A的next属性指向B的后继节点Ccurrent->next->previous = current->previous // B的后继节点C的previous属性指向B的前驱节点Acurrent->previous = null // B的previous属性指向nullcurrent->next = null // B的next属性指向null
具体代码如下：
1 data = $data;10 $this->previous = NULL;11 $this->next = NULL;12 }13 }14 // 双链表类15 class DoubleLinkedList {16 private $header; // 头节点17 18 function __construct($data) {19 $this->header = new Node($data);20 }21 // 查找节点22 public function find($item) {23 $current = $this->header;24 while ($current->data != $item) {25 $current = $current->next;26 }27 return $current;28 }29 // 查找链表最后一个节点30 public function findLast() {31 $current = $this->header;32 while ($current->next != null) {33 $current = $current->next;34 }35 return $current;36 }37 //（在节点后）插入新节点38 public function insert($item, $new) {39 $newNode = new Node($new);40 $current = $this->find($item);41 $newNode->next = $current->next;42 $newNode->previous = $current;43 $current->next = $newNode;44 return true;45 }46 // 从链表中删除一个节点47 public function delete($item) {48 $current = $this->find($item);49 if ($current->next != null) {50 $current->previous->next = $current->next;51 $current->next->previous = $current->previous;52 $current->next = null;53 $current->previous = null;54 return true;55 }56 }57 // 显示链表中的元素58 public function display() {59 $current = $this->header;60 if ($current->next == null) {61 echo "链表为空！";62 return;63 }64 while ($current->next != null) {65 echo $current->next->data . " ";66 $current = $current->next;67 }68 }69 // 反序显示双向链表中的元素70 public function dispReverse() {71 $current = $this->findLast();72 while ($current->previous != null) {73 echo $current->data . " ";74 $current = $current->previous;75 }76 }77 }78 79 // 测试80 $linkedList = new DoubleLinkedList('header');81 $linkedList->insert('header', 'China');82 $linkedList->insert('China', 'USA');83 $linkedList->insert('USA','England');84 $linkedList->insert('England','Australia');85 echo '链表为：';86 $linkedList->display();87 echo "";88 echo '-----删除节点USA-----';89 echo "";90 $linkedList->delete('USA');91 echo '链表为：';92 $linkedList->display();93 94 // 输出：95 链表为：China USA England Australia96 -----删除节点USA-----97 链表为：China England Australia 98 99 PHP实现双链表
三、循环链表
循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即:head.next = head，这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。换句话说，链表的尾节点指向头节点，形成了一个循环链表。
在循环链表中，涉及遍历的操作，其终止条件是判断它们是否等于头结点，而不是像单链表那样判别p或p->next是否为空。
插入：如果不是在链表尾端插入，则与单链表相似，将待插入节点的前驱节点指向新加入的节点，而新加入的节点指向原来前驱指向的节点；如果是在尾端插入，则待插入节点的前驱节点指向新加入的节点，而新加入的节点指向头节点（见下图）。
由上图可知，插入节点D，B、C、D三者之间的关系为
current为插入节点的前驱节点// 中间current->next = new // B节点指向新节点Dnew->next = current->next // 新节点D指向B的后继节点C// 尾端current->next = new // C节点指向新节点Dnew->next = header // 新节点D指向头节点Header
删除：如果删除的是中间元素，则与单链表操作相同，将待删除节点的前驱节点指向待删除节点的后继节点；如果删除的是尾端元素，则将待删除节点的前驱节点指向头节点。
由上图可知，删除节点时，B、C、D三者之间的关系为
current为要删除节点的前驱节点// 中间current->next = current->next->next // A节点指向C节点// 尾端current->next = header // B节点指向头节点Header
具体代码如下：
1 data = $data;10 $this->next = NULL;11 }12 }13 // 循环链表类14 class CircularLinkedList {15 private $header; // 头节点16 17 function __construct($data) {18 $this->header = new Node($data);19 $this->header->next = $this->header;20 }21 // 查找节点22 public function find($item) {23 $current = $this->header;24 while ($current->data != $item) {25 $current = $current->next;26 }27 return $current;28 }29 // 插入新节点30 public function insert($item, $new) {31 $newNode = new Node($new);32 $current = $this->find($item);33 if ($current->next != $this->header) { // 链表中间34 $current->next = $newNode;35 $newNode->next = $current->next;36 } else { // 链表尾端37 $current->next = $newNode;38 $newNode->next = $this->header;39 }40 return true;41 }42 // 删除节点43 public function delete($item) {44 $current = $this->header;45 while ($current->next != null && $current->next->data != $item) {46 $current = $current->next;47 }48 if ($current->next != $this->header) { // 链表中间49 $current->next = $current->next->next;50 } else { // 链表尾端51 $current->next = $this->header;52 }53 }54 // 显示链表中的元素55 public function display() {56 $current = $this->header;57 while ($current->next != $this->header) {58 echo $current->next->data . " ";59 $current = $current->next;60 }61 }62 }63 64 // 测试65 $linkedList = new CircularLinkedList('header');66 $linkedList->insert('header', 'China');67 $linkedList->insert('China', 'USA');68 $linkedList->insert('USA', 'England');69 $linkedList->insert('England', 'Australia');70 echo '链表为：';71 $linkedList->display();72 echo "";73 echo '-----删除节点USA-----';74 echo "";75 $linkedList->delete('USA');76 echo '链表为：';77 $linkedList->display();78 // 输出：79 链表为：China USA England Australia80 -----删除节点USA-----81 链表为：China England Australia 82 83 PHP实现循环链表
注：循环链表还可以分为单循环链表和双循环链表，这里只实现了单循环链表。