单链表是一种线性数据结构，特点是：(1) .分配空间是不需要一块大的内存空间,因为每个节点都可以独立存储;
(2) .从最后添加一个节点的时间复杂度为 O(1) ， 增删查找操作的时间复杂度都为O(n)
节点类 :
class Node :
def __init__(self):
self.value = None
self.next_node = None链表的初始化方法 :
def __init__(self):
self.head = None
self.end = None
self.next_node = None
self.length = 0从链表尾部添加一个元素add 方法: 这里用了 end 这个尾结点,使得每次添加的时间复杂度为 O(1)，而不需要每次都需要从表头走到表尾
def add(self,value):
"""从尾部添加一个元素"""
new_node = Node()
new_node.value = value
if self.head == None:
self.head = new_node
self.next_node =self.head
if self.end == None :
self.end = new_node
self.head.next_node = new_node
else:
self.end.next_node = new_node
self.end = new_node
self.length += 1从给定值得后面添加一个元素 insert 方法
def insert(self,node_value,value):
"""在某个元素后面插入一个元素,
如果node_value 没有在链表中,就返回 -1
插入成功 ,返回True
"""
new_node = Node()
new_node.value = value
next = self.head
while (next.value != node_value):
if next == self.end :
return -1
next = next.next_node
new_node.next_node = next.next_node
next.next_node = new_node
self.length += 1
return True删除给定值得节点 remove 方法
def remove(self,value):
"""删除给定值得节点"""
next = self.head
prev = None
while (next.value != value):
prev = next
next = next.next_node
if next == None :
return True
self.length -= 1
prev.next_node = next.next_node修改值 update 方法
def update(self,old , new):
"""
修改第一个找到的值为old的节点的值为new
:param old: 要修改的节点的值
:param new: 节点新的值
:return: -1 : 在链表中没有找到值为 old 的节点
True : 修改成功
"""
next = self.head
while (next.value != old):
next = next.next_node
if next.next_node == None :
return -1
next.value = new
return True查找给定值在链表中的索引 getIndex
def getIndex(self,value):
"""
查找给定值在链表中的索引
:param value:
:return: -1 : 给定的值不在列表中
0 ~ length :找到给定值得索引
"""
next = self.head
index = 0
while(next.value != value):
next = next.next_node
index += 1
if next == None :
return -1
return index查找给定值得索引 getValue
def getValue(self,index):
"""
根据给定的索引返回改索引的值
:param index:
:return:
"""
if index > self.length or index < 0:
return -1
next = self.head
temp_index = 0
while(temp_index<index):
next = next.next_node
return next.value使用 __iter__ 和 __next__ 方法使链表为可迭代对象
def __iter__(self):
return self
def __next__(self):
this_node = self.next_node
if this_node != None :
self.next_node = self.next_node.next_node
return this_node
else:
raise StopIteration循环链表是单链表的简单变形,把链表的尾节点和头结点连接到一起,操作的时候,边界判定不是下一个节点为null，而是下一个节点为头结点的时候
class CircleLink :
def __init__(self):
self.head = None
self.next_node = None
self.length = 0
def add(self,value):
"""从尾部添加一个元素"""
new_node = Node()
new_node.value = value
if self.head == None:
self.head = new_node
self.next_node =self.head
next = self.head
while(next.next_node != self.head):
next = next.next_node
next.next_node = new_node
new_node.next_node = self.head
self.length += 1
def insert(self,node_value,value):
"""在某个元素后面插入一个元素,
如果node_value 没有在链表中,就返回 -1
插入成功 ,返回True
"""
new_node = Node()
new_node.value = value
next = self.head
while (next.value != node_value):
if next.next_node == self.head :
return -1
next = next.next_node
new_node.next_node = next.next_node
next.next_node = new_node
self.length += 1
return True
def remove(self,value):
"""删除给定值得节点"""
next = self.head
prev = None
while (next.value != value):
prev = next
next = next.next_node
if next == self.head :
return True
self.length -= 1
prev.next_node = next.next_node
def update(self,old , new):
"""
修改第一个找到的值为old的节点的值为new
:param old: 要修改的节点的值
:param new: 节点新的值
:return: -1 : 在链表中没有找到值为 old 的节点
True : 修改成功
"""
next = self.head
while (next.value != old):
next = next.next_node
if next.next_node == self.head :
return -1
next.value = new
return True
def getIndex(self,value):
"""
查找给定值在链表中的索引
:param value:
:return: -1 : 给定的值不在列表中
0 ~ length :找到给定值得索引
"""
next = self.head
index = 0
while(next.value != value):
next = next.next_node
index += 1
if next == self.head :
return -1
return index
def getValue(self,index):
"""
根据给定的索引返回改索引的值
:param index:
:return:
"""
if index > self.length or index < 0:
return -1
next = self.head
temp_index = 0
while(temp_index<index):
next = next.next_node
return next.value
def __iter__(self):
return self
def __next__(self):
this_node = self.next_node
if this_node != self.head :
self.next_node = self.next_node.next_node
return this_node
else:
raise StopIteration
def __len__(self):
return self.length
版权声明：本文为weixin_41789943原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。