Python3
Windows电脑
打开Python开发工具IDLE,新建‘SingleLindedList.py’文件，并写代码如下：class Node: def __init__(self,item): self.item = item self.next = Noneclass SingleLinkedList: def __init__(self): self.__head = None def add(self,item): node = Node(item) node.next = self.__head self.__head = node def isEmpty(self): return self.__head == None def walk(self): cur = self.__head while cur is not None: print (cur.item) cur = cur.nextif __name__ == '__main__': sll = SingleLinkedList() print (sll.isEmpty()) sll.add(8) sll.walk() print (sll.isEmpty())解释一下：先定义了节点类Node，含有两个字段一个是数据item,一个是指向下一个节点的变量next。之后定义单向链表类SingleLinkedList，私有字段head指向第一个节点，对象创建时为None，add函数在头部添加数据，isEmpty测试链表是否为空，walk遍历链表
F5运行程序，打印出内容如下：True 单向链表刚创建时内容为空8 打印出单向链表内容False 单向链表添加节点后不为空
接下来写单向链表长度函数，代码如下：class Node: def __init__(self,item): self.item = item self.next = Noneclass SingleLinkedList: def __init__(self): self.__head = None def add(self,item): node = Node(item) node.next = self.__head self.__head = node def isEmpty(self): return self.__head == None def walk(self): cur = self.__head while cur is not None: print (cur.item) cur = cur.next def length(self): cur = self.__head count = 0 while cur is not None: count += 1 cur = cur.next return count if __name__ == '__main__': sll = SingleLinkedList() print (sll.length()) sll.add(8) sll.add(7) sll.walk() print (sll.length())解释一下;也是通过遍历方式，只要节点不为None就加1计数
F5运行程序，打印出内容如下：0 刚创建时长度为0782 添加两个数据后长度为2
下面写从指定位置插入元素及尾部添加元素的函数：class Node: def __init__(self,item): self.item = item self.next = Noneclass SingleLinkedList: def __init__(self): self.__head = None def add(self,item): node = Node(item) node.next = self.__head self.__head = node def isEmpty(self): return self.__head == None def walk(self): cur = self.__head while cur is not None: print (cur.item) cur = cur.next def length(self): cur = self.__head count = 0 while cur is not None: count += 1 cur = cur.next return count def append(self,item): if self.length()==0: self.add(item) else: node = Node(item) cur = self.__head while cur.next is not None: cur = cur.next cur.next = node def insert(self,i,item): if i<=0: self.add(item) elif i>=self.length(): self.append(item) else: node = Node(item) cur = self.__head index = 0 while index < i-1: index = index +1 cur = cur.next node.next = cur.next cur.next = node if __name__ == '__main__': sll = SingleLinkedList() sll.append(10) sll.add(8) sll.add(7) sll.insert(12,9) sll.walk()特别注意当插入位置大于小于长度时单向链表的操作。
F5运行程序，打印出内容如下：78109
最后是查找和删除方法，代码如下：class Node: def __init__(self,item): self.item = item self.next = Noneclass SingleLinkedList: def __init__(self): self.__head = None def add(self,item): node = Node(item) node.next = self.__head self.__head = node def isEmpty(self): return self.__head == None def walk(self): cur = self.__head while cur is not None: print (cur.item) cur = cur.next def length(self): cur = self.__head count = 0 while cur is not None: count += 1 cur = cur.next return count def append(self,item): if self.length()==0: self.add(item) else: node = Node(item) cur = self.__head while cur.next is not None: cur = cur.next cur.next = node def insert(self,i,item): if i<=0: self.add(item) elif i>=self.length(): self.append(item) else: node = Node(item) cur = self.__head index = 0 while index < i-1: index = index +1 cur = cur.next node.next = cur.next cur.next = node def search(self,item): cur = self.__head while cur is not None: if cur.item == item: return True cur = cur.next return False def delete(self,item): cur = self.__head pre = None while cur is not None: if cur.item == item: if pre is not None: pre.next = cur.next else: self.__head = cur.next pre = cur cur = cur.next if __name__ == '__main__': sll = SingleLinkedList() sll.append(10) sll.add(8) print (sll.search(5) ) sll.insert(12,9) sll.delete(8) sll.walk()注意删除元素时要记录前一个节点信息，让前一个节点直接指向当前节点的下一个节点，就达到了删除的目的
F5运行程序，打印出内容如下：False109节点item为8的被成功删除