【你问我答】数组和链表的区别是什么？

数组：物理上存储单元有序（比如第一个地址是1001，第二个就是1002），也就是放在一个连续的内存块中。使用前需要提前申请内存空间，大小固定，不准改变。空间从栈申请。 链表：物理存储单元不连续，寻址靠每一个元素的指针链接实现的。（等于每个抽屉里装着数据--数据域，还有写着下一个抽屉的序号的小纸条--指针域）内存空间不需要提前申请，是动态申请的。空间从堆申请。 数组查询用下标，所以很快，o（1），但是插入和删除都比较慢，因为后面的元素都需要调整（尤其是在头部进行插入和删除）。 链表查询要靠指针一个个找下去，相对较慢，o（n），但是插入和删除都比较快，因为不涉及到其他元素（具体见链表插入删除节点）。

逻辑上来说两者都属于线性表。 物理上来说，即在内存两种逻辑结构所对应的物理存储分布，数组占用一块连续的内存区，而链表在内存上是不连续的。因此需要一个东西将各个元素串起来，这个串起来的额外操作是通过一个节点指向下一个节点的指针实现的，即对于链表来说每个节点除了要存储对应的元素（数据域），还需存储指向下一个节点的指针（指针域），因此对于链表来说，存储一个节点，相比于数组所要消耗的资源更多。也正因为这种物理结构的差异，使得两者在访问、增加、删除节点这三种操作上所带来的时间复杂度不同。 数组可以使用下标在O(1)的复杂度下访问元素。链表没有下标的概念，只能通过头节点指针，从每一个节点，依次往下找，复杂度为O(n)。 增加元素，由于要保持数组内存的连续性，在所插入位置之后的所有元素都需要依次后移，复杂度为O(n)，而链表增加元素只需要改变增加位置前一个节点的指针指向，即可以实现增加，复杂度O(1)。 删除类似于增加，数组中所删除元素之后的元素都需要依次前移，链表也只需改变删除节点前一个节点的指针指向即可，两这复杂度分别为O(n)与O(1)。 综上来说，数组适用于读操作（查询）更多的场景，链表适用于写操作（增删）更多的场景。