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()

 1 """
 2 双向链表
 3 """
 4 import sys
 5 import collections
 6 
 7 # 双向链表的节点类
 8 class Node(object):
 9     def __init__(self, data):
10         self.data = data
11         self.next = None
12         self.prev = None
13 
14 
15 # 双向链表类
16 class DoubleLinkedList(object):
17     def __init__(self):
18         self.head = None
19 
20     def push(self, newdata):
21         """
22         尾插法插入数据,也就是向链表的结尾追加元素
23         param@newdata: 新插入的数据，为Node类的实例对象的data
24         """
25         newdata = Node(newdata)
26         if self.head == None:
27             self.head = newdata
28         elif self.head.next == None:
29             newdata.next = self.head.next
30             self.head.next = newdata
31             newdata.prev = self.head
32         else:
33             data = self.head
34             while data.next:
35                 data = data.next
36             newdata.next = data.next
37             data.next = newdata
38             newdata.prev = data
39             
40     # 正向打印出链表值的函数
41     def listprint(self):
42         data = self.head
43         while data is not None:
44             print(data.data, end=' ')
45             data = data.next
46         print()
47 
48     # # 反向打印出链表值的函数
49     def listprint_2(self):
50         data = self.head
51         while data.next:
52             data = data.next
53         while data is not None:
54             print(data.data, end=' ')
55             data = data.prev
56         print()
57 
58     def insert(self, prev_node, newdata):
59         """
60         在链表的一个节点后插入一个节点
61         param@prev_node: 要插入节点的前一个节点
62         param@newdata: 插入的节点的值，为Node类实例对象的data
63         """
64         newdata = Node(newdata)
65         if prev_node is None:
66             return
67         elif prev_node.next is None:
68             newdata.next = prev_node.next
69             prev_node.next = newdata
70             newdata.prev = prev_node
71         else:
72             prev_node.next.prev = newdata
73             newdata.prev = prev_node
74             newdata.next = prev_node.next
75             prev_node.next = newdata
76         
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()