Java-链表（单向、循环、双向）
前言：
什么是链表？链表是一种常见的基础数据结构，是一种线性表，但并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针来做关联，同时链表也分为，单链表、双链表、循环链表。
单链表（单向链表）
单链表由两个部分构成
- DATA域：数据域、用来存储数据元素
- NEXT域：指针域、用来指向下一个节点
链表与数组类似,也可以进行查找、插入、删除、读取等操作,但是由于链表与数组的特性不同,导致不同操作的复杂度也不同
查找方式
从头节点进入,开始比对节点的值,如果不同则通过指针进入下一个节点
重复上面的动作,直到找到相同的值,或者节点的指针指向null
时间复杂度为O(n)
插入或删除方式
链表与数组最大的不同就在于删除、插入的性能优势,由于链表是非连续的内存,所以不用像数组一样在插入、删除操作的时候需要进行大面积的成员位移,比如在a、b节点之间插入一个新节点c,链表只需要做
- a断开指向b的指针，将指针指向c
- c节点将指针指向b，完毕（这才是魅力所在）
插入或删除只需要调整指针即可。
时间复杂度为O(1)
下面看下链表的插入、删除操作
读取方式
链表与数组相比读取性能是有劣势的。数组读取操作性能高效是因为它是一块连续内存，读取通过寻址公式就可以快速定位，链表非连续内存必须通过指针节点一一遍历。
使用场景
- 撤销功能,这种操作最多见于各种文本、图形编辑器中,撤销重做在编辑器场景下属于家常便饭,单向链表由于良好的删除特性在这个场景很适用
- 图片队列上传
- …
双链表（双向链表）
我们看到双向链表多了一个新的指针prev指向节点的前一个节点,当然由于多了一个指针,所以双向链表要更占内存
插入操作
向双链表中插入一个新节点，需要通过调整两次prev指向和两次next指向来完成。如下图所示，X为新节点，将A1的next指向X，将X的next指向A2，将A2的prev指向X，将X的prev指向A1即可。
删除操作
从双链表中删除一个节点，需要通过调整一次prev指向和一次next指向来完成。如下图所示，删除A2节点，将A1的next指向A3，将A3的 prev指向A1即可。
循环链表
环形链表又叫循环链表，本文讲述的是单向环形链表，其与单链表的唯一区别是尾部节点的next不再为空，则是指向了头部节点，这样便形成了一个环。
小结：链表与数组的的不同之处在于数组是一块连续的内存,而链表可以不是连续内存,链表的节点与节点之间通过指针来联系的
- 数组静态分配内存，链表动态分配内存
- 数组在内存中连续，链表不连续
- 数组元素在栈区，链表元素在堆区
- 数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)
- 数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)
