数组与链表
数组与链表
基本概念
数组就是指数据是放在连续的内存空间，数组数据称为元素。
使用索引存取数组内容
由于数组数据是在连续空间，存取是用索引方式存取，这个读取方式在计算机领域称作随机存取，只要一个步骤就可以取得数组元素内容，所以时间复杂度是O(1)。
新数据插入数组
数组结构虽然好用，但插入删除元素需要较多时间。插入删除数据时，可能要移动所有数组元素，所以时间复杂度是O(n)。
数组的优缺点
当数组空间不足时，必须移动整个数组到新的内存空间，常常移动数组会造成程序的执行效率降低，应为数组多预留空间。多预留的空间超过时，数组数据仍必须在内存移动。如果没有使用多预留的空间，内存空间就会被浪费，别的程序也无法使用。
数组用二分法搜寻，时间复杂度是O(logn)。
链表数据形式与内存概念
链表表面上看是一串数据，但数据可能散布在内存各个地方。
链表中每个节点元素有两个区块，一个区块是数据区，主要存放数据，另一个区块是指标区，主要指向下一个元素。
链表的数据读取
链表读取数据使用顺序读取，必须从头开始搜寻数据，整个执行的时间复杂度是O(n)。
插入删除链表
只要将前一个节点指标指向此新节点，然后将新节点指标指向下一个节点就可以了，不需要遍历n个节点，所以时间复杂度是O(1)。
循环链表与双向链表
循环链表不管目前指标是指向哪一个节点，都可以搜寻整个链表。双向链表每个节点多增加了一个指标区，其中一个指标指向前面节点，另一个指标指向后面节点，指标可以向前搜寻，也可以向后搜寻。