python 实现单链表

 1 class Node(object):
 2     def __init__(self,elem):
 3         self.elem = elem
 4         self.next = None
 5 
 6 class SingleLinkList(object):
 7     """单向列表"""
 8     def __init__(self):
 9         self.__head = None
10 
11     def is_empty(self):
12         return self.__head is None
13 
14     def get_length(self):
15         """遍历整个列表"""
16         curr_node = self.__head
17         count = 0
18         while curr_node.next is not None:
19             count += 1
20             curr_node = curr_node.next
21         count += 1
22         return count
23 
24     def add(self,item):
25         """头部添加"""
26         node = Node(item)
27         node.next = self.__head
28         self.__head = node
29 
30     def append(self,item):
31         node = Node(item)
32         if self.is_empty():
33             self.__head = node
34         else:
35             curr_node = self.__head
36             while curr_node.next is not None:
37                 curr_node = curr_node.next
38             curr_node.next = node
39 
40     def insert(self,pos,item):
41         if pos <=0:
42             self.add(item)
43         elif pos >(self.length()-1):
44             self.append(item)
45         else:
46             pre = self.__head
47             count = 0
48             while count < (pos-1):
49                 count +=1
50                 pre = pre.next
51             #循环退出后 pre指向pos-1
52             node = Node(item)
53             node.next = pre.next
54             pre.next = node
55 
56     def remove(self,item):
57         """删除数据"""
58         curr_node = self.__head
59         pre = None
60         while curr_node is not None:
61             if curr_node.elem == item:
62                 #先判断是否是头结点
63                 if curr_node == self.__head:
64                     self.__head = curr_node.next
65                 else:
66                     pre.next = curr_node.next
67                 break
68             else:
69                 pre = curr_node
70                 curr_node = curr_node.next
71 
72     def elem_travel(self):
73         """遍历整个列表"""
74         if self.is_empty():
75             return None
76         curr_node = self.__head
77         while curr_node.next is not None:
78             print(curr_node.elem, " ")
79             curr_node = curr_node.next
80         print(curr_node.elem, " ")
81 
82 if __name__ == "__main__":
83     linkList = SingleLinkList()
84     print(linkList.is_empty())    #True
85     linkList.add(9)
86     linkList.add(12)
87     linkList.append(4)
88     linkList.append(8)
89     print(linkList.is_empty())  # False
90     print(linkList.get_length()) # 4
91     linkList.remove(4)
92     print(linkList.get_length()) # 3
93     linkList.elem_travel()  # 9 12 8