数据结构与算法之美 | 学习笔记03 ——链表（上）

一、链表

跟数组需要一块连续的存储空间不同，链表通过“指针”将一组零散的内存块串联起来使用。
内存块称为链表的“结点”，每个链表的结点除了存储数据外，还存储下一个节点地址，即后继指针NEXT。

1. 单链表

如上图，其中，头结点记录链表的基地址，尾结点指向空地址NULL。
对于链表的插入和删除操作，只需考虑相邻结点的指针改变，对应时间复杂度为$O(1)$O(1)（单、双向链表不同，后边会讲到）；对于链表的查找操作，则需要依次遍历，对应时间复杂度为$O(n)$O(n)。

2. 循环链表

循环链表的尾结点指向链表的头结点。当处理的数据有环形结构特点时适合使用。

3. 双向链表

双向链表每个结点需要额外两个空间存储后继结点和前驱结点的地址，因此占用更多内存空间。
插入、删除给定指针指向的结点时：对于单向链表需要遍历查找前驱结点，p->next=q，时间复杂度为$O(n)$O(n)；对于双向链表已知前驱结点，时间复杂度为$O(1)$O(1)。
实际开发中，例如Java中LinkedHashMap就用到了双向链表的数据结构。

二、数组与链表

数组：

• 因CPU缓存机制，每次读取一块数据，预读数组中的数据，所以访问效率更高；
• 当声明的数组过大时，可能会出现“内存不足（out of memory）”的情况；
• 当声明的数组过小时，可能会出现不够用的情况，这是扩容需要将原数组拷贝至新地址，很耗费时间。

链表：

• 每个结点会消耗额外的存储空间来存储指针，所以内存消耗会翻倍；
• 当对链表进行频繁的插入、删除操作时，导致频繁的内存申请和释放，容易造成内存碎片（Java里会导致频繁Garbage Collection（垃圾回收））。