Skip to content
第2章

2.9 链式存储与链表 ​

放弃"相邻"约定 ​

顺序表把关系藏在位置里:a在c后面,就把a放在c的下一格。这条约定不占空间,按位置取元素也一步到位。

可是挪动也是它带来的。在编辑器里,光标停在行首附近敲字,每敲一下,光标右边的字符都要往后挪一格。2.7节算过,这是O(n)。

放弃这条约定会怎样?

放弃之后,元素可以放在内存的任何地方。插入时随便找个空格子放进去,不用挪动任何字符。

各个字符是在不同时候放进去的,每次哪里有空就放哪里。于是cat的三个字符可能散成这样:c在100号,t在105号,a在109号。

text
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ c │   │   │   │   │ t │   │   │   │ a │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

可是关系没了。按位置往后找,c的下一格并不是a。位置已经不能告诉我们谁在谁后面。

要读出cat,得有别的办法知道:c的下一个是a,a的下一个是t。

本节问题
放弃"相邻格子放相邻元素"这条约定,"谁在谁后面"的关系存到哪里?
选中正文里的任意文字,就可以针对它发表评论