本节书摘来自华章出版社《数据结构与算法：Python语言描述》一书中的第3章，第3.4节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看
3.4链表的变形和操作
链表并非只有前面讨论的一种。实际上，人们提出了许多形式不同的链表设计，它们各有优点和适用环境。下面首先介绍单链表的简单变形，而后再介绍双链表。
3.4.1单链表的简单变形
即使同为单链表（即每个结点只有一个指针域），也存在多种不同的设计，而且完全可以根据需要和认识修改已有的设计。现在从前面定义的简单单链表的一个缺点出发，讨论一种修改后的设计。
前面单链表实现有一个缺点：尾端加入元素操作的效率低，因为这时只能从表头开始查找，直至找到表的最后一个结点，而后才能链接新结点。
在实际中，需要频繁地从表的两端加入元素的情况也很多见。现在的问题是，能不能改进表的设计，提高后端插入操作的效率？
图3.12给出了一种可行设计，其中的表对象增加一个表尾结点引用域。有了这个域，只需常量时间就能找到尾结点，在表尾加入新结点的操作就可能做到O(1)。
应该注意到：链表的这一新设计与前面单链表的结构近似，这种结构变化应该不影响非变动操作的实现，只影响到表的变动操作。在这种情况下，有可能重用前面定义（或者前面定义的一部分）吗？
通过继承和扩充定义新链表类
实际中经常遇到这样的问题：需要的程序部件和某个已有部件很像，但也有些不同。在这种情况下，一个简单想法是把原来的代码复制一份，在其基础上修改。但是，一旦复制了代码，引进了重复片段，很多麻烦就不可避免地出现了。维护两份类似代码很麻烦，不但两者都可能需要修改，还可能需要确保维护修改的一致性。
第2章讲过，面向对象编程技术为解决这方面的问题提供了支持，允许基于已有类（基类）定义新类（派生类）。这种派生类将继承其基类的所有功能（数据域和方法），可以定义新的数据域，定义新的方法，还可以重新定义基类里已定义的方法（覆盖已有方法）。下面通过把链表的新变形作为派生类的例子，展示如何做这件事情。
链表类LList提供了（具有图3.12所示新结构的）新链表类对象的许多功能，应该尽可能设法利用。用面向对象编程的说法，即应该考虑把新链表类定义为LList的派生类。这样，这个新类就能继承LList的所有非变动操作。实际上，作为派生类会继承基类的所有操作，但原有的变动操作不符合需要，必须重新定义。
从数据域看，新类的对象需要增加一个尾结点引用域，在这个类的初始化函数里应正确设置这个域，变动操作都可能修改这个域，需要重新定义。
第2章最后介绍了如何在定义新类的时候指定其基类。将现在要定义的类命名为LList1，这个类的定义的头部就应该是：
class LList1(LList):
...... # 方法定义和其他
实际上，任何用户定义类都是某个类的派生类。如果定义时不注明基类，按Python的规定，这个类自动以公共类object作为基类。也就是说，前面定义的类LNode和LList都以object作为基类，是object的派生类。前面定义的异常类也继承了已有的异常类，是特定标准异常类的派生类。
初始化和变动操作
下面考虑类的方法定义，首先是初始化方法。注意，LList1类的对象也是LList类的对象，是想作为链表使用的，因此这种对象里应该有LList对象的所有数据域（虽然这里只有一个_head，但其他基类可能有很多），在LList1的初始化函数中，应该首先初始化LList对象的那些数据域。做这件事，最合理而且方便的方式就是对self对象调用LList类的初始化函数。现在还要初始化一个尾结点引用域。由于是作为内部数据域，用_rear作为域名，将它也初始化为None：
def __init__(self):
LList.__init__(self)
self._rear = None
考虑前端插入操作。加入包含新数据的结点，操作方式与LList里一样，但现在还要考虑尾结点引用域的设置：如果原来是空表，新加入的第一个结点也是最后一个结点。这说明需要重新定义prepend覆盖原来的操作。下面是一种定义方式：
def prepend(self, elem):
self._head = LNode(elem, self._head)
if self._rear is None: # 是空表
self._rear = self._head
这里用检查_rear是否为None的方式判断空表，实际上要求在表空的时候，不仅_head是None，_rear也必须是None。相应的删除操作也需要保证这一点。
回忆一下，从LList继承的判断表空操作只检查_head。同一个类里的其他操作应该与它一致。下面定义虽然比上面的长一点，但更合适：
def prepend(self, elem):
if self._head is None:
self._head = LNode(elem, self._head)
self._rear = self._head
else:
self._head = LNode(elem, self._head)
在一个类里，不同的方法在处理同一事项上应保持一致，下面有专门讨论。
增加了尾结点引用后，可以直接找到尾结点，在其后增加结点的操作也能更快完成。这个操作的性能是本次设计修改的主要收获。注意，在链表操作定义中，通常都需要区分被修改的是头变量（域）的情况还是一般情况。函数定义：
def append(self, elem):
if self._head is None: # 是空表
self._head = LNode(elem, self._head)
self._rear = self._head
else:
self._rear.next = LNode(elem)
self._rear = self._rear.next
现在应该考虑弹出元素的操作pop，有趣的是它不需要重新定义。之所以能这样，与统一用_head为None判断空表有关。请读者自己分析。
最后是弹出末元素的操作。若采用新的表结构，这个函数没有变简单，反而稍微麻烦了一点。现在删除了尾结点之后还需更新_rear。由于确定了统一用_head的值判断表空，删除最后一个结点使表变空时，不需要给_rear赋值None：
def pop_last(self):
if self._head is None: # 是空表
raise LinkedListUnderflow("in pop_last")
p = self._head
if p.next is None: # 表中只有一个元素
e = p.elem
self._head = None
return e
while p.next.next is not None: # 直到p.next是最后结点
p = p.next
e = p.next.elem
p.next = None
self._rear = p
return e
下面是一段使用这个类的代码：
mlist1 = LList1()
mlist1.prepend(99)
for i in range(11, 20):
mlist1.append(randint(1,20))
for x in mlist1.filter(lambda y: y % 2 == 0):
print(x)
新类的基本使用形式与LList相同，变化的只是后端插入操作的效率。最后一个语句输出表mlist1里的所有偶数，其中用一个lambda表达式描述筛选条件。
类设计的内在一致性
现在结合上面的例子，简单讨论类设计中的一个重要原则。
一个类定义是一个整体，它描述了一种程序对象。类定义比较复杂，其中可以有许多成分，特别是可能定义了许多方法。每个方法定义是类定义中的一个独立片段，编程语言（Python）对不同方法之间的关系并没有任何约束，也不对这样一组方法定义做任何相互关系方面的检查。但是，作为同一个类定义的成分，这些方法需要相互协调，保持一致，才能保证所定义的程序对象有意义。这件事需要编程序的人考虑和保证。
以类LList1为例，前面讨论了两种可能设计：一种设计要求在表空的时候_head和_rear的值都是None，另一种设计只要求这时_head为None。基于两种设计都能正确实现这个类，但是一旦选定了一种设计，类中的所有方法都必须遵照这种设计来定义，包括所有的插入和删除操作。
一般情况，在设计一个类时总需要考虑一套统一的规则。类的初始化方法建立起的对象应满足这些规则，操作也不能破坏规则，这样定义的类才是有效的。
当然，不同规则可能影响类定义的细节和复杂程度。在上面例子里采用了后一种设计，也是因为它更简单，需要维护的关系少一点。还考虑到基类的已有设计，尽可能与其保持一致，以便更多地利用已有的功能。
3.4.2循环单链表
单链表的另一常见变形是循环单链表（简称循环链表），其中最后一个结点的next域不用None，而是指向表的第一个结点，如图3.13a所示。但如果仔细考虑，就会发现在链表对象里记录表尾结点更合适（如图3.13b），这样可以同时支持O(1) 时间的表头/表尾插入和O(1) 时间的表头删除。当然，由于循环链表里的结点连成一个圈，哪个结点算是表头或表尾，主要是概念问题，从表的内部形态上无法区分。
现在考虑实现一个循环单链表类，采用图3.13b的表示。下面只讨论几个典型操作，它们反映了循环链表各方面的特点，更多操作留给读者作为练习。
循环单链表操作与普通单链表的差异就在于扫描循环的结束控制。易见，一些不变操作的实现也要修改，如printall。
这种表对象只需一个数据域_rear，它在逻辑上始终引用着表的尾结点。前端加入结点，就是在尾结点和首结点之间加入新的首结点，尾结点引用不变。通过尾结点引用很容易实现这个操作。另一方面，尾端加入结点也是在原尾结点之后（与首结点之间）插入新结点，只是插入后要把它作为新的尾结点，因此需要更新尾结点引用。这两个操作都要考虑空表插入的特殊情况。对于输出表元素的操作，关键在于循环结束的控制。下面实现中比较扫描指针与表头结点的标识，到达了表头结点就结束。前端弹出操作也很容易实现，后端弹出操作（留作练习）需要通过一个扫描循环确定位置。
循环单链表类
下面循环单链表类定义只实现了几个典型方法，供参考：
class LCList: # 循环单链表类
def __init__(self):
self._rear = None
def is_empty(self):
return self._rear is None
def prepend(self, elem): # 前端插入
p = LNode(elem)
if self._rear is None:
p.next = p # 建立一个结点的环
self._rear = p
else:
p.next = self._rear.next
self._rear.next = p
def append(self, elem): # 尾端插入
self.prepend(elem)
self._rear = self._rear.next
def pop(self): # 前端弹出
if self._rear is None:
raise LinkedListUnderflow("in pop of CLList")
p = self._rear.next
if self._rear is p:
self._rear = None
else:
self._rear.next = p.next
return p.elem
def printall(self): 输出表元素
if self.is_empty():
return
p = self._rear.next
while True:
print(p.elem)
if p is self._rear:
break
p = p.next
前面简单链表的演示代码也可以用在这里，只需要修改类名。
3.4.3双链表
单链表只有一个方向的链接，只能做一个方向的扫描和逐步操作。即使增加了尾结点引用，也只能支持O(1) 时间的首端元素加入/删除和尾端加入。如果希望两端插入和删除操作都能高效完成，就必须修改结点（从而也是链表）的基本设计，加入另一方向的链接。这样就得到了双向链接表，简称双链表。有了结点之间的双向链接，不仅能支持两端的高效操作，一般结点操作也会更加方便。当然，这样做也需要付出代价：每个结点都需要增加一个链接域，增加的空间开销与结点数成正比，是O(n)。如果每个表结点里的数据规模比较大，新增加的开销可能就显得不太重要了。
为了支持首尾两端的高效操作，双链表应该采用图3.14所示的结构，包含一个尾结点引用域。易见，从双链表中任一结点出发，可以直接找到其前后的相邻结点（都是O(1) 操作）。而对单链表而言，只能方便地找到下一个结点，要找前一结点，就必须从表头开始逐一检查（通过一次扫描）。
可以直接找到当前结点的前后结点，使得双链表的许多操作都很容易地进行。下面假定结点的下一结点引用域是next，前一结点引用域是prev。
结点操作
先考虑结点删除。实际上，只要掌握着双链表里一个结点，就可以把它从表中取下，并把其余结点正确链接好。图3.15说明了这个操作。示例代码是：
p.prev.next = p.next
p.next.prev = p.prev
这两个语句使p所指结点从表中退出，其余结点保持顺序和链接。如果要考虑前后可能无结点的情况，只需增加适当的条件判断。
在任一结点的前后加入结点的操作也很容易局部完成，只需掌握确定加入位置的这个结点。易见，加入一个结点需要做四次引用赋值，请读者自己考虑。
双链表类
现在考虑定义一个双链表类。
首先，双链表的结点与单链表不同，因为结点里多了一个反向引用域。可以考虑独立定义，或者在LNode类的基础上派生。这里用派生方式定义：
class DLNode(LNode): # 双链表结点类
def __init__(self, elem, prev=None, next_=None):
LNode.__init__(self, elem, next_)
self.prev = prev
使用的方式与链表结点类似。
下面定义了一个双链表类，从带首尾结点引用的单链表类LList1派生，采用图3.14所示的结构。空表判断和find、filter、printall方法都可以继承，它们执行中只使用next方向的引用，用在双链表上也完全正确。
类中的几个变动操作都需要重新定义，因为它们需要设置前一结点引用prev。可以看到，这里的首端和尾端的插入/删除方法中都不需要循环，因此都能在常量时间内完成。如果仔细检查下面的两对方法，可以发现它们几乎是对称的，其中的_head与_rear对应，next与prev对应。
class DLList(LList1): # 双链表类
def __init__(self):
LList1.__init__(self)
def prepend(self, elem):
p = DLNode(elem, None, self._head)
if self._head is None: # 空表
self._rear = p
else: # 非空表, 设置prev引用
p.next.prev = p
self._head = p
def append(self, elem):
p = DLNode(elem, self._rear, None)
if self._head is None: # 空表插入
self._head = p
else: # 非空表, 设置next引用
p.prev.next = p
self._rear = p
def pop(self):
if self._head is None:
raise LinkedListUnderflow("in pop of DLList")
e = self._head.elem
self._head = self._head.next
if self._head is not None: # _head空时不需要做任何事
self._head.prev = None
return e
def pop_last(self):
if self._head is None:
raise LinkedListUnderflow("in pop_last of DLList")
e = self._rear.elem
self._rear = self._rear.prev
if self._rear is None:
self._head = None # 设置 _head保证is_empty正确工作
else:
self._rear.next = None
return e
前面各种链接表的演示代码在这里都能工作，只是有些操作的性能改善了，从代码执行的输出结果上看不到什么不同。
循环双链表
双链表也可以定义为循环链表，也就是说，让表尾结点的next域指向表的首结点，而让表首结点的prev域指向尾结点。如图3.16所示。易见，在这种表里，各结点的next引用形成了向下一结点方向的引用环，而各结点的prev引用形成向前一结点方向的引用环。两个环相向而行。实际上，图中尾结点指针并不必要。
有意思的是，由于在这种表里存在双向链接，无论是掌握着表的首结点还是尾结点，都能高效实现首尾两端的元素加入/删除操作（O(1) 复杂度）。
这种链表的实现留作练习。
3.4.4两个链表操作
前面几小节讨论了链表的几种重要变形，并且展示了如何在各种不同的结点链接结构上实现几个最基本的操作。现在讨论两个更有趣一点的链表操作，从它们的实现中可以看到链表操作的更多特点。
链表反转
首先考虑表元素的反转，也就是Python中list类reverse操作的工作。在3.2.4节最后给出了一个顺序表上的示例性实现。反转顺序表中元素的算法用两个下标，通过逐对交换元素位置并把下标向中间移动的方式工作，直到两个下标碰头时操作完成。
同样的操作模式可以用在双链表上，因为双链表中结点有next和prev两个引用，同时支持两个方向的扫描操作，这个问题留作个人练习。在单链表上也可以实现这种操作方式，实现元素反转。但是单链表不支持从后向前找结点，要找前一结点，只能从头开始做，这就使算法需要O(n2) 时间。请读者想想还有别的办法吗？
请注意，对顺序表而言，改变其中元素的顺序的方法只有一种，就是在表中搬动元素。而对于链表，实际上存在着两种方法：可以在结点之间搬动元素，也可以修改结点的链接关系，通过改变结点的链接顺序来改变表元素的顺序。
根据前面讨论，通过搬动元素的方式实现单链表中的元素反转很不方便，而且效率很低。下面考虑基于修改链接的方法，看看有什么可能。
对于单链表，有一个情况很重要：在首端插入/删除元素或结点是最方便的操作，只需要O(1) 时间。实现单链表操作时，最好能在首端进行。
如果不断向一个表的首端插入结点，最早放进去的结点将在表的最后（即尾结点），而从表的首端取下结点，最后取下的是尾结点。也就是说，从一个表的首端不断取下结点，将其加入另一个表的首端，就形成了一个反转过程。取下和加入操作都是O(1) 的，总时间开销是O(n)，所以这个过程就是一个高效的反转算法。
下面的函数作为LList类的一个方法，最后把反转后的结点链赋给表对象的_head域。链表类LList1继承LList时，必须重新定义这个方法，因为它需要反转操作在完成基本工作后正确设置_rear：
def rev(self):
p = None
while self._head is not None:
q = self._head
self._head = q.next # 摘下原来的首结点
q._next = p
p = q # 将刚摘下的结点加入 p 引用的结点序列
self._head = p # 反转后的结点序列已经做好，重置表头链接
在实际生活中也经常能见到类似的过程，如通过调度把一列火车车厢的顺序颠倒过来。另外，如果桌上有一摞书，一本本拿下来放到另一处，叠成另一摞，也是这个操作的实例。
链表排序
现在考虑一个更复杂的操作：对链表中的元素排序。把一组物品按某种顺序排列是在真实世界中经常需要做的工作，数据处理中也经常需要将数据排序。
排序是一种数据序列操作，希望对序列中数据项的位置做一些调整，使它们按某种特定的顺序排列。由于这是数据处理中经常需要做的事情，人们对排序问题做了很多研究，开发出许多重要算法。本书第9章将专门研究这个问题。本节只是想通过排序问题，讨论表操作的一些技术。下面讨论中假定数据可以用“>”和“<=”等关系运算符比较，希望完成的是将序列（表）里的数据按“<=”关系从小到大排序。
Python的list类型有一个sort方法，可以完成list的元素排序。如果lst的值是一个list类型的对象，lst.sort()将把lst中元素从小到大进行排序。另外，也可以用标准函数sorted对各种序列进行排序，sorted(lst)生成一个新的表（list类型的对象），其中元素是lst的元素排序的结果。
链表里也存储着数据的序列，因此也经常有对其中元素排序的需求。下面讨论单链表的排序问题，以及相关的算法和实现。
这里只准备考虑一种简单的排序算法，称为插入排序。其基本想法是：
1）在操作过程中维护一个排好序的序列片段。初始时该段只包含一个元素，可以是任何一个元素，因为一个元素的序列总应该认为是排序的。
2）每次从尚未处理的元素中取出一个元素，将其插入已排序片段中的正确位置，保持插入后的序列片段仍然是正确排序的。
3）当所有元素都加入了排序的片段时，排序工作完成。
先看一个顺序表（list）排序函数，帮助理解插入排序的操作过程。首先要考虑已排序段的安排，放在哪里。由于未排序部分越来越小，每做一次上面的操作 2减少一个元素；已排序部分越来越大，每次增加一个元素。因此，可以让这两个部分共用原来的表，例如在表前部积累排序片段，不需要额外的存储。
排序过程中，被排序表的状态如图3.17a所示：下标i之前的段已经从小到大排序，从i开始的段尚未处理，下一步考虑位置i的元素d的插入问题，并正确完成这一工作。这样一次处理一个元素后i值加一，直至i的值超出表的右端时排序完成。
一个元素的处理也需要通过一个循环。在这个循环中，需要维持已排序元素的相对顺序，并最终确定d的正确插入位置。循环开始时取出d，使位置i变为空位。循环中的状态如图3.17b所示：新下标变量j记录空位，并逐步左移。每次迭代将j－1位置的元素与d比较，如果d较小，就把位于j－1的元素右移到j位置，并将j值减一（表示空位左移了）。这样在j到i之间就会积累一段大于d的元素。反复做到位置j之前元素不大于d时，将d放入空位。显然，直至i的子序列仍保持有序。将i加一后又回到了图3.17a的状态。
这个算法中需要嵌套的两重循环：
def list_sort(lst):
for i in range(1, len(lst)): # 开始时片段[0:1]已排序
x = lst[i]
j = i
while j > 0 and lst[j-1] > x:
lst[j] = lst[j-1] # 反序逐个后移元素至确定插入位置
j -= 1
lst[j] = x
现在考虑单链表的排序算法。注意：由于这里只有next链接，扫描指针只能向下一个方向移动，不能从后向前查找结点（或找元素）。另外，如前所述，这里也存在两种可能完成排序的做法：移动表中元素，或者调整结点之间的链接关系。下面将考虑两个算法，它们分别采用这两种技术完成排序，用的都是插入排序方法。
首先考虑基于移动元素的单链表排序算法。采用插入排序方法，在这里也是每次拿一个未排序元素，在已排序序列中找到正确位置后插入。但是，由于处理的是单链表，为了有效操作，算法中只能按下一个的方向检查和处理表元素。
下面算法工作中的基本状态如图3.18所示。其中扫描指针crt指向当前考虑的结点（假设这里的表元素为x），在一个大循环中每次处理一个表元素并前进一步。对一个元素的处理分两步完成：第一步从头开始扫过小于或等于x的表元素，直至确定了图3.18中已排序段里标出虚线的位置，找到了第一个大于x的表元素；第二步是做一系列“倒换”，把x放入正确位置，并将其他表元素后移。下面函数实现了这个过程：
def sort1(self):
if self._head is None:
return
crt = self._head.next # 从首结点之后开始处理
while crt is not None:
x = crt.elem
p = self._head
while p is not crt and p.elem <= x: # 跳过小元素
p = p.next
while p is not crt: # 倒换大元素，完成元素插入的工作
y = p.elem
p.elem = x
x = y
p = p.next
crt.elem = x # 回填最后一个元素
crt = crt.next
函数里比较技术性的一段是倒换大元素的循环，每次迭代取出一个结点里的数据，然后把手头数据x存入，前进一步。请仔细考察其中的操作和顺序。
现在考虑通过调整链接的方式实现插入排序。这种方法的操作过程比较好理解，就是一个个取下链表结点，将其插入一段元素递增的结点链中的正确位置。
这个过程由下面的方法实现。如果被处理的表为空或只包含一个元素，它自然是排序的，工作完成。表更长时就需要处理。函数里用rem记录除第一个元素之外的结点段，然后通过循环把这些结点逐一插入_head关联的排序段。
函数的内层循环在排序段查找rem结点的插入位置。这里用了两个扫描指针p和q，它们亦步亦趋地前进，直到p所指结点的元素更大或已到排序段尾，这时结点rem应该插入q和p之间。随后的条件语句分别处理表头插入和一般情况插入，最后连接好排序段并将rem推进一步。大循环结束时全部结点都插入排序段，工作完成。
def sort(self):
p = self._head
if p is None or p.next is None:
return
rem = p.next
p.next = None
while rem is not None:
p = self._head
q = None
while p is not None and p.elem <= rem.elem:
q = p
p = p.next
if q is None:
self._head = rem
else:
q.next = rem
q = rem
rem = rem.next
q.next = p
在这个定义里，需要特别注意最后三个赋值语句。赋值的次序不能出错，否则将导致被处理的表段丢失，就不可能完成排序工作了。
两个排序函数都假定定义在LList类里，用在其他地方时需适当修改。
3.4.5不同链表的简单总结
3.3节和本节介绍了多种不同的链表结构，现在对它们做一个简单的总结，其中讨论时间复杂度时用的n均指表的长度。
基本单链表包含一系列结点，通过一个方向的链接构造起来。它支持高效的（O(1) 的）前端（首端）插入和删除操作，定位操作或尾端操作都需要O(n) 时间。
增加了尾结点引用域的单链表可以很好地支持首端/尾端插入和首端弹出元素，它们都是O(1) 时间复杂度的操作，但不能支持高效的尾端删除。
循环单链表也能支持高效的表首端/尾端插入和首端弹出元素。在这种表上扫描，需要特别注意结束判断问题。
双链表中每个结点都有两个方向的链接，因此可以高效地找到前后结点。如果有尾结点引用，两端插入和删除操作都能在O(1) 时间完成。循环双链表的性质类似。
对于单链表，遍历和数据检索操作都只能从表头开始，需要O(n) 时间。对于双链表，这些操作可以从表头或表尾开始，复杂度不变。与它们对应的两种循环链表，遍历和检索可以从表中任何一个地方开始，但要注意结束条件。
链接表有一些重要的优点，分析如下：
表结构是通过一些链接起来的结点形成的，结点（及其中表元素）之间的顺序由链接关系决定，链接可以修改，因此表的结构很容易调整和修改。
不需要修改结点里的数据元素或移动它们，只通过修改结点之间的链接，就能灵活地修改表的结构和数据排列方式。例如，加入/删除一个或多个元素，翻转整个表，重排表中元素顺序，将一个表根据需要划分为两个表或多个表，等等。
整个表由一些小的存储块构成，比较容易安排和管理。用Python编写程序时，这些问题由解释器负责，程序员不必处理，但了解情况也很重要。
链接表也有一些明显的缺点，主要是一些操作的代价比较大：
定位访问（基于位置找到元素）需要线性时间，这是与顺序表相比的最大劣势。
简单单链表上的尾端操作需要线性时间。增加一个尾指针，可以将尾端插入变成常量时间操作，但仍不能有效实现尾端删除。双链表通过在每个结点里增加第二个链接，可以实现两端的高效插入和删除。
要找当前元素的前一元素，必须从头开始扫描表结点。这种操作应尽量避免。双链表可以解决这个问题，但每个结点要付出更多存储代价。
为存储一个表元素，需要多用一个链接域，这是实现链接表的存储代价。双链表可以提高链表操作的灵活性，但需要增加两个链接域。
