✅数组和链表有何区别？

典型回答

从定义上讲：

数组和链表都是数据的集合。

1. 数组中每个元素都是连续的，通过下标进行访问，当我们获取到下标后，就可以随意访问数组中的值

2. 链表中的元素则是不连续的，必须获得链表中某个元素后，才能顺序访问该元素的周围元素，我们没办法随意访问链表中的元素。链表分为单向链表，双向链表，环形链表等

从实现上来讲：

1. 数组可以由一块连续区域的内存实现，其中，内存地址可以作为数组的下标，该地址中的值就是数组中元素的值。因为数组占用的是一块空间，所以数组的大小申请之后就会固定；

2. 链表可以由不连续的内存存储实现，每个元素都会存储下一个元素的地址。（如果是双向链表的话，元素则会还会存储上个元素的地址）。因为链表中存储了元素的地址，所以链表可以在内存足够的情况下随意申请空间

如下图所示：

数组和链表的区别如下所示：

比较项	数组	链表
内存中是否连续	是	否
查询效率	1. 通过下标查是O(1) 2. 通过数值查是O(n)，如果是有序数组则O(logn)	O(n)
占用空间	1. 直接申请空间，当元素个数不确定时，容易浪费	1. 相对数组来说会存储前后指针 2. 大小和元素个数相同
插入/删除	数组需要移动n/2个元素	链表只需要修改指针

知识扩展

什么是双向链表和环形链表

1. 双向链表是指每个元素不仅指向下一个元素，还会指向上一个元素，如下图所示：

2. 环形链表指链表的最后一个元素会指向链表的第一个元素；或者链表的最后一个元素会指向链表中间的某个元素，如下图所示：

相关算法

1. 反转链表：https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
2. 合并两个有序数组：https://leetcode.cn/problems/merge-sorted-array/
3. 判断环形链表：https://leetcode.cn/problems/linked-list-cycle/