链表

链表

定义

通过指针将一组零散的内存快串联起来使用。其中我们将内存块称为链表的结点，下一个结点的地址叫作后继指针next。

种类

单链表

image.png

第一个结点叫头结点，最后一个结点叫尾结点。头结点记录链表的基地址，尾结点指针指向的下一个地址为空地址NULL。

单链表在插入和删除操作的时候，只需要对相邻结点指针的改变，所以时间复杂度为O(1)

image.png

但是单链表在随机访问第K个元素的时候，效率就没有那么高效，因为链表非连续存储，所以不能用寻址公式找到对应地址，二十需要根据指针一个结点一个结点的依次遍历，找到对应结点，所以时间复杂度为O(n)。

循环链表

循环链表是一种特殊的单链表，单链表的尾结点指针指向NULL，而循环链表的尾结点指向链表的头结点。

image.png

和单链表比较，循环链表的优点是从链尾到链头比较方便。当数据是环形结构时，例如约瑟夫问题。

双向链表

与单链表比较，单链表只有一个方向，只有一个后继指针next指向后面的结点。而双向链表他支持两个方向，每个结点不止有一个后继指针还有一个前驱指针指向前面的结点。

image.png

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址，所以相比单链表占用更多的内存空间。但是支持双向遍历，使得链表更加灵活。

双链表支持O(1)时间复杂度的情况下找到前驱结点，所以在某些情况下插入和删除操作比单链表更加简单高效。

双向循环链表

image.png

数组VS链表

插入删除查询时间复杂度比较。

image.png

数组是使用连续的内存空间，可以借助CPU缓存增加访问效率，链表在内存中不是连续的，对CPU缓存不友好。

数组的内存空间是连续的，如果数组太大可能会发生没有足够的内存空间分配给它。如果初始化的比较小后续不够用扩容的时候就需要申请一个更大的空间，将原数组拷贝过去。而链表本身没有限制大小本身支持动态扩容。

链表的内存空间因为有前驱结点和后继结点指针的存储，所以会消耗额外的空间，当对链表进行频繁的插入和删除操作时，会导致内存频繁的申请和释放，容易造成内存碎片，会导致频繁的GC。