数据结构-链表

链表是日常工作中十分常见且常用的一种数据结构，那么什么是链表，链表有那些结构呢？

什么是链表

链表是一种线性的数据结构，和数组不同的是，链表不需要一块连续的内存空间，它通过指针将一组零散的内存空间串联起来。

链表有哪些结构

链表的结构非常多，常用的有单链表、双向链表和循环链表。

1. 单链表是指每个node都只维护指向下一个node的next指针
2. 双向链表是指每个node都维护着指向下一个节点的next指针和指向前一节点的prev指针
3. 循环链表是一种特殊的单链表，其尾节点会指向链表的头节点（普通的单链表尾节点是指向null的）

链表操作时间复杂度的常见误区

常听见的说法是链表的随机访问时间复杂度是O(n)，删除或插入操作时间复杂度是O(1)，但实际使用却不是每次都是这样的。
对删除动作，删除动作无外乎两种情况

1. 删除节点中某个给定值的节点
2. 删除给定引用的节点

针对第一种情况，其完成删除动作的时间复杂度其实是O(n)，因为首先你需要遍历查找出给定值的节点（时间复杂度为O(n)），然后删除该节点，并将其前一个节点的next指针指向被删除节点的next节点(时间复杂度为O(1))，所以整体的时间复杂是O(n)。

针对第二种情况，单链表和双向链表的表现不同，对单链表而言，给定节点引用去删除的时候，还是需要遍历找到该节点的前一个节点，然后才能完成删除动作，所以时间复杂度依然是O(n)。但是对于双向链表而言，给定节点引用去删除时，可以直接通过prev指针获取前一个节点，然后完成删除动作，其时间复杂度为O(1)。

LeetCode练习题

141: 环形链表
142: 环形链表2
203: 移除链表元素
206: 反转链表