本文实例讲述了Python单向链表和双向链表原理与用法。分享给大家供大家参考，具体如下：
链表是一种数据结构，链表在循环遍历的时候效率不高，但是在插入和删除时优势比较大。
链表由一个个节点组成。
单向链表的节点分为两个部分：存储的对象和对下一个节点的引用。注意是指向下一个节点。
而双向链表区别于单向链表的是它是由三个部分组成：存储的对象、对下一个节点的引用、对上一个节点的引用，可以实现双向遍历。
单向列表的结构如下图：
head是头节点，tail是尾节点，每个节点由Data存储对象和Next对下一个节点引用组成
下面说一下单向链表插入和删除的过程。
插入一个新节点：
原理：前一个节点的Next指向当前新节点，新节点的Next指向要插入节点位置的后一个节点。
注意：在实际应用时需要考虑插入位置是头结点和尾节点的情况。
删除一个节点：
原理：找到要删除节点的上一个节点，直接上一个节点的Next指向删除位置的下一个节点。
注意：在实际应用中需要考虑到删除的节点是否是头节点或尾节点，需要考虑到链表的长度。
下面附上一个用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
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
|
class Node: next = None data = None def __init__(self,nodeData): self.data = nodeDataclass List: head = None size = 0 def __init__(self): self.size = 0 self.head = None #遍历链表 def a(self): print("avx") def printlist(self): p=self.head while(p is not None): print(p.data) p=p.next print("——————————————————————————————————————") def insertlink(self, a, newdata): newnode = Node(newdata) if self.size == 0: print("The link is none") self.head = newnode self.size = self.size+1 else: p = self.head while(p is not None )and (p.data != a): p = p.next if p.next is None: p.next = newnode self.size = self.size + 1 else: newnode.next = p.next p.next = newnode self.size = self.size + 1 #删除链表中的节点 def deldata(self,a): if self.size == 0: print("The link is none") elif self.size ==1: self.head = None self.size = self.size -1 else: p = self.head while(p is not None )and (p.data != a): q = p p = p.next if p is None: print("Can't find a") elif p == self.head: self.head = p.next elif p.data ==a and p.next is not None: q.next = q.next.next self.size = self.size - 1 else: q.next = None self.size = self.size - 1 #修改链表中的指定节点 def updatelink(self,a,b): p = self.head print(p.data) while(p is not None ) and (p.data!=a): p = p.next if p is None: print("Can't find a") else: p.data = bif __name__=="__main__": p = List() p.insertlink(1,1) p.insertlink(1,2) p.insertlink(1,3) p.insertlink(1,4) print("_________________________---insertlink") p.printlist() print("_________________________--chalink") p.updatelink(2,5) p.printlist() print("___________________________-----dellink") p.deldata(5) p.printlist() |
运行结果：
The link is none
_________________________---insertlink
1
4
3
2
——————————————————————————————————————
_________________________--chalink
1
1
4
3
5
——————————————————————————————————————
___________________________-----dellink
1
4
3
——————————————————————————————————————
双向链表的结构如下图：
head是头节点，tail是尾节点，每个节点由Data存储对象，Next对下一个节点的引用和Pre对上一个节点的引用组成。可以实现双向的遍历
下面说一下双向链表的插入和删除
插入一个新节点：
原理：
找到要插入的节点位置，新节点的Next指向插入位置的下一个节点，插入位置的下一个节点的Pre指向新节点。
插入位置节点的左侧Next指向新节点，新节点的Pre指向左侧的节点。
删除一个节点：
说明：
找到要删除的节点的上一个节点
直接把上一个节点的Next指向要删除节点的下一个节点
并把要删除节点的下一个节点的Pre指向要上出节点的上一个节点即可
双向链表的代码：
|
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
|
class Node(): data = None nextnode = None prenode = None def __init__(self, data): self.data = dataclass PersonChan(): size = 0 head = None tail = None def __init__(self): self.head = None self.tail = None self.size = 0 #增加节点 def add_node(self, a): newnode = Node(a) if(self.head == None): self.head = newnode self.head.prenode = None self.tail = newnode self.tail.prenode = None self.tail.nextnode = None self.size = self.size+1 else: temp = self.head while temp.nextnode is not None:#返回尾节点tail temp = temp.nextnode temp.nextnode = newnode self.tail = newnode self.tail.prenode = temp self.tail.nextnode = None self.size = self.size+1 #在查找到的a后面增加节点 def ins_node(self,a,b): newnode = Node(b) if self.head ==None: self.head = newnode self.tail = newnode print("Insert success:",newnode.data) self.size = self.size +1 else: temp = self.head while(temp is not None)&(temp.data != a): temp = temp.nextnode if temp.nextnode == None: temp.nextnode = newnode self.tail = newnode self.tail.prenode = temp self.tail.nextnode = None temp = None print("Insert success:",newnode.data) self.size = self.size+1 else: newnode.prenode = temp newnode.nextnode = temp.nextnode temp.nextnode = newnode print("Insert success:",newnode.data) self.size = self.size+1 #删除节点 def del_node(self,a): if self.head == None: pass elif self.head.data == a: if self.size ==1: self.head = None self.tail = None self.size = self.size-1 else: self.head = self.head.nextnode self.size = self.size -1 else: temp = self.head.nextnode while (temp is not None) and (temp.data != a): temp = temp.nextnode p = temp.prenode if temp != None: if temp.nextnode == None: self.tail = p self.tail.nextnod = None else: p.nextnode = temp.nextnode temp = None self.size = self.size -1 print("Delete is success:",a) def listall(self):#正序排列 if self.size == 0: print("No data in the list") else: temp = self.head while(temp is not None): print(temp.data) temp = temp.nextnode def lista(self):#倒序排列 if self.size == 0: print("No data in the list") temp = self.tail while(temp is not None): print(temp.data) temp = temp.prenodeif __name__ == '__main__': link = PersonChan() link.add_node(1) link.add_node(2) link.add_node(3) link.add_node(4) link.listall() print("The list's size is:",link.size) link.lista() |
运行结果：
1
2
3
4
("The list's size is:", 4)
4
3
2
1
希望本文所述对大家Python程序设计有所帮助。
原文链接：https://www.cnblogs.com/meitian/p/4584020.html
