1.定义链表节点

　　链表是由一个个数据节点连接而成，首先需要构建数据节点，包含数据元素elem和指向下一节点的next。

1 class Node(object): 
2     """首先定义节点类"""
3     def __init__(self, element):  # 构建数据节点时，需要传入数据元素element
4         self.elem = element
5         self.next = None  # 由于一开始next节点不知道指向什么地方，所以就设置为空

2.初始化单链表

　　初始化链表时，需要一个对象属性指向头结点。

1 class SingleLinkList(object):
2     """定义单链表类"""
3     def __init__(self, node = None):  # 构建链表时，需要传入数据节点node，node默认为None
4         self. __head = node  # head是私有属性

3.单链表基本操作

3.1.链表判空

　　空链表的头一定是指向None的。

1     def is_empty(self):
2         """链表是否为空"""
3         return self.__head is None

3.2.求链表长度

　　求链表长度就是统计链表节点的个数，可以使用一个游标cur遍历节点，使用一个计数器count记录节点个数。

1     def length(self):
2         """链表长度"""
3         cur = self.__head
4         count = 0
5         while cur is not None:
6             count += 1
7             cur = cur.next
8         return count

3.3.遍历链表

1     def travel(self):
2         """遍历链表"""
3         cur = self.__head
4         while cur is not None:
5             print(cur.elem, end=" ")  # end=" "关闭换行功能,print的原型默认是以end="
"结尾.
6             cur = cur.next
7         print(end="
")

3.4.往链表头部添加元素

　　往链表中添加元素就相当远添加数据节点，需要传入节点的数据。

　　Tips_1：增删链表时，A=B可以被理解为，使A指向B；

　　Tips_2：增删链表时，需要先保证不破坏原有链表的链接，以保证操作的顺序正确，如需要先node.next = self.__head，再self.__head = node。

1     def add(self, item):
2         """在链表头部添加元素"""
3         node = Node(item)
4         node.next = self.__head
5         self.__head = node

3.5.往链表尾部添加元素

 1     def append(self, item):
 2         """链表尾部添加元素"""
 3         node = Node(item)
 4         if self.is_empty():
 5             self.__head = node
 6         else:
 7             cur = self.__head
 8             while cur.next is not None:
 9                 cur = cur.next
10             cur.next = node

3.6.往链表指定位置添加元素

　　需要考虑添加位置的边界条件：如果添加的位置是链表头部，可以直接调用add()函数。如果添加的位置是链表尾部，可以直接调用append()函数。

 1     def insert(self, pos, item):
 2         """在指定位置添加元素"""
 3         if pos <= 0:
 4             self.add(item)
 5         elif pos > self.length()-1:
 6             self.append(item)
 7         else:
 8             node = Node(item)
 9             prev = self.__head
10             count = 0
11             while count < (pos-1):
12                 count += 1
13                 cur = cur.next
14             node.next = cur.next
15             cur.next = node

3.7.删除节点

　　链表被打断后，需要pre记录断点前的链表部分。

 1     def remove(self, item):
 2         """删除节点"""
 3         cur = self.__head
 4         pre = None  
 5         while cur is not None:
 6             if cur.elem == item:
 7                 if cur == self.__head:  # 头节点特殊处理
 8                     self.__head = cur.next
 9                 else:
10                     pre.next = cur.next
11                 break
12             else:
13                 pre = cur
14                 cur = cur.next

3.8.查找节点

1     def search(self, item):
2         """查找节点是否存在"""
3         cur = self.__head
4         while cur is not None:
5             if cur.elem == item:
6                 return True
7             else:
8                 cur = cur.next
9         return False

3.9.测试与结果

 1 # 测试
 2 if __name__ == "__main__":
 3     li = SingleLinkList()
 4     print(li.is_empty())       # True
 5     print(li.length())         # 0
 6 
 7     li.append(1)
 8     print(li.is_empty())       # False
 9     print(li.length())         # 1
10 
11     li.append(2)
12     li.add(8)
13     li.append(3)
14     li.append(4)
15     li.append(5)
16     li.append(6)
17     li.insert(-1, 9)  
18     li.insert(2, 100)  
19     li.insert(10, 200) 
20     li.travel()                # 9 8 100 1 2 3 4 5 6 200
21 
22     li.remove(100)
23     li.travel()                # 9 8 1 2 3 4 5 6 200
24     li.remove(9)  
25     li.travel()                # 8 1 2 3 4 5 6 200 
26     li.remove(200)  
27     li.travel()                # 8 1 2 3 4 5 6