Python实现单链表，双链表，单循环链表，双循环链表

描述：用Python实现单链表，双链表，单循环链表，双循环链表

单链表的实现（链表的基本方法）：

  1 # _*_ coding: utf-8 _*_
  2 # Filename: singlelinklist
  3 # Function: create linklist datastructure
  4 # Author: Latup
  5 
  6 
  7 class Node():
  8     """define the node of linklist"""
  9 
 10     def __init__(self, data=None, next=None):
 11         self.data = data
 12         self.next = next
 13 
 14 
 15 class LinkList():
 16     """define class of linklist"""
 17 
 18     def __init__(self):
 19         self.head = Node()
 20         self.length = 0
 21 
 22     def init_linklist(self, data):
 23         """initial linklist"""
 24 
 25         p = self.head
 26         for i in data:
 27             node = Node(i)
 28             p.next = node
 29             p = p.next
 30             self.length += 1
 31 
 32     def isEmpty(self):
 33         """Determine if the linklist is empty"""
 34         return self.length == 0
 35 
 36     def insert(self, _index, data):
 37         """Insert an element into the linklist"""
 38 
 39         if _index < 1 or _index > self.length+1:
 40             print('IndexError: out of index, fail to insert')
 41             return
 42         p = self.head
 43         node = Node(data)
 44         count = 0
 45         while count < _index-1:
 46             p = p.next
 47             count += 1
 48         node.next = p.next
 49         p.next = node
 50         self.length += 1
 51 
 52     def delt(self, _index):
 53         """Delete the value of the element corresponding to _index"""
 54 
 55         if _index < 1 or _index > self.length:
 56             print('IndexError: out of index, fail to delt')
 57             return
 58         p = self.head
 59         count = 0
 60         while count < _index-1:
 61             p = p.next
 62             count += 1
 63         p.next = p.next.next
 64         self.length -= 1
 65 
 66     def node_updata(self, _index, data):
 67         """Replace the value of the element corresponding to _index with data"""
 68 
 69         if _index < 1 or _index > self.length:
 70             print('IndexError: out of index, fail to updata')
 71             return
 72         p = self.head.next
 73         count = 1
 74         while count < _index:
 75             p = p.next
 76             count += 1
 77         p.data = data
 78 
 79     def getItem(self, _index):
 80         """Get the value of the element corresponding to _index"""
 81 
 82         if _index < 1 or _index > self.length:
 83             print('IndexError: out of index, fail to getitem')
 84             return
 85         p = self.head.next
 86         count = 1
 87         while count < _index:
 88             p = p.next
 89             count += 1
 90         return p.data
 91 
 92     def getIndex(self, data):
 93         """Get the index of the element data"""
 94 
 95         if self.isEmpty():
 96             print('the linklist is empyt, fail to getindex')
 97             return
 98         p = self.head.next
 99         count = 1
100         while p and p.data != data:
101             p = p.next
102             count += 1
103         if count == self.length+1:
104             print('%s not found' % str(data))
105             return
106         else:
107             return count
108 
109     def traverse_linklist(self):
110         """Traversing the linklist"""
111 
112         p = self.head.next
113         if p == None:
114             print('empty linklist')   
115         while p:
116             print(p.data, end=' ')
117             p = p.next
118 
119     def reverse_linklist(self):       # reverse_linklist()是一个生成器函数，而不是普通函数
120         pre = None
121         _next = None
122         p = self.head.next
123         while p:
124             _next = p.next
125             p.next = pre
126             pre = p
127             p = _next
128         self.head.next = pre
129 
130         p = self.head.next
131         while p:
132             yield p.data
133             p = p.next

双链表的实现（双链表在结点定义、初始化链表和插入删除上和单链表稍有不同）：

 1 class Node:
 2     """define the node of linklist"""
 3 
 4     def __init__(self, data=None, prior=None, next=None):
 5         self.data = data
 6         self.prior_item = prior
 7         self.next_item = next
 8 
 9 
10 def init_linklist(self, data):
11     """initial linklist"""
12     p = self.head
13     for i in data:
14         node = Node(i, prior=p)
15         p.next_item = node
16         p = p.next_item
17         self.length += 1
18 
19 def insert(self, _index, data):
20     """Insert an element into the linklist"""
21     if _index < 1 or _index > self.length+1:
22         print('IndexError: out of index, fail to insert')
23         return
24     p = self.head
25     node = Node(data)
26     count = 0
27     while count < _index-1:
28         p = p.next_item
29         count += 1
30     node.next_item = p.next_item
31     p.next_item = node
32     node.prior_item = p
33     if node.next_item != None:
34         node.next_item.prior_item = node
35     self.length += 1
36 
37 def delt(self, _index):
38     """Delete the value of the element corresponding to _index"""
39     if _index < 1 or _index > self.length:
40         print('IndexError: out of index, fail to delete')
41         return
42     p = self.head
43     count = 0
44     while count < _index-1:
45         p = p.next_item
46         count += 1
47     p.next_item = p.next_item.next_item
48     p.next_item.prior_item = p
49     self.length -= 1

单循环链表的实现（需要修改初始化和插入方法）：

 1 def init_linklist(self, data):
 2     """initial linklist"""
 3     p = self.head
 4     for i in data:
 5         node = Node(i, next=self.head)
 6         p.next_item = node
 7         p = p.next_item
 8         self.length += 1
 9 
10 def insert(self, _index, data):
11     """Insert an element into the linklist"""
12     if _index < 1 or _index > self.length+1:
13         print('IndexError: out of index, fail to insert')
14         return
15     p = self.head
16     node = Node(data)
17     count = 0
18     while count < _index-1:
19         p = p.next_item
20         count += 1
21     node.next_item = p.next_item
22     # If the inserted position is the end of the linklist
23     if node.next_item == None:
24         node.next_item = self.head
25     p.next_item = node
26     self.length += 1

双循环链表的实现（修改初始化和插入方法）：

 1 def init_linklist(self, data):
 2     """initial linklist"""
 3     p = self.head
 4     for i in data:
 5         node = Node(i, prior=p, next=self.head)
 6         p.next_item = node
 7         p = p.next_item
 8         self.head.prior_item = node
 9         self.length += 1
10 
11 def insert(self, _index, data):
12     """Insert an element into the linklist"""
13     if _index < 1 or _index > self.length+1:
14         print('IndexError: out of index, fail to insert')
15         return
16     p = self.head
17     node = Node(data)
18     count = 0
19     while count < _index-1:
20         p = p.next_item
21         count += 1
22     node.next_item = p.next_item
23     p.next_item = node
24     node.prior_item = p
25     # If the inserted position is the end of the linklist
26     if node.next_item == None:
27         node.next_item = self.head
28         self.head.prior_item = node
29     self.length += 1