算法与数据结构(二)-数组、链表(Array、Linked List)
数组与链表是两种最简单的线性数据结构。
1.数组:
最左边0-8是它的下标，按照这个下标你可以随机地访问这个数组中的任意元素。右边是他的内存地址，这里的内存地址是一个示意，实际情况要复杂地多，而且还会有一套寻址的算法，还会有虚拟内存类似的东西。访问内存中任意一个数组的时间复杂度是O(1)的。如果我们需要改变数组的话，我们有两种操作，一种是插入(inserting)操作，一种是删除(deleting)操作。这里的时间复杂度不是O(1)，由于要挪动之后的元素，所以是O(n)的时间复杂度。插入最后一个是O(1)的，插入最前面那个是O(n)的，平均下来的话是O(n/2)，所以我们说它的时间复杂度是O(n)的。
2.链表
如果你想改善插入和删除所用的时间复杂度的话，我们可以采用链表的方式。
用指针指向他的下一个节点，将其链起来就是链表。
链表插入操作：
链表删除也类似：
可以看到这里只需要两次操作，也就是说它的时间复杂度是O(1)的时间复杂度。但是他的查找是O(n)的时间复杂度。
除了单链表之外还有双链表，你可以往前走也可以往后走。
这样在查询的时候会方便一点。