一、链表简介
链表是一种在存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现。链表是由一系列的结点组成，结点可以在运行时动态生成。每个结点包含两部分：数据域与指针域。数据域存储数据元素，指针域存储下一结点的指针。
二、单向链表
单向链表也叫单链表，是链表中最简单的形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
head 保存首地址，item 存储数据，next 指向下一结点地址。
链表失去了序列的随机读取优点，同时链表增加了指针域，空间开销也较大，但它对存储空间的使用要相对灵活。
列如：有一堆数据[1,2,3,5,6,7]，要在3和5之间插入4, 如果用数组，需要将5之后的数据都往后退一位，然后再插入4，这样非常麻烦，但是如果用链表，我就直接在3和5之间插入4就行。
1. 定义结点
结点的数据结构为数据元素(item)与 指针(next)
1
2
3
4
5
6
7
8
|
class Node(object):
"""单链表的结点"""
def __init__(self, item):
# item存放数据元素
self.item = item
# next是下一个节点的标识
self.next = None
|
2. 定义链表
链表需要具有首地址指针head。
1
2
3
4
5
|
class SingleLinkList(object):
"""单链表"""
def __init__(self):
self._head = None
|
示例：创建链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
if __name__ == '__main__':
# 创建链表
link_list = SingleLinkList()
# 创建结点
node1 = Node(1)
node2 = Node(2)
# 将结点添加到链表
link_list._head = node1
# 将第一个结点的next指针指向下一结点
node1.next = node2
# 访问链表
print(link_list._head.item) # 访问第一个结点数据
print(link_list._head.next.item) # 访问第二个结点数据
|
是不是感觉很麻烦，所以我们要在链表中增加操作方法。
- is_empty() 链表是否为空
- length() 链表长度
- items() 获取链表数据迭代器
- add(item) 链表头部添加元素
- append(item) 链表尾部添加元素
- insert(pos, item) 指定位置添加元素
- remove(item) 删除节点
- find(item) 查找节点是否存在
代码如下：
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
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
|
class SingleLinkList(object):
"""单链表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head is None
def length(self):
"""链表长度"""
# 初始指针指向head
cur = self._head
count = 0
# 指针指向None 表示到达尾部
while cur is not None:
count += 1
# 指针下移
cur = cur.next
return count
def items(self):
"""遍历链表"""
# 获取head指针
cur = self._head
# 循环遍历
while cur is not None:
# 返回生成器
yield cur.item
# 指针下移
cur = cur.next
def add(self, item):
"""向链表头部添加元素"""
node = Node(item)
# 新结点指针指向原头部结点
node.next = self._head
# 头部结点指针修改为新结点
self._head = node
def append(self, item):
"""尾部添加元素"""
node = Node(item)
# 先判断是否为空链表
if self.is_empty():
# 空链表，_head 指向新结点
self._head = node
else:
# 不是空链表，则找到尾部，将尾部next结点指向新结点
cur = self._head
while cur.next is not None:
cur = cur.next
cur.next = node
def insert(self, index, item):
"""指定位置插入元素"""
# 指定位置在第一个元素之前，在头部插入
if index <= 0:
self.add(item)
# 指定位置超过尾部，在尾部插入
elif index > (self.length() - 1):
self.append(item)
else:
# 创建元素结点
node = Node(item)
cur = self._head
# 循环到需要插入的位置
for i in range(index - 1):
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
"""删除节点"""
cur = self._head
pre = None
while cur is not None:
# 找到指定元素
if cur.item == item:
# 如果第一个就是删除的节点
if not pre:
# 将头指针指向头节点的后一个节点
self._head = cur.next
else:
# 将删除位置前一个节点的next指向删除位置的后一个节点
pre.next = cur.next
return True
else:
# 继续按链表后移节点
pre = cur
cur = cur.next
def find(self, item):
"""查找元素是否存在"""
return item in self.items()
|
示例：操作链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
if __name__ == '__main__':
link_list = SingleLinkList()
# 向链表尾部添加数据
for i in range(5):
link_list.append(i)
# 向头部添加数据
link_list.add(6)
# 遍历链表数据
for i in link_list.items():
print(i, end='\t')
# 链表数据插入数据
link_list.insert(3, 9)
print('\n', list(link_list.items()))
# 删除链表数据
link_list.remove(0)
# 查找链表数据
print(link_list.find(4))
|
三、循环链表
单向循环链表为单向链表的变种，链表的最后一个next指向链表头，新增一个循环。
1. 循环链表结点
1
2
3
4
5
6
7
8
|
class Node(object):
"""链表的结点"""
def __init__(self, item):
# item存放数据元素
self.item = item
# next是下一个节点的标识
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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
class SingleCycleLinkList(object):
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head is None
def length(self):
"""链表长度"""
# 链表为空
if self.is_empty():
return 0
# 链表不为空
count = 1
cur = self._head
while cur.next != self._head:
count += 1
# 指针下移
cur = cur.next
return count
def items(self):
""" 遍历链表 """
# 链表为空
if self.is_empty():
return
# 链表不为空
cur = self._head
while cur.next != self._head:
yield cur.item
cur = cur.next
yield cur.item
def add(self, item):
""" 头部添加结点"""
node = Node(item)
if self.is_empty(): # 为空
self._head = node
node.next = self._head
else:
# 添加结点指向head
node.next = self._head
cur = self._head
# 移动结点，将末尾的结点指向node
while cur.next != self._head:
cur = cur.next
cur.next = node
# 修改 head 指向新结点
self._head = node
def append(self, item):
"""尾部添加结点"""
node = Node(item)
if self.is_empty(): # 为空
self._head = node
node.next = self._head
else:
# 寻找尾部
cur = self._head
while cur.next != self._head:
cur = cur.next
# 尾部指针指向新结点
cur.next = node
# 新结点指针指向head
node.next = self._head
def insert(self, index, item):
""" 指定位置添加结点"""
if index <= 0: # 指定位置小于等于0，头部添加
self.add(item)
# 指定位置大于链表长度，尾部添加
elif index > self.length() - 1:
self.append(item)
else:
node = Node(item)
cur = self._head
# 移动到添加结点位置
for i in range(index - 1):
cur = cur.next
# 新结点指针指向旧结点
node.next = cur.next
# 旧结点指针 指向 新结点
cur.next = node
def remove(self, item):
""" 删除一个结点 """
if self.is_empty():
return
cur = self._head
pre = Node
# 第一个元素为需要删除的元素
if cur.item == item:
# 链表不止一个元素
if cur.next != self._head:
while cur.next != self._head:
cur = cur.next
# 尾结点指向 头部结点的下一结点
cur.next = self._head.next
# 调整头部结点
self._head = self._head.next
else:
# 只有一个元素
self._head = None
else:
# 不是第一个元素
pre = self._head
while cur.next != self._head:
if cur.item == item:
# 删除
pre.next = cur.next
return True
else:
pre = cur # 记录前一个指针
cur = cur.next # 调整指针位置
# 当删除元素在末尾
if cur.item == item:
pre.next = self._head
return True
def find(self, item):
""" 查找元素是否存在"""
return item in self.items()
if __name__ == '__main__':
link_list = SingleCycleLinkList()
print(link_list.is_empty())
# 头部添加元素
for i in range(5):
link_list.add(i)
print(list(link_list.items()))
# 尾部添加元素
for i in range(6):
link_list.append(i)
print(list(link_list.items()))
# 添加元素
link_list.insert(3, 45)
print(list(link_list.items()))
# 删除元素
link_list.remove(5)
print(list(link_list.items()))
# 元素是否存在
print(4 in link_list.items())
|
四、双向链表
双向链表比单向链表更加复杂，它每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个链接指向下一个节点，当此节点为最后一个节点时，指向空值。
head 保存首地址，item 存储数据，next 指向下一结点地址，prev 指向上一结点地址。
1. 定义双向链表结点
1
2
3
4
5
6
7
8
9
10
11
|
class Node(object):
"""双向链表的结点"""
def __init__(self, item):
# item存放数据元素
self.item = item
# next 指向下一个节点的标识
self.next = None
# prev 指向上一结点
self.prev = None
|
2. 定义双向链表
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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
class BilateralLinkList(object):
"""双向链表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head is None
def length(self):
"""链表长度"""
# 初始指针指向head
cur = self._head
count = 0
# 指针指向None 表示到达尾部
while cur is not None:
count += 1
# 指针下移
cur = cur.next
return count
def items(self):
"""遍历链表"""
# 获取head指针
cur = self._head
# 循环遍历
while cur is not None:
# 返回生成器
yield cur.item
# 指针下移
cur = cur.next
def add(self, item):
"""向链表头部添加元素"""
node = Node(item)
if self.is_empty():
# 头部结点指针修改为新结点
self._head = node
else:
# 新结点指针指向原头部结点
node.next = self._head
# 原头部 prev 指向 新结点
self._head.prev = node
# head 指向新结点
self._head = node
def append(self, item):
"""尾部添加元素"""
node = Node(item)
if self.is_empty(): # 链表无元素
# 头部结点指针修改为新结点
self._head = node
else: # 链表有元素
# 移动到尾部
cur = self._head
while cur.next is not None:
cur = cur.next
# 新结点上一级指针指向旧尾部
node.prev = cur
# 旧尾部指向新结点
cur.next = node
def insert(self, index, item):
""" 指定位置插入元素"""
if index <= 0:
self.add(item)
elif index > self.length() - 1:
self.append(item)
else:
node = Node(item)
cur = self._head
for i in range(index):
cur = cur.next
# 新结点的向下指针指向当前结点
node.next = cur
# 新结点的向上指针指向当前结点的上一结点
node.prev = cur.prev
# 当前上一结点的向下指针指向node
cur.prev.next = node
# 当前结点的向上指针指向新结点
cur.prev = node
def remove(self, item):
""" 删除结点 """
if self.is_empty():
return
cur = self._head
# 删除元素在第一个结点
if cur.item == item:
# 只有一个元素
if cur.next is None:
self._head = None
return True
else:
# head 指向下一结点
self._head = cur.next
# 下一结点的向上指针指向None
cur.next.prev = None
return True
# 移动指针查找元素
while cur.next is not None:
if cur.item == item:
# 上一结点向下指针指向下一结点
cur.prev.next = cur.next
# 下一结点向上指针指向上一结点
cur.next.prev = cur.prev
return True
cur = cur.next
# 删除元素在最后一个
if cur.item == item:
# 上一结点向下指针指向None
cur.prev.next = None
return True
def find(self, item):
"""查找元素是否存在"""
return item in self.items()
|
Reference
1、 https://zhuanlan.zhihu.com/p/60057180
打赏
微信
|
支付宝
|
| 万分感谢 |
|