Skip to content
第2章

2.16 按结点操作 ​

每次都从头找 ​

2.15做出了编辑器2.0,留下一个问题:换成链表之后,到底快没快?

用2.7的方法量一量。2.9说过,链表插入、删除不用挪动,步数全花在从头走到要改的结点上。编辑器2.0的每条指令,都按光标的位置去找结点。设这一行有n个字符:

  • 敲字符、退格:调用Insert、Delete,要从头结点走到光标处。光标在行首,一步不走;在行尾,走n步。最坏O(n)。
  • 右移:先要调用Length看是不是到了行尾。链表没有记长度,Length要从头数一遍,O(n)。
  • 左移:只改cursor,O(1)。
  • 显示:Show调用n次Get,每次Get都从头走,合起来是n×n步,O(n²)。顺序表的Show是O(n),换成链表,显示慢了一个量级。

求长度也可以是O(1)

给链表多加一个变量记长度,求长度就是O(1),不用每次从头数一遍。代价是插入、删除时,要记得把它加1、减1。多花一个变量的空间,省下数一遍的时间,这是常用的"空间换时间"。

行首打字确实快了:顺序表要挪n个字符,链表一步不用走。可在行尾打字,反而是顺序表快:顺序表一个都不挪,链表要走n步。编辑器2.0并没有整体变快,步数只是从挪动搬到了走路。

最慢的是行尾。看一个例子:屏幕是cats|,再敲一个e。

敲e,调用的是Insert(L, 4, 'e')。链表要先找到第3个结点s,才能把e接在它后面。可链表没有格子可算,只能从头结点出发,一个一个往后走:

text
L = 120
  │
  ▼
┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐
│   │ 100 │────►│ c │ 109 │────►│ a │ 105 │────►│ t │ 116 │────►│ s │  0  │
└───┴─────┘     └───┴─────┘     └───┴─────┘     └───┴─────┘     └───┴─────┘
    120             100             109             105             116
   头结点                                                          prev

走了4步,才走到s结点。可s结点就是上一次刚接上去的,光标也一直停在它后面。

一行有一千个字符时,每敲一个字,都要从头走一千步。光标明明一直停在那里,程序却每次都从头找一遍。

本节问题
光标一直停在同一个地方。能不能不再每次从头找?
选中正文里的任意文字,就可以针对它发表评论