数组和链表对比

数组的特点是在内存中地址是连续的，所以在随机访问一个数组中的地址的时间复杂度是O(1),寻址公式大概是：

	
int a[3] = {1,2,3};

a[i]_address = begin_address + i * data_type_size

int a[3][2] = {{1,2},{6,7},{3,5}};

address = begin_address + ( i * n + j) * data_type_size

数组由于对内存的要求比较苛刻，带来的一个问题就是低效的“插入”和“删除”，在做数据的插入和删除的时候要频繁的进行数据的迁移。对于数组的动态扩容策略的实现可以参考redis的字符串底层实现原理或者java中的arrayList<>.

使用场景注意： 操作的数据不宜过大。

链表的分类：

单链表： 后继指针指next向下一个节点的heac（节点包含头部，数据data和指针next）
双向链表： 后继指针next指向下一个节点的prev (节点包括前驱指针prev,数据data,后继指针next)
循环链表： 尾结点指针指向头节点

链表就是用指针将节点连接起来，它对内存的要求没有数组那么苛刻，所以链表在“插入”和“删除”的动作上的时间复杂度是O(1),但是由于链表内存不是连续的，所以不能随机访问某个元素，在查找的时候时间复杂度是O(n)。

单链表的使用经典案例如：LRU缓存淘汰策略

双向链表：java中的LinkedHashMap实现，双向链表比单链表会占用更多的内存，但是在查找元素的速度上会比单链表性能更高，因为双向链表的每个节点上既有前驱指针，又有后继指针，当我们知道具体某一个node的时候那么它的前驱和后继指针我们就知道了，所以它在查找过程中可以判断是忘前走还是往后走，体现了用空间换时间的设计思想。

链表的另一种使用场景经常会配合散列表使用，配合hashtable使用的目的主要是为了解决链表在查询过程中时间复杂度O(N)的问题。做法是将单链表或者双链表中的节点通过hash函数散列到数组的槽(桶)上，用一个新的指针通过拉链的方式将冲突的节点连接上。这样在查找某一个node的时候，时间复杂度是接近O(1)的。

• 本文作者： 李宏伟
• 本文链接： https://blog.chuangketime.com/2023/03/23/数据结构-数组和链表/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！