Python之链表
在我的记忆里,链表是我在大学时候学 C 和数据结构的时候接触过,后面就很少去碰了,今天突然心血来潮刷一刷 Leetcode,遇到了如下链表的问题:
起初我以为可以当列表来玩(原谅自己是个菜鸟),发现行不通,就去搜索了一下 python 链表相关的知识,找到了一篇写的相对比较齐全的文档,我就厚颜无耻的抄录了。
原始链接:http://zhaochj.github.io/2016/05/12/2016-05-12-数据结构-链表/ (opens new window)
许可协议: "署名-非商用-相同方式共享 4.0" (opens new window) 转载请保留原文链接及作者。
# 介绍
链表是实现了数据之间保持逻辑顺序,但存储空间不必按顺序的方法。可以用一个图来表示这种链表的数据结构:
链表中的基本要素:
- 结点(也可以叫节点或元素),每一个结点有两个域,左边部份叫
值域
,用于存放用户数据;右边叫指针域
,一般是存储着到下一个元素的指针 - head 结点,head 是一个特殊的结节,head 结点永远指向第一个结点
- tail 结点,tail 结点也是一个特殊的结点,tail 结点永远指向最后一个节点
- None,链表中最后一个结点指针域的指针指向 None 值,因也叫
接地点
,所以有些资料上用电气上的接地符号代表 None
链表的常用方法:
- LinkedList() 创建空链表,不需要参数,返回值是空链表
- is_empty() 测试链表是否为空,不需要参数,返回值是布尔值
- append(data) 在尾部增加一个元素作为列表最后一个。参数是要追加的元素,无返回值
- iter() 遍历链表,无参数,无返回值,此方法一般是一个生成器
- insert(idx,value) 插入一个元素,参数为插入元素的索引和值
- remove(idx)移除 1 个元素,参数为要移除的元素或索引,并修改链表
- size() 返回链表的元素数,不需要参数,返回值是个整数
- search(item) 查找链表某元素,参数为要查找的元素或索引,返回是布尔值
# 节点类
python 用类来实现链表的数据结构,节点(Node)是实现链表的基本模块,每个节点至少包括两个重要部分。首先,包括节点自身的数据,称为“数据域”(也叫值域)。其次,每个节点包括下一个节点的“引用”(也叫指针)
下边的代码用于实现一个 Node 类:
class Node:
def __init__(self, data):
self.data = data
self.next = None
2
3
4
此节点类只有一个构建函数,接收一个数据参数,其中next
表示指针域的指针,实例化后得到一个节点对象,如下:
node = Node(4)
此节点对象数据为4
,指针指向 None。
这样一个节点对象可以用一个图例来更形象的说明,如下:
图 2: 节点
# 链表类
先来看 LinkedList 类的构建函数:
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
2
3
4
此类实例后会生成一个链表对象,初始化了head
和tail
节点,且两节点都指向None
,实例化代码如下:
link_list = LinkedList()
也可以用图形象的表示这个链表对象,如下:
图 3:空链表
# is_empty 方法实现
is_empty 方法检查链表是否是一个空链表,这个方法只需要检查head
节点是否指向None
即可,代码如下:
def is_empty(self):
return self.head is None
2
如果是空列表返回True
,否则返回False
# append 方法实现
append 方法表示增加元素到链表,这和 insert 方法不同,前者使新增加的元素成为链表中第一个节点,而后者是根据索引值来判断插入到链表的哪个位置。代码如下:
def append(self, data):
node = Node(data)
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
2
3
4
5
6
7
8
既然要新增加节点,首先把 Node 类实例化得到一个 node 对象。这里有两种情况需要考虑,一是链表是一个空链表时怎样 append 一个节点;二是当链表不是空链表时又怎样 append 一个节点?
当if self.head is None:
为True
时,把链表的head
和tail
都指向了node
,假如我们执行了
link_list(append(4))
此时的链表结构如下图:
图 4:append-1
当if self.head is None:
为False
时,说明链表已经增加了一个节点了,再增加一个节点时head
已经指向了第一个节点,所以不为None
,比如增加的第二个节点为:
link_list(append(5))
2
增加第二个节点的操作需要分两步完成,第一步:self.tail.next = node
,即把上一个节点的next
指针指向当前node
;第二步:self.tail = node
,把tail
移动到node
,如下图:
移动完成后就成这样了:
当增加第三个、第四个等节点时,按照上边的操作依次类推。
# iter 方法实现
iter 方法表示遍历链表。在遍历链表时也要首先考虑空链表的情况。遍历链表时从head
开始,直到一个节点的next
指向None
结束,代码如下:
def iter(self):
if not self.head:
return
cur = self.head
yield cur.data
while cur.next:
cur = cur.next
yield cur.data
2
3
4
5
6
7
8
当是遍历一个空链表时,if not self.head:
为True
,直接返回None
;如果不是空链表就让一个局部变量cur
指向head
,并把head
的data
属性yield
出来,再对cur
的next
指针指向的对象做while
循环,直到next
指向None
,这样就遍历了链表。insert 方法实现
假如采取append
方法又增加了两个节点,增加完成后如下图:
如果想在数据域为6
的那节点处插入一个节点,需要做的操作有两步:
- 把新节点的 next 指针指向数据域为
6
的这个节点,即为数据域为5
节点的 next 指向指向的对象 - 把数据域为
5
节点的 next 指针指向新加的节点
注: 这两个步骤不能颠倒,如果颠倒,数据域为6
的节点会被丢失,数据域为7
的节点不再是链表的节点。
示意图如下:
还要额外考虑两种情况:
- 空链表时
- 插入位置超出链表节点的长度时
- 插入位置是链表的最后一个节点时,需要移动 tail
当是在链表最后一个节点插入时,示意图如下:
要在指定的索引位置插入一个节点,前提是需要找到这个位置,在链表中只有采用遍历的方式,具有 O(n)的速度,最糟糕时会遍历链表的所有节点,而当找到插入点时,我们并不需要当前节点的信息,而是需要前一个节点的信息,所以代码中巧妙的使用了while cur_idx < idx-1:
的方式,这样能使用cur
这个变量能指向插入点上一个节点对象。
实现insert
方法的代码如下:
def insert(self, idx, value):
cur = self.head
cur_idx = 0
if cur is None:
raise Exception('The list is an empty list')
while cur_idx < idx-1:
cur = cur.next
if cur is None:
raise Exception('list length less than index')
cur_idx += 1
node = Node(value)
node.next = cur.next
cur.next = node
if node.next is None:
self.tail = node
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# remove 方法实现
remove 方法接收一个 idx 参数,表示要删除节点的索引,此方法要考虑以下几种情况:
- 空链表,直接抛出异常
- 删除第一个节点时,移动 head 到删除节点的 next 指针指向的对象
- 链表只有一个节点时,把 head 与 tail 都指向 None 即可
- 删除最后一个节点时,需要移动 tail 到上一个节点
- 遍历链表时要判断给定的索引是否大于链表的长度,如果大于则抛出异常信息
请看下边图例:
以下为 remove 函数的代码:
def remove(self, idx):
cur = self.head
cur_idx = 0
if self.head is None: # 空链表时
raise Exception('The list is an empty list')
while cur_idx < idx-1:
cur = cur.next
if cur is None:
raise Exception('list length less than index')
cur_idx += 1
if idx == 0: # 当删除第一个节点时
self.head = cur.next
cur = cur.next
return
if self.head is self.tail: # 当只有一个节点的链表时
self.head = None
self.tail = None
return
cur.next = cur.next.next
if cur.next is None: # 当删除的节点是链表最后一个节点时
self.tail = cur
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# size 函数实现
size 函数不接收参数,返回链表中节点的个数,要获得链表的节点个数,必定会遍历链表,直到最后一个节点的next
指针指向None
时链表遍历完成,遍历时可以用一个累加器来计算节点的个数,如下代码:
def size(self):
current = self.head
count = 0
if current is None:
return 'The list is an empty list'
while current is not None:
count += 1
current = current.next
return count
2
3
4
5
6
7
8
9
# search 函数实现
search 函数接收一个 item 参数,表示查找节点中数据域的值。search 函数遍历链表,每到一个节点把当前节点的data
值与item
作比较,最糟糕的情况下会全遍历链表。如果查找到有些数据则返回True
,否则返回False
,代码如下:
def search(self, item):
current = self.head
found = False
while current is not None and not found:
if current.data == item:
found = True
else:
current = current.next
return found
2
3
4
5
6
7
8
9
# Node 类与 LinkedList 类完整代码
最后把Node类
和LinkedList类
的完整代码整理如下:
Node 类:
class Node:
def __init__(self, data):
self.data = data
self.next = None
2
3
4
LinkedList 类及调度代码:
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
return self.head is None
def append(self, data):
node = Node(data)
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def iter(self):
if not self.head:
return
cur = self.head
yield cur.data
while cur.next:
cur = cur.next
yield cur.data
def insert(self, idx, value):
cur = self.head
cur_idx = 0
if cur is None: # 判断是否是空链表
raise Exception('The list is an empty list')
while cur_idx < idx-1: # 遍历链表
cur = cur.next
if cur is None: # 判断是不是最后一个元素
raise Exception('list length less than index')
cur_idx += 1
node = Node(value)
node.next = cur.next
cur.next = node
if node.next is None:
self.tail = node
def remove(self, idx):
cur = self.head
cur_idx = 0
if self.head is None: # 空链表时
raise Exception('The list is an empty list')
while cur_idx < idx-1:
cur = cur.next
if cur is None:
raise Exception('list length less than index')
cur_idx += 1
if idx == 0: # 当删除第一个节点时
self.head = cur.next
cur = cur.next
return
if self.head is self.tail: # 当只有一个节点的链表时
self.head = None
self.tail = None
return
cur.next = cur.next.next
if cur.next is None: # 当删除的节点是链表最后一个节点时
self.tail = cur
def size(self):
current = self.head
count = 0
if current is None:
return 'The list is an empty list'
while current is not None:
count += 1
current = current.next
return count
def search(self, item):
current = self.head
found = False
while current is not None and not found:
if current.data == item:
found = True
else:
current = current.next
return found
if __name__ == '__main__':
link_list = LinkedList()
for i in range(150):
link_list.append(i)
# print(link_list.is_empty())
# link_list.insert(10, 30)
# link_list.remove(0)
for node in link_list.iter():
print('node is {0}'.format(node))
print(link_list.size())
# print(link_list.search(20))
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
然后我们上面那个问题就可以解决了,
- 从头遍历两个链表,将它们的值进行相加,如果其中有一个链表为 None,其值为 0
- 用一个参数来记录其进位,进位的标准为 1 或者 0,如果相加的和大于 10,则进位为 1,反之为 0
- 每做完一次相加,就将两个链表前进一位
代码如下:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
# 定义一个进位标志
carry = 0
# 定义一个tmp用来存储计算结果
res = ListNode(0)
tmp = res
# 循环条件为l1或者l2不为空
while l1 or l2:
# 取值计算结果
val = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
# 计算上面的计算结果是否有进位
carry,val = val//10,val%10
# 存储值
tmp.next=ListNode(val)
tmp=tmp.next
# 将l1和l2前进一位
l1,l2 = l1.next if l1 else None,l2.next if l2 else None
# 处理最后carry>0的情况
if carry>0:
tmp.next = ListNode(1)
return res.next
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
作者:
本文链接:https://jokerbai.com
版权声明:本博客所有文章除特别声明外,均采用 署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0) 许可协议。转载请注明出处!
- 02
- 使用Zadig从0到1实现持续交付平台07-19
- 03
- 基于Jira的运维发布平台07-19