一、前言

• 最近在学习数据结构时看到了线性表这一块内容，在LeetCode刷题时叶遇到不少链表的题目，于是便试着用php实现链表
• 结合书本知识，通过Google，百度等，最后写了这篇文章
• 有关链表的题：

合并两个有序链表
两数相加

• 参考文章：https://www.cnblogs.com/sunshineliulu/p/7717301.html

二、概念

链表是线性表的链式表现和实现，链表也是一组节点组成的集合，每个节点都使用一个对象的引用指向它的后继。链表又分为单链表，双链表和循环链表

三、单链表

1.描述

每个节点都有next指向下一个节点

2.单链表的结构

如下图所示：

3.插入节点操作

链表中插入一个节点的效率很高，向链表中插入一个节点，需要修改它前面的节点(前驱)，使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点，如下图所示：

B、C之间插入D，三者之间的关系：

#current为插入节点的前驱节点
current->next = new              // B节点指向新节点D
new->next = current->next        // 新节点D指向B的后继节点C

4.删除节点操作

从链表中删除一个元素，将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null，元素就删除成功了（见下图）

A、C之间删除B，三者之间的关系：

#current为要删除节点的前驱节点
current->next = current->next->next    // A节点指向C节点

四、双链表

1.描述

双链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱
从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点

2.双链表结构

3.双链表插入操作

插入一个节点时，需要指出该节点正确的前驱和后继
修改待插入节点的前驱节点的next属性，使其指向新加入的节点
而新插入的节点的next属性则指向原来前驱指向的节点，同时将原来前驱指向的节点的previous属性指向新节点，而新加入节点的previous属性指向它前驱节点
结合下图理解上面这段话

B、C之间插入D，三者之间的关系：

#current为插入节点的前驱节点
current->next = new              // B的next属性指向新节点D
new->next = current->next        // 新节点D的next属性指向B的后继节点C
current->next->previous = new    // B的后继节点C的previous属性指向新节点D（原先是C的previous属性指向B）

4.双链表删除操作

双向链表的删除操作比单向链表的效率更高，因为不需要再查找前驱节点了。
首先需要在链表中找出存储待删除数据的节点，然后设置该节点前驱的next 属性，使其指向待删除节点的后继;设置该节点后继的 previous属性，使其指向待删除节点的前驱

B、C之间删除D，三者之间的关系：

current为要删除的节点
current->previous->next = current->next        // B的前驱节点A的next属性指向B的后继节点C
current->next->previous = current->previous    // B的后继节点C的previous属性指向B的前驱节点A
current->previous = null                       // B的previous属性指向null
current->next = null                           // B的next属性指向null

五、循环链表

1.描述

循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即:head.next
= head，这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。换句话说，链表的尾节点指向头节点，形成了一个循环链表
在循环链表中，涉及遍历的操作，其终止条件是判断它们是否等于头结点，而不是像单链表那样判别p或p->next是否为空

2.循环链表结构

3.循环链表插入操作

如果不是在链表尾端插入，则与单链表相似，将待插入节点的前驱节点指向新加入的节点，而新加入的节点指向原来前驱指向的节点；如果是在尾端插入，则待插入节点的前驱节点指向新加入的节点，而新加入的节点指向头节点（见下图）

插入节点D，B、C、D三者之间的关系

current为插入节点的前驱节点
// 中间
current->next = new              // B节点指向新节点D
new->next = current->next        // 新节点D指向B的后继节点C
// 尾端
current->next = new              // C节点指向新节点D
new->next = header               // 新节点D指向头节点Header

4.循环链表删除操作

如果删除的是中间元素，则与单链表操作相同，将待删除节点的前驱节点指向待删除节点的后继节点；如果删除的是尾端元素，则将待删除节点的前驱节点指向头节点

删除节点时，B、C、D三者之间的关系：

current为要删除节点的前驱节点
// 中间
current->next = current->next->next    // A节点指向C节点
// 尾端
current->next = header                 // B节点指向头节点Header