Skip to content
第2章

2.17 双向链表 ​

找前一个结点要从头走 ​

编辑器2.1里,屏幕是cat|,光标记着t结点。按一次l左移,光标要移到t的前一个结点,也就是a结点:

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

站在t结点上,往后一步就到:它的地址格记着下一个结点的地址。可t的前一个是谁,t结点里没有任何记录。所以Prev只能从头结点出发,一个一个往后走,直到下一个是t为止。

一行有一千个字符时,光标在行尾按一次左移,就要走一千步。2.16量过,编辑器2.1的左移和退格都要调用Prev,都是O(n)。

本节问题
能不能站在一个结点上,一步就找到前一个?
选中正文里的任意文字,就可以针对它发表评论