外观
2.19 顺序表与链表的比较
顺序表:相邻存放
顺序表和链表都做出了编辑器,可快慢各不相同。
本节问题顺序表和链表,各快在哪、慢在哪?该怎么选?
先看顺序表。cat存在顺序表里是这样:
text
┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ │ │ length = 3
└───┴───┴───┴───┴───┘
0 1 2 3 4顺序表的一切,都来自一条原理:元素一个挨一个,放在连续的格子里。逻辑上相邻,内存里也相邻。
由这一条,就能推出它的四个特点。
① 取第i个快。格子是连续的,凭位序直接就能找到第i个格子,不用从头数,O(1)。这叫随机存取。
② 插入、删除慢。要保持相邻,插入一个,后面的元素都得往后挪;删除一个,后面的都得往前挪,O(n)。
③ 要一整段连续的空间。格子必须连在一起,所以要事先申请一整段。用满了只能扩容,2.8做过。
④ 不用额外空间记关系。先后关系靠位置就记下了,格子里只存数据。图里空着的两格是另一回事:那是③事先多申请的。