参考【易百教程】用Python实现链表及其功能
1 """ 2 python链表的基本操作：节点、链表、增删改查 3 """ 4 import sys 5 6 class Node(object): 7 """ 8 节点类，实例化后的对象用来表示链表中的一个节点 9 """ 10 def __init__(self, dataval=None): 11 self.dataval = dataval 12 self.nextval = None 13 14 15 class SLinkedList(object): 16 """ 17 链表类，用于初始化一个链表，及多链表的一些操作 18 """ 19 def __init__(self): 20 self.headval = None 21 22 def listprint(self): 23 """ 24 打印链表 25 """ 26 val = self.headval 27 while val is not None: 28 print(val.dataval, end=' ') 29 val = val.nextval 30 print() 31 32 def insertStart(self, newdata): 33 """ 34 从链表头插入一个节点 35 param@newdata: 插入的新节点，为Node类实例对象的dataval 36 """ 37 newdata = Node(newdata) 38 newdata.nextval = self.headval 39 self.headval = newdata 40 41 def insertEnd(self, newdata): 42 """ 43 从链表尾部插入一个节点 44 param@newdata: 插入的新节点，为Node类实例对象的dataval 45 """ 46 newdata = Node(newdata) 47 if self.headval == None: 48 self.headval = newdata 49 return 50 else: 51 temp = self.headval 52 while temp.nextval: 53 temp = temp.nextval 54 temp.nextval = newdata 55 56 def insertBetween(self, node, newdata): 57 """ 58 在链表的node节点后插入一个新元素 59 param@node: 链表中的一个节点，新插入的元素将插入其后面 60 param@newdata: 插入的新节点，为Node类实例对象的dataval 61 """ 62 if (not node) or node == None: 63 raise Exception('参数异常！') 64 else: 65 newdata = Node(newdata) 66 newdata.nextval = node.nextval 67 node.nextval = newdata 68 69 def removeNode(self, node_val): 70 """ 71 从链表中删除值为node_val的节点 72 param@node_val: 被删除节点的值，即Node类实例对象的dataval 73 """ 74 if self.headval == None: 75 print('链表为空链表！') 76 else: 77 if self.headval.nextval == None: 78 if self.headval == node_val: 79 sefl.headval = None 80 else: 81 return 82 else: 83 temp = self.headval 84 if temp.dataval == node_val: 85 self.headval = temp.nextval 86 else: 87 temp = self.headval 88 while temp.nextval: 89 if temp.nextval.dataval == node_val: 90 temp.nextval = temp.nextval.nextval 91 break 92 temp = temp.nextval 93 94 95 96 97 98 li = SLinkedList() 99 e1 = Node('one')100 e2 = Node('two')101 e3 = Node('three')102 li.headval = e1 103 e1.nextval = e2 104 e2.nextval = e3 105 li.listprint() 以上为单向链表一些基本操作的Python实现，接下来也展示一下双向链表的一些简单实现
1 """ 2 双向链表 3 """ 4 import sys 5 import collections 6 7 # 双向链表的节点类 8 class Node(object): 9 def __init__(self, data):10 self.data = data11 self.next = None12 self.prev = None13 14 15 # 双向链表类16 class DoubleLinkedList(object):17 def __init__(self):18 self.head = None19 20 def push(self, newdata):21 """22 尾插法插入数据,也就是向链表的结尾追加元素23 param@newdata: 新插入的数据，为Node类的实例对象的data24 """25 newdata = Node(newdata)26 if self.head == None:27 self.head = newdata28 elif self.head.next == None:29 newdata.next = self.head.next30 self.head.next = newdata31 newdata.prev = self.head32 else:33 data = self.head34 while data.next:35 data = data.next36 newdata.next = data.next37 data.next = newdata38 newdata.prev = data39 40 # 正向打印出链表值的函数41 def listprint(self):42 data = self.head43 while data is not None:44 print(data.data, end=' ')45 data = data.next46 print()47 48 # # 反向打印出链表值的函数49 def listprint_2(self):50 data = self.head51 while data.next:52 data = data.next53 while data is not None:54 print(data.data, end=' ')55 data = data.prev56 print()57 58 def insert(self, prev_node, newdata):59 """60 在链表的一个节点后插入一个节点61 param@prev_node: 要插入节点的前一个节点62 param@newdata: 插入的节点的值，为Node类实例对象的data63 """64 newdata = Node(newdata)65 if prev_node is None:66 return67 elif prev_node.next is None:68 newdata.next = prev_node.next69 prev_node.next = newdata70 newdata.prev = prev_node71 else:72 prev_node.next.prev = newdata73 newdata.prev = prev_node74 newdata.next = prev_node.next75 prev_node.next = newdata76 77 78 79 dlist = DoubleLinkedList()80 dlist.push('one')81 dlist.push('two')82 dlist.push('three')83 dlist.insert(dlist.head, 'hhh')84 dlist.listprint()85 dlist.listprint_2() 暂时到这里