Skip to content
第2章

2.19 顺序表与链表的比较 ​

顺序表:相邻存放 ​

顺序表和链表都做出了编辑器,可快慢各不相同。

本节问题
顺序表和链表,各快在哪、慢在哪?该怎么选?

先看顺序表。cat存在顺序表里是这样:

text
      ┌───┬───┬───┬───┬───┐
data  │ c │ a │ t │   │   │   length = 3
      └───┴───┴───┴───┴───┘
        0   1   2   3   4

顺序表的一切,都来自一条原理:元素一个挨一个,放在连续的格子里。逻辑上相邻,内存里也相邻。

由这一条,就能推出它的四个特点。

① 取第i个快。格子是连续的,凭位序直接就能找到第i个格子,不用从头数,O(1)。这叫随机存取。

② 插入、删除慢。要保持相邻,插入一个,后面的元素都得往后挪;删除一个,后面的都得往前挪,O(n)。

③ 要一整段连续的空间。格子必须连在一起,所以要事先申请一整段。用满了只能扩容,2.8做过。

④ 不用额外空间记关系。先后关系靠位置就记下了,格子里只存数据。图里空着的两格是另一回事:那是③事先多申请的。

选中正文里的任意文字,就可以针对它发表评论