放弃"相邻"约定
顺序表把关系藏在位置里: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。
本节问题放弃"相邻格子放相邻元素"这条约定,"谁在谁后面"的关系存到哪里?
什么是链式存储
办法是把关系明确地记下来:在每个字符右边的格子里,写上下一个字符的地址。
text┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ c │109│ │ │ │ t │ 0 │ │ │ a │105│ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
右格里的109、105不是数据,是另一个格子的编号。c的右格写着109,意思是"c的下一个在109号"。到109号,读到a。a的右格写着105,再到105号,读到t。
t的右格写着0,表示后面没有了。地址0不会放任何变量,所以用它做结束标记。
还差一样:从哪开始读?我们看图知道c在最前面,程序却不知道。所以还要另外记下第一个字符的地址:head等于100。
这就是新的存法。现在给它和它用到的东西起名字。
链式存储就是:每个元素旁边,记下它后一个元素的地址。元素本身放在哪个格子都行。
一格数据加一格地址,合起来叫一个结点。上图有三个结点,分别在100号、109号、105号。
结点用地址一个接一个串起来,这样存的线性表叫链表。
另外记下的第一个结点的地址head,叫头指针。
所以,一个链表,就是一串用地址连起来的结点,加上一个头指针。
结点和元素要分清。元素是c、a、t这些数据,结点是"数据加下一个地址"这两格。下文说"c结点",指的是存放元素c的那个结点。说地址、说指向的时候,说的都是结点。
回到开头的问题。"谁在谁后面"不再靠位置,而是存在每个结点的地址格里。
格子图看得清"分开存",却看不清顺序。把它简化一下:只画三个结点,按逻辑顺序从左往右摆,方框下面标出结点的地址;地址格里的数字画成箭头,指向那个地址上的结点。
texthead = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 109 105
这就是链表的箭头图。它和上面的格子图是同一份数据,只是画法不同。格子图按内存位置排,t在a前面;箭头图按逻辑顺序排,t在最后。
两张图一一对应。c结点的地址格写着109,箭头就指向109号的a结点;a结点的地址格写着105,箭头就指向105号的t结点。箭头只是地址的画法,改了地址格里的数字,箭头就跟着变。
后面讲链表,都画箭头图。
链式存储的得失
放弃"相邻"约定,换来了什么,又付出了什么?
先看换来的。在a和t之间插入x:x放进任何一个空格子,比如102号;x的地址格写105,接到t;a的地址格从105改成102,让a接到x。
text┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ c │109│ x │105│ │ t │ 0 │ │ │ a │102│ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
texthead = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 109 │────►│ a │ 102 │────►│ x │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
100 109 102 105
c、a、t一个都没挪,只改了两个地址格。顺序表在这里要把t往后挪一格;插得越靠前,挪得越多。
删除也一样:要删掉x,只要把a的地址格从102改回105,同样一个元素都不挪。所以Insert和Delete本身,都不用挪动元素。
再看付出的。开头说过,相邻存放时,按位置一步就能取到元素。放弃相邻之后,位置算不出地址。还是看原来的cat:要取t,只能从head出发:到100号读地址格,得到109;到109号读地址格,得到105;到105号,才读到t。取第i个,也就是Get,要从第一个结点出发,顺着地址走i步,最坏走n−1步,是O(n)。
Insert、Delete也躲不开这一步。上面改的是a的地址格,可程序怎么知道a在109号?也只能从head走过去。改地址本身只要一步,找到要改的结点却要从头走。插得越靠后,走得越远,最坏也是O(n)。
所以,放弃"相邻"约定,省掉的是挪动,付出的是走路。
另外两个操作,从定义就能看出来。一个链表只有结点和头指针,没有记长度。要知道有几个,只能从head出发数一遍,Length是O(n)。Init只要让head等于NULL,一步就完成,O(1)。
| 操作 | 时间复杂度 | 为什么 |
|---|
| Init | O(1) | 只让head等于NULL |
| Length | O(n) | 从head数一遍 |
| Get | O(n) | 从第一个结点走i步 |
| Insert、Delete | O(n) | 要先走到前一个结点;改地址本身只要一步 |
顺序表和链表的逐项对比,放在2.19。