数据结构之链表
什么是链表
同数组一样，链表是一种线性数据结构，由一组相连的节点组成。在日常工作中，虽然我们直接使用链表的机会较少，但是间接使用的机会还是很多的，比如HashMap的底层数据结构中就有链表，而且这个基本上是面试必问的，还有Redis的list也是使用链表实现的，掌握链表对于我们日常编码过程中选择合适的数据结构，提高代码质量大有裨益。
链表的分类
单向链表
在单向链表中，一个节点包含两个部分，一个存储数据，另一个存储指向下个节点的指针。
双向链表
所谓双向链表就是在单向链表的基础上增加了指向前一个节点的指针，所以双向链表不仅支持向后查找，也支持向前查找。
循环链表
循环链表指的链表的最后一个节点指针指向链表第一个节点，首尾连接，形成一个循环结构。上图为双向循环链表。
链表与数组的区别
存储方式不同
数组是在内存中是连续存储的，而链表则可以分散存储
查找和增删效率存在差异
这是由于数据的存储方式决定的，连续存储使得数组的查询效率较高，可以使用索引实现高效的数据访问，而链表只能一个接一个节点的查找，所以链表的查询效率偏低，但是其分散的存储方式使得其新增和删除的效率很高，只需要改变指针的指向即可，数组的增删则比较重量级。
链表的正确使用方式
在一些增删比较频繁的场景中，比较适合使用链表，以HashMap为例，为解决Hash冲突问题，HashMap引入了链表来连接Entry，在出现Hash碰撞时，只需要向链表中增加一个节点即可，当然，上面也提到过，链表的查询效率偏低，所以后来HashMap在链表长度大于8时会转变为红黑树以提高查询的效率。