数据结构与算法的Python实现（三）——线性表之链表

上一篇中我提到线性表的另一种实现——链表，这一篇就主要讲链表。

一、链表的概念和基本思想

（一）链表的概念

线性表的一个基本特性就是元素的序列关系，顺序表虽然没有直接指明序列关系，但因为保存在了连续的存储空间内，所以形成了这种关系。我们也可以不把元素连续存储，而在每个元素中指明序列关系，这样就也可以实现线性表了，基于这种链接结构的线性表，就叫做链表。

（二）实现链表的基本思想

1.表中的每一个元素都独立存储在自己的一块空间内；

2.表中的任意元素都记录了下一元素的位置，可以通过这个位置找到下一元素。

由此，只需要找到第一个元素所在结点，就可以顺着链接找到任意一个元素所在结点。

二、单链表

（一）单链表的概念

单链表全称单向链接表，一般说链表就是指单链表。

单链表的每一个结点都是一个二元组，分别存放表的元素elem和下一结点next。表里的所有元素通过链接形成单链表，通过变量p找到首结点，顺次就可以找到其他元素。

所以说，只需要用一个变量保存对首结点的引用，就可以完全控制整个表了，这个变量就叫表头变量。

链表的最后一个结点并没有下一个元素，所以链接指向None（Python中的系统变量，表示空）。

由以上讨论，我们可以定义一个简单的表结点类：

class LNode:

def __init__(self,elem,next_node = None):

self.elem = elem

self.next = next_node

（二）链表操作

1.创建一个空链表

只需要把表头变量设置为None即可。O(1)

2.删除链表

同理，直接将表头变量指向None，解释器会自行回收被抛弃的结点。O(1)

3.判断是否为空

判断表头变量是否为None即可。O(1)

（三）元素操作

1.插入元素

•在表的首结点前插入O(1)

分为三个步骤，一是创建一个表结点q，二是将q的next指向第一个结点，即head当前指向的结点，然后将head指向q：

q = LNode(12)

q.next = head

head = q

•在其他位置插入O(n)

假设要插入的位置的前一结点为pre，操作类似：

q = LNode(12)

q.next = pre.next

pre.next = q

2.删除元素

•删除首结点元素O(1)

直接表头变量指向第二个结点即可：

head = head.next

•其他结点删除O(n)

同理，只需将上一结点跳过该结点指向下一结点即可：

3.扫描和遍历

•扫描定位O(n)

单链表的特性导致只能从首结点开始寻找制定结点，如果是按照下标i查找：

p = head

while p is not None and i>0:

i -= 1

p = p.next

如果是按照元素elem查找：

p = head

while (p is not None) and (not (p.elem == elem)):

p = p.next

•遍历O(n)

以遍历输出元素为例：

p = head

while p is not None:

print(p.elem)

p = p.next

4.求表的长度

采用遍历结点的方式：O(n)

def length(head):

p , n = head , 0

while p is not None:

n += 1

p = p.next

return n

这种方式效率比较低，每次求表长都需要遍历，我们可以在首结点前加一个结点作为存放表长度的区域，该结点的next指向第一个表结点，这样只需读取该区域就可以获取长度了，时间复杂度变为O(1)，但每次执行插入删除时都需要修改改长度的值。

三、单链表的Python实现

先定义一个异常类用于处理空表访问等异常情况：

class LinkedListUnderflow(ValueError):

pass

在前面，我们定义了单链表结点类：

class LNode:

def __init__(self,elem,next_node = None):

self.elem = elem

self.next = next_node

接下来是单链表类的实现：

class LList:

def __init__(self): #创建空链表

self._head = None

def is_empty(self): #判断是否为空链表

return self._head is None

def prepend(self,elem): #在最开始插入元素

self._head = LNode(elem,self._head)

def pop(self): #弹出首结点元素并输出

if self._head is None:

raise LinkedListUnderflow(“pop None”)

e = self._head.elem

self._head = self._head.next

return e

def append(self,elem): #在最后追加元素

if self._head is None:

self._head = LNode(elem)

p = self._head

while p.next is not None:

p = p.next

p.next = LNode(elem)

def pop_last(self): #弹出尾结点元素并输出

if self._head is None:

raise LinkedListUnderflow(“pop_last None”)

p = self.head

if p.next is None:

e = p.elem

self._head = None

return e

while p.next.next is not None:

p = p.next

e = p.next.elem

p.next = None

return e

def find(self,pred): #找到第一个满足谓词pred的元素并输出

p = self._head

while p is not None:

ifpred(p.elem):

return p.elem

p = p.next

return None

def print(self): #依次输出全部元素

p = self._head

while p is not None:

print(p.elem, end =‘’)

if p.next is not None:

print(‘,’,end = ‘’)

p = p.next

print(‘’)

def for_each(self, proc): #遍历所有结点并执行proc操作

p = self._head

while p is not None:

proc(p.elem)

p = p.next

def elements(self): #按所有元素构造生成器

p = self._head

while p is not None:

yield p.elem

p = p.next

def filter(self,pred): #构造链表中符合谓词pred的元素的生成器

p = self.head

while p is not None:

if pred(p.elem):

yield p.elem

p = p.next

四、链表的其他形式

（一）单链表的拓展

单链表对于尾端的操作效率很低，如果用一个变量引用尾结点，那尾结点的相关操作时间复杂度就变为了O(1)，可以用继承的方式来定义：

class LList2(LList):

def __init__(self):

LList.__init__(self)

self._rear = None

只需要在初始化时额外定义一个变量指向尾部，同样在部分操作时，需要重载方法，以最后插入元素为例：

def append(self,elem):

if self._head is None:

self._head = LNode(elem)

self._rear = self._head

else:

self._rear.next = LNode(elem)

self._rear = self._rear.next

（二）循环单链表

循环单链表的尾结点的next指向头结点，形成了一个圈，此时只需要一个rear指向尾结点就可以确保，首结点和尾结点的操作时间复杂度都为一，定义如下：

class LCList:

def __init__(self):

self._rear = None

部分操作会变简单，以在最后插入元素为例：

def append(self,elem):

p = LNode(elem)

if self._rear is None:

self._rear = p

p.next = p

else:

p.next = self._rear.next

self._rear.next = p

self._rear = self._rear.next #在开头插入时，删除这条语句即可

（三）双向链表

单循环链表存在的问题是删除尾结点的时间复杂度依然为O(n)，如果在每个结点中，不仅可以引用下一个结点，还可以引用上一个结点的话，那这个问题就解决了，不过增加了额外的空间消耗。新的结点定义如下：

class DLNode(LNode):

def __init__(self,elem,pre = None,next_node = None):

LNode.__init__(self,elem,next_node)

self.prev = pre

双向链表的类可以直接从拓展后的单链表继承，具体操作要有变化，以删除尾结点为例：

def pop_last(self):

if self._head is None:

raise LinkedListUnderflow(“DLList pop_last None”)

e = self._rear.elem

self._rear = self._rear.pre

if self._rear is None:

self._head = None

else:

self._rear.next = None

return e

（四）循环双链表

循环双链表只需要把最后一个结点的next指向首结点即可，在此不做赘述，使用循环双链表，保存首或尾的引用，都可以保证首位的增删操作时间复杂度尾O(1)。

思考：顺序表和链表完成翻转和排序操作分别应该如何实现呢？下一篇讲表的应用，讲三个内容，一个是表的翻转，一个是表的排序，一个是Josephus问题的几种解法。

以下是上篇思考题我的实现，核心思想是使用两个栈，一个维护数据，一个维护最小值，用一倍的空间将getMin方法时间复杂度变为O(1)，欢迎提建议：

class MyList:

def __init__(self):

self._list = [ ]

self._min_list = [ ]

def pop(self):

if self._list is None:

return None

self._min_list.pop()

return self._list.pop()

def push(self,x)

self._list.append(x)

if self._min_list is None:

self._min_list.append(x)

else:

self._min_list.append(min(x,self._min_list[-1]))

def top(self):

if self._list is None:

return None

return self._list[-1]

def getMin(self)

if self._min_list is None:

return None

return self._min_list[-1]

以上。