实现

• 数组 数组初始化，是在内存上申请了一整块连续的内存，一般都是预留一些空的内存以便于数组的增大，但也不会很多，因为预留很多又用不到就会产生浪费。如果数组增大到比分配空间更大，那么就会复制整个数组到一个新的内存块。
• 链表 链表的每个节点都包含头部和主体，头部包含指向下一个节点的地址，主体存储信息。因此在内存上是可以不用连续的。

性能

查询

• 数组 因为数组的内存是连续的，所以是支持随机读取的，也就是说，查询一个节点不用从头遍历到底，可以根据数组的初始地址和目标的index直接计算到目标的内存地址。
• 链表 链表因为不能直接拿到目标的内存地址，所以就需要从第一个节点开始遍历，直到找到目标值。

增删

• 数组 数组在增删一个节点后，为了保证顺序以及不浪费内存，增删节点位置之后的所有节点就需要往后/前（增/删）挪。
• 链表 链表的增删节点，只需要保证前后节点的header链接正确即可。

改

在这个层次上，改不涉及到内存的变化。基本上对性能影响不大。

结论

在查询的时候，数组因为可以随机查询，性能是好于链表的，但是如果增删操作比较多的话，那么链表的优势就体现出来了。