data structure

1
2
3



	单向循环链表拥有值域和后继节点域，后继节点域记录下一个节点的位置，
	
	最后一个节点的next域指向第一个节点。

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



	class Node(object):
	节点
	def __init__(self,elem):
		self.elem = elem
		self.next = None

	class SingleLinkList(object):
		单链表
		def __init__(self,node=None):
			self._head=node
			if node:
				node.next = node
		def is_empty(self):
			return self._head ==None
		def length(self):
			if self.is_empty():
				return 0
			cur  = self._head
			count =  1
			while cur.next !=self._head:
				count+=1
				cur = cur.next
			return count
		遍历列表
		def travel(self):
			if self.is_empty():
				return None
			cur = self._head
			while cur.next !=self._head:
				print(cur.elem,end=" ")
				cur = cur.next
			print(cur.elem)

		头添加
		def add(self,item):
			node = Node(item)
			if self.is_empty():
				self._head = node
				node.next = node
			else:
				cur = self._head
				while cur.next !=self._head:
					cur=cur.next
				node.next = self._head
				self._head = node
				cur.next = self._head
		尾添加元素 尾插法
		def append(self,item):
			node = Node(item)
			if self.is_empty():
				self._head=node
				node.next = node
			else:
				cur = self._head
				while cur.next !=self._head:
					cur = cur.next
				cur.next =node
				node.next = self._head
		指定位置添加
		def insert(self,pos,item):
			'''只想位置'''
			if pos <= 0:
				self.add(item)
			elif pos >(self.length()-1):
				self.append(item)
			else:
				pre=self._head
				count=0
				while count <(pos-1):
					count+=1
					pre = pre.next
				node = Node(item)
				node.next = pre.next
				pre.next = node

		删除节点
		def remove(self,item):
			if self.is_empty():
				return
			cur = self._head
			pre = None
			while cur.next!=self._head:
				if cur.elem ==item:
					if cur == self._head:
						rear = self._head
						while rear.next!=self._head:
							rear = rear.next
						self._head =cur.next
						rear.next = self._head
					else:
						pre.next = cur.next
					return 
				else:
					pre = cur
					cur = cur.next
			if cur.elem ==item:
				if cur ==self._head:
					self._head = None
				else:
					pre.next = cur.next


		查找节点是否存在
		def search(self,item):
			if self.is_empty():
				return False
			cur = self._head
			while cur.next !=self._head:
				if cur.elem == item:
					return True
				else:
					cur = cur.next
			if cur.elem ==item:
				return True
			return False

	if __name__ == "__main__":
		ll = SingleLinkList()
		print(ll.is_empty())
		print(ll.length())
		ll.append(1)
		print(ll.is_empty())
		print(ll.length())
		ll.append(2)
		ll.add(8)
		ll.append(3)
		ll.append(4)
		ll.insert(2,100)
		ll.append(5)
		ll.travel()
		ll.remove(8)
		ll.travel()