python 数据结构之单链表的实现（别人的成果）

瞬秒爆加速

原文地址：http://www.cnblogs.com/yupeng/p/3413763.html#3103095

链表的定义：

　　链表(linked list)是由一组被称为结点的数据元素组成的数据结构，每个结点都包含结点本身的信息和指向下一个结点的地址。由于每个结点都包含了可以链接起来的地址信息，所以用一个变量就能够访问整个结点序列。也就是说，结点包含两部分信息：一部分用于存储数据元素的值，称为信息域；另一部分用于存储下一个数据元素地址的指针，称为指针域。链表中的第一个结点的地址存储在一个单独的结点中，称为头结点或首结点。链表中的最后一个结点没有后继元素，其指针域为空。　　

如下图所示：

                               
登录/注册后可看大图

单链表的结构：

                               
登录/注册后可看大图

单链表的插入和删除示意图：

                               
登录/注册后可看大图

1. #!/usr/bin/python
   
2. # -*- coding: utf-8 -*-
   
3. 
   
4. class Node(object):
   
5.     def __init__(self,val,p=0):
   
6.         self.data = val
   
7.         self.next = p
   
8. 
   
9. class LinkList(object):
   
10.     def __init__(self):
    
11.         self.head = 0
    
12. 
    
13.     def __getitem__(self, key):
    
14. 
    
15.         if self.is_empty():
    
16.             print 'linklist is empty.'
    
17.             return
    
18. 
    
19.         elif key <0  or key > self.getlength():
    
20.             print 'the given key is error'
    
21.             return
    
22. 
    
23.         else:
    
24.             return self.getitem(key)
    
25. 
    
26. 
    
27. 
    
28.     def __setitem__(self, key, value):
    
29. 
    
30.         if self.is_empty():
    
31.             print 'linklist is empty.'
    
32.             return
    
33. 
    
34.         elif key <0  or key > self.getlength():
    
35.             print 'the given key is error'
    
36.             return
    
37. 
    
38.         else:
    
39.             self.delete(key)
    
40.             return self.insert(key)
    
41. 
    
42.     def initlist(self,data):
    
43. 
    
44.         self.head = Node(data[0])
    
45. 
    
46.         p = self.head
    
47. 
    
48.         for i in data[1:]:
    
49.             node = Node(i)
    
50.             p.next = node
    
51.             p = p.next
    
52. 
    
53.     def getlength(self):
    
54. 
    
55.         p =  self.head
    
56.         length = 0
    
57.         while p!=0:
    
58.             length+=1
    
59.             p = p.next
    
60. 
    
61.         return length
    
62. 
    
63.     def is_empty(self):
    
64. 
    
65.         if self.getlength() ==0:
    
66.             return True
    
67.         else:
    
68.             return False
    
69. 
    
70.     def clear(self):
    
71. 
    
72.         self.head = 0
    
73. 
    
74. 
    
75.     def append(self,item):
    
76. 
    
77.         q = Node(item)
    
78.         if self.head ==0:
    
79.             self.head = q
    
80.         else:
    
81.             p = self.head
    
82.             while p.next!=0:
    
83.                 p = p.next
    
84.             p.next = q
    
85. 
    
86. 
    
87.     def getitem(self,index):
    
88. 
    
89.         if self.is_empty():
    
90.             print 'Linklist is empty.'
    
91.             return
    
92.         j = 0
    
93.         p = self.head
    
94. 
    
95.         while p.next!=0 and j <index:
    
96.             p = p.next
    
97.             j+=1
    
98. 
    
99.         if j ==index:
    
100.             return p.data
     
101. 
     
102.         else:
     
103. 
     
104.             print 'target is not exist!'
     
105. 
     
106.     def insert(self,index,item):
     
107. 
     
108.         if self.is_empty() or index<0 or index >self.getlength():
     
109.             print 'Linklist is empty.'
     
110.             return
     
111. 
     
112.         if index ==0:
     
113.             q = Node(item,self.head)
     
114. 
     
115.             self.head = q
     
116. 
     
117.         p = self.head
     
118.         post  = self.head
     
119.         j = 0
     
120.         while p.next!=0 and j<index:
     
121.             post = p
     
122.             p = p.next
     
123.             j+=1
     
124. 
     
125.         if index ==j:
     
126.             q = Node(item,p)
     
127.             post.next = q
     
128.             q.next = p
     
129. 
     
130. 
     
131.     def delete(self,index):
     
132. 
     
133.         if self.is_empty() or index<0 or index >self.getlength():
     
134.             print 'Linklist is empty.'
     
135.             return
     
136. 
     
137.         if index ==0:
     
138.             q = Node(item,self.head)
     
139. 
     
140.             self.head = q
     
141. 
     
142.         p = self.head
     
143.         post  = self.head
     
144.         j = 0
     
145.         while p.next!=0 and j<index:
     
146.             post = p
     
147.             p = p.next
     
148.             j+=1
     
149. 
     
150.         if index ==j:
     
151.             post.next = p.next
     
152. 
     
153.     def index(self,value):
     
154. 
     
155.         if self.is_empty():
     
156.             print 'Linklist is empty.'
     
157.             return
     
158. 
     
159.         p = self.head
     
160.         i = 0
     
161.         while p.next!=0 and not p.data ==value:
     
162.             p = p.next
     
163.             i+=1
     
164. 
     
165.         if p.data == value:
     
166.             return i
     
167.         else:
     
168.             return -1
     
169. 
     
170. 
     
171. l = LinkList()
     
172. l.initlist([1,2,3,4,5])
     
173. print l.getitem(4)
     
174. l.append(6)
     
175. print l.getitem(5)
     
176. 
     
177. l.insert(4,40)
     
178. print l.getitem(3)
     
179. print l.getitem(4)
     
180. print l.getitem(5)
     
181. 
     
182. l.delete(5)
     
183. print l.getitem(5)
     
184. 
     
185. l.index(5)

复制代码

爱琴海里的星

好长~C语言默默飘过~