数据结构包含数组，链表，散列表，树，图 。但其实所有数据结构的底层思想原理，也都是基于数组链表。今天来谈谈这两种基础数据结构的理解。
两种数据结构特点：
数组：从内存中分配一段连续的内存空间，来存放数据。访问时通过内存地址进行访问。因为存储空间要求连续，所以分配好之后并不方便扩容，如果空间不够用，就只会重新找一段更大的内存空间，然后把原始数据挪过去。
链表：只为一个数据分配内存空间，我们把它称为 节点。每一个节点都有一个变量空间用于指向下一个节点，下一个节点再指向再下一个。以此类推。直到最后一个节点的下一个节点为空，我们把它称为尾节点。相应的第一个节点叫做头节点。因为链表的内存分配是动态的，需要的时候才进行分配。所以，在数据扩容时更加方便，只需要再分配一块内存然后尾节点只想该节点即可。
上面只是简要说明，下面会进行再详细的描述：
数组的访问，插入，删除，扩容：
- 访问：因为数组是一次性分配好一段连续的内存空间，并给每一个存储空间分配一个下标，即可通过下标直接访问到数据的内存地址以获取数据。时间复杂度：O(1)（常数级）
- 插入：分为两种情况，第一种是插入在最后一个有效元素后面，则只需要直接把数据放在最后一个元素后面的下标中即可。第二种是插入在指定位置，则需要把后面的元素全部向后移动一位，然后把腾出来的空间给需要插入的指定元素。（两种情况前提是数组有剩余空间，如无剩余空间则参考扩容）时间复杂度：插入在指定位置复杂度为O（n），如插入到最后则为O（1）
- 删除：同样是两种情况，第一种，无需理会数组中为空的下标，则直接把指定下标置空；第二种需要考虑的话，处理方式则是把后续所有下标全部向前移动，并将最后一位置空。时间复杂度：如无需移动其他元素：O(1),如需移动其他元素O(n)
- 扩容： 因为数组的空间是静态分配的，一开始就定死了。如果动态使用中发现空间不够用。则只能重新分配一段更大的内存空间，因为重新分配的内存空间是新的，所以还需要将原始的数据迁移过去。扩充过程时间复杂度：O(n)
链表的访问，插入，删除，扩容：
- 访问：因为链表是动态分配的，寻找方式是通过头节点，挨个寻找下一个节点找下去，直到找到指定位置的节点为止。所以随机访问的时间复杂度较高，时间复杂度为：O（n)
- 插入：插入这个过程在链表中体现相对比较简单。举例来说，链表a,c,d。需要在a后面插入b，插入过程为将b的next指向c，然后a的next指向b，就已经完成了插入。如果是尾节点还可以再省一步。无需考虑其他元素，所以时间复杂度为：O(1)
- 删除： 同样以前面a,c,d链表举例子，如需删除c，将a的next指向d即可。逻辑跟插入的逻辑类似。时间复杂度：O(1)
- 扩容：链表的扩容于插入元素相同，无需考虑数据迁移问题。略过。
以上可以得出一个基本的结论，链表更适合增删扩容的场景，而数组则更适合需要数组内容变化少，随机访问性能要求高的场景。但是这两种仅仅是基础数据结构，在后续还有这两种数据结构的基础上改进的来的数据结构，兼顾了两种数据结构的优点。
