一、单向非循环链表
1.python中的变量并不是保存真实的数据，而是保存该数据存储空间的地址。
2.判断是否为空，计算链表长度，遍历链表，在链表头部、尾部、任意位置插入元素，删除元素、查找元素。
class Node(object): #结点类 def __init__(self,item): self.item = item self.next = None #单链表类 class SingleLinkList(object): def __init__(self,node=None): self.__head = node def is_empty(self): #判断链表是否为空 return self.__head is None def length(self): #计算链表的长度 #考虑特殊情况：链表为空，也满足下面条件 cur = self.__head count = 0 while cur is not None: count += 1 cur = cur.next return count def travel(self): #遍历链表 cur = self.__head while(cur is not None): print(cur.item,end=" ") #设置空格为了取消python3自动换行 cur = cur.next print("") def add(self,item): #头插法：添加元素 #考虑特殊情况：链表为空，也满足下面条件 #构造结点 node = Node(item) node.next = self.__head self.__head = node def append(self,item): #尾插法：添加元素 node = Node(item) if self.is_empty(): self.__head = node #考虑特殊情况：链表为空,需满足下面条件 else: cur = self.__head while cur.next is not None: cur = cur.next cur.next = node def insert(self,pos,item): #在链表的指定位置添加元素 if pos <= 0: self.add(item) elif pos>=self.length(): self.append(item) else: cur = self.__head count = 0 while count < (pos-1): count += 1 cur = cur.next node = Node(item) node.next = cur.next cur.next = node def remove(self,item): #删除结点 cur = self.__head pre = None while cur is not None: if cur.item == item: if cur == self.__head: self.__head = cur.next else: pre.next = cur.next return pre = cur cur = cur.next def search(self,item): #查找元素 cur = self.__head while cur is not None: if cur.item == item: return True cur = cur.next return False注：非常感谢B站中各位大神分享的python数据结构与算法的视频教程，我仅用该博客作为复习笔记以及知识普及。
