回顾

数组和链表是数据结构中最基础的两种结构，之前两篇都没有写如何访问访问其中的元素，现在简单的补充一下。

数组

数组的查和改

因为数组的元素在内存中都是连续的，在访问其中元素的时候，会根据元素的下标相对于第一个下标的距离直接访问内存，所以访问任意元素的时间复杂度为O(1)，不与数组下标大小有关联，所以说它的随机存取的速度非常快。改数组其中的元素其实也是访问数组的下标，更改内存地址存放的内容，其复杂度是一样的。

数组的增

查的时候说了数组存取非常快，在数组的增加元素的时候，看复杂度的时候要看元素插入的位置。自己在前面文章时候偷懒了，只在Goalng的切片后面加元素，不用动其他的元素，这是最乐观的情况，所以在数组后面添加元素的时候，时间最好复杂度
为O(1)，如果在数组最前面添加元素的话，后面元素在内存中存放的位置都要往后挪一位，此时要操作所有的元素，此时为最坏复杂度
：O(n)，如果要看平均复杂度
的话，那么就要遍历数组插入的所有插入位置的可能，然后把所有的复杂度相加再除以所有的可能的数量，那么假如数组长度为N,复杂度就是（1+2+3+...+n）/n=>n/2,然后忽略常数部分，数组增加元素平均复杂度
就是O(n)。

数组的删

删除和增加元素一样，删除数组第一个元素，后面所有的元素都要移动内存地址，复杂度为O(n)，删除最后一个元素，就只操作数组中的一个元素，此时复杂度是最好复杂度
：O(1),平均复杂度
为O(n)。

链表

链表的查和改

在上篇文章我也偷懒了，只做了一个返回链表第一个元素的方法，访问链表第一个元素的内存地址存放的值，所以此时的复杂度为最好复杂度
：O(1)，假如要访问最后一个元素的话就要从链表第一个元素开始访问，依次读取下一个节点，直到最后一个位置，因为链表的元素的内存地址是不连续的，不能直接根据下标计算自己想找的元素与头节点的之间距离，所以最坏复杂度
：O(n),平均复杂度
跟数组的增一样为O(n)，链表的改与链表的查是一样的，最主要是找到元素的位置，然后更改节点存放的值。

链表的增

链表在最后的位置增加元素的时候需要链表的头开始遍历访问各个节点内存地址，遍历到最后一个位置然后增加一个节点。所以此时的复杂度为最坏复杂度
：O(n)，没有写在第一个节点新增元素的例子，这里可以想一下，正因为链表元素的内存存放的位置不是连续的，在头节点插入元素的时候直接新增一个节点，这个新增的节点存放下一个节点的内存地址指向是旧的头节点这样就完成了头节点的元素插入，不用挪动元素的位置，此时的复杂度为O(1)，所有链表的平均复杂度为O(n)。 

链表的删

链表的删，同理链表的增，假如删除的的元素在链表的最后面，那么需要一个个遍历所有的节点才能找到尾部的节点，再删掉它，此时的时间复杂度为最坏复杂度
：O(n)，假如删除链表中元素的位置在第一位，就不用遍历，直接删掉第一个节点的位置，此时的时间复杂度为最好复杂度
：O(1)，平均复杂度
：O(n)。

总结对比

来个表格最直观：

总体看起来操作线性结构的数据结构其中元素的使用采用动态数组比较好，效率比较高，但是链表看似效率不行操作元素比较耗费时间，实际上链表很节约内存空间，用多少内存空就申请多少内存空间，不会创建很多没用的的内存空间。