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     print("当前链表数据:")
94     linkList.elem_travel()  # 9 12 8

运行结果：