【数据结构】链表和数组的区别

不同点：

• 链表是链式的存储结构；数组是顺序的存储结构。
• 链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。
• 链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难。
• 数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。
• 在内存中，数组是一块连续的区域，需要预留空间。
• 在数组起始位置处，插入数据和删除数据效率低。插入数据时，待插入位置的元素和他后面的所有元素都需要向后搬移；删除数据时，待删除位置后面的所有元素都需要向前搬移。
• 数组随机访问效率很高，时间复杂度可以达到O(1)
• 数组开辟的空间，在不够使用的时候需要进行扩容；扩容的话，就涉及到需要

相同点：

• 两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构