线性表是最基础的数据结构之一,在实际程序中应用非常广泛,它常被用作其它各更为复杂的数据结构的表等。
线性表是一组元素(序列)的抽象,一个表就是某个元素的一个集合,还记录着元素之间的一些顺序关系。

线性表的抽象数据类型

抽象数据类型(ADT, Abstract Data Type),线性表的基本操作应当有创建空表长度插入删除等基本操作,其基本的ADT如下:

1
2
3
4
5
6
7
8
9
10
11
12
ADT List:
List(self) # 创建一个新表
is_empty(self) # 判断self是否是一个空表
len(self) # 返回表的长度
prepend(self, elem) # 在表头插入元素elem
append(self, elem) # 在表的尾部插入元素elem
insert(self, elem, i) # 在表的i索引位置插入数据
del_first(self) # 删除表头的数据
del_last(self) # 删除表尾的数据
del(self, i) # 删除第i个元素
search(self, elem) # 查找元素elem出现的位置
forall(self, op) # 对表进行遍历操作

书序表的实现

Python内部的 listtouple 采用的就是顺序表的结构实现,其中 touple 是固定结构,一旦创建就无法进行修改,而 list 是支持变动的操作。

Python中 listtouple 的相关方法:

1
2
3
4
new_list = list([1, 2, 3, 4, 5])
new_list.append(6)
new_list.pop()
new_list.insert(3, 7)

顺序表的优势在于 O(1) 时间的定位元素访问,头尾部添加和删除,很多简单的操作效率也比较高,比较麻烦的是中间位置插入删除操作。

链表的实现

基于链接技术实现的线性表称之为链表或者链接表,用链接关系显式的表示元素之间的顺序关系,链接表结构基本思想如下:

  • 把表中的元素分别存储在一批独立的存储块中(节点)。
  • 保证从组成表结构中的任何一个节点可找到与其相关的下一个存储块(节点)。
  • 在前一个存储块(节点)里使用链接的方式显式的记录和下一个存储块(节点)之间的关联。

单链表

链表有很多的组织方式,其中最简单的是单链表,其中每个节点记录着元素和下一个元素的链接,如下图所示:

单链表

其中,链接域里面存放着下一个节点的标识。
总结一下,一个具体的表由以下具体的结构点组成:

  • 每个节点有自己的标识(链接)
  • 节点之间通过节点链接建立顺序联系
  • 给表的最后一个节点(表尾节点)的链接域设置一个不会作为节点对象标识的值(Python中使用None)称之为空链接

链表的几个基本操作

  • 创建空链表,只需要将表头设置为空链接
  • 删除链表,丢弃链表的所有节点
  • 判断链表是否为空表,检查表头变量是否是空链接
  • 判断表是否满表,链接表不会满,除非存储空间用完

创建节点类

单个节点

节点类的实现代码如下:

1
2
3
4
class ListNode:
def __init__(self, elem):
self.elem = elem
self.next = None

节点类里面包含两个部分,节点元素和节点域。

单链表类的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class LinkedListUnderflow(ValueError):
"""
定一个链表位置定位异常
"""
pass

class LinkList:
def __init__(self):
self._head = None # 初始化头结点
self.num = 0 # num 记录节点数

def is_empty(self):
"""判断表是否为空"""
return self._head is None

def len(self):
"""返回表的长度"""
return self.num

def find(self, index):
"""查询表的第index个节点元素"""
if index > self.num or index < 1:
raise LinkedListUnderflow("超出定位范围")
node = self._head
i = 0
if index == 0:
return node
else:
while i < index:
node = node.next
i += 1
return node
单链表操作 —— 首端插入节点
  • 创建一个新节点存入数据
  • 把原链表的首节点的链接存放到新节点的链接域
  • 修改表头变量(head指针)使之引用新节点

链表头部插入流程

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class LinkList:
def __init__(self):
self._head = None # 初始化头结点
self.num = 0 # num 记录节点数

# 此处省略其它方法 ...

def prepend(self, elem):
"""链表头部插入元素"""
new_node = ListNode(elem)
new_node.next = self._head
self._head = new_node
self.num += 1
单链表操作 —— 尾端插入节点
  • 创建一个新节点存入数据
  • 如果表是空表的时,直接使表头引用新的节点并结束,否则找到表尾节点
  • 令尾结点的链接域引用新的节点,并将新的节点链接域设置为空(节点类的链接域默认为空)。

链表尾部插入流程

链表尾部插入节点代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class LinkList:
def __init__(self):
self._head = None # 初始化头结点
self.num = 0 # num 记录节点数

# 此处省略其它方法 ...

def append(self, elem):
""""""
new_node = ListNode(elem)
if self._head is None:
self._head = new_node
self.num += 1
else:
p = self._head
while p.next is not None:
p = p.next
p.next = new_node
self.num += 1

单链表操作 —— 定位插入节点

  • 找到新节点插入位置的前一个节点,不存在时结束
  • 创建新节点存入数据
  • 修改前一节点和新节点的链接域,将新节点连入

链表定位插入流程

定位插入节点代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class LinkList:
def __init__(self):
self._head = None # 初始化头结点
self.num = 0 # num 记录节点数

# 此处省略其它方法 ...

def insert(self, index, elem):
new_node = ListNode(elem)
pre_node = self.find(index - 1)
new_node.next = pre_node.next
pre_node.next = new_node
self.num += 1

单链表操作 —— 删除元素

  • 首端删除:直接修改表头指针,使之引用当时表头节点的下一个节点,Python系统会自动回收无用对象的存储块内存。
  • 尾端删除:找到倒数第二个节点,使其节点链接域设置为空链接
  • 定位删除:找到要删除元素所在的节点的前一个节点,修改该节点的链接域将需要删除的节点从表中删除

链表删除流程

删除节点操作的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class LinkList:
def __init__(self):
self._head = None # 初始化头结点
self.num = 0 # num 记录节点数

# 此处省略其它方法 ...

def locate_del(self, index):
if index == 0:
self._head = self._head.next
self.num -= 1
else:
pre_node = self.find(index - 1)
pre_node.next = pre_node.next.next
self.num -= 1

def pop(self):
p = self._head

if p is None:
raise LinkedListUnderflow("空表无法删除")
elif p.next is None:
e = p.elem
self._head = None
self.num -= 1
return e

while p.next.next is not None:
p = p.next
e = p.next.elem
p.next = None
self.num -= 1
return e

单链表操作 —— 链表倒置

对于单链表,有一个重要的特点就是,在首端进行节点的插入和删除都是 O(1) 的时间操作,实现单链表的操作的时候最好在表的首端进行。
如果不断向一个链表的首端插入节点,最早放进去的节点将会在表的最后端。也就是说在一个表的首端不断取下节点,将取下的节点插入到另一个表的首端,就形成了一个反转链表的效果,取下和插入都是 O(1) 的操作,总时间开销是 O(n) ,所以这个过程是一个高效的反转算法。

反转链表的代码如下:

1
2
3
4
5
6
7
8
def reverse(self):
p = None
while self._head is not None:
q = self._head
self._head = q.next
q.next = p
p = q
self._head = p

链表反转程序流程

单链表的变形 —— 带尾结点引用的单链表

前面实现的单链表有一个缺点就是尾端加入操作效率低,而实际中可能频繁的在表的两端进行加入元素的操作,一种可能是采用下面的结构,给表的对象增加一个对尾部节点的引用:

尾端加入引用的单链表

这样,对尾部进行加入或删除元素的操作也是 O(1),带尾结点引用的单链表表示方式:

单链表的变形 —— 循环单链表

单链表的另一种变形就是循环单链表,其中最后节点指向首节点。

循环单链表

双向链表

单链表只能支持首端元素的加入/删除和尾端的加入的 O(1) 实现,如果要实现两端的加入/删除的高效操作,就必须修改节点的设计,节点间双向链接不仅支持两端的高效操作,一般节点操作也方便。

支持首端高效操作的双线链接表(双向链表)结构:

双向链表结构

从任意一个一个节点出发,可以直接找到前后的相邻节点,对于单链表,找后面一个节点很简单,但是找前一个节点就必须从头开始逐一检查。

  • 每个节点都需要增加一个前向引用域,指向前一个节点
  • 与前面一样,增加了尾结点的引用,才能实现高效的尾端操作
  • 在双链表里可以直接找到前后节点,因此许多操作变得简单高效

双链表的实现

先定义一下双链表的节点类的实现,由于双链表和单链表的只是增加了一个前向的节点域,所以可以在单链表的基础上进行扩充。

1
2
3
4
class DoubleListNode(ListNode):
def __init__(self, prev, elem):
ListNode.__init__(self,elem)
self.prev = prev

基于带尾结点引用的单链表表派生一个双链表的类

1
2
3
class DoubleLinkList(LinkList):
def __init__(self):
LinkList.__init__(self)

基类的非变动操作都可以继承,无需重新定义(它们不使用 prev 链接域)
对于前后端的节点的加入和删除操作,这两对操作是完全对称的,都能在 O(1) 时间完成。
加入节点的操作:

1
2
def prepend(self, elem):
new_node = DoubleListNode(None, elem)