Python实现单向链表
1、打开Python开发工具IDLE,新建‘SingleLindedList.py’文件，并写代码如下：
class Node:
def __init__(self,item):
self.item = item
self.next = None
class 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
if __name__ == '__main__':
sll = SingleLinkedList()
print (sll.isEmpty())
sll.add(8)
sll.walk()
print (sll.isEmpty())
解释一下：先定义了节点类Node，含有两个字段一个是数据item,一个是指向下一个节点的变量next。之后定义单向链表类SingleLinkedList，私有字段head指向第一个节点，对象创建时为None，add函数在头部添加数据，isEmpty测试链表是否为空，walk遍历链表
2、F5运行程序，打印出内容如下：
True 单向链表刚创建时内容为空
8 打印出单向链表内容
False 单向链表添加节点后不为空
3、接下来写单向链表长度函数，代码如下：
class Node:
def __init__(self,item):
self.item = item
self.next = None
class 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计数
4、F5运行程序，打印出内容如下：
0 刚创建时长度为0
7
8
2 添加两个数据后长度为2
5、下面写从指定位置插入元素及尾部添加元素的函数：
class Node:
def __init__(self,item):
self.item = item
self.next = None
class 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()
特别注意当插入位置大于小于长度时单向链表的操作。
6、F5运行程序，打印出内容如下：
7
8
10
9
7、最后是查找和删除方法，代码如下：
class Node:
def __init__(self,item):
self.item = item
self.next = None
class 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()
注意删除元素时要记录前一个节点信息，让前一个节点直接指向当前节点的下一个节点，就达到了删除的目的
8、F5运行程序，打印出内容如下：
False
10
9
节点item为8的被成功删除
