本文实例讲述了Python单链表原理与实现方法。分享给大家供大家参考，具体如下：
一个单向链表的节点由数据字段和指针组成，指针指向下一个元素所在内存地址
定义一个链表节点类,self.value实例属性表示节点数据字段；self.next表示指针；初始化值为None
class Node(object):
def __init__(self, value=None, next=None):
self.value = value
self.next = next在单链表中第一个节点为头(head)指针节点(即头指针指向的节点为单链表第一个节点，后续简称头指针节点)，从头指针节点出发可以遍历整个链表，进行元素查找，插入和删除，非常重要。一般不移动head头指针。
单链表中最后一个节点为尾节点，其指针为None，表示结束。
建立单链表我们首先需要创建头指针节点（引入头指针是为了方便操作单链表，对于头指针节点，只有指针域指向链表第一个节点，不含实际值）
class linkedList(object):
def __init__(self):
self.head = Node()# 创建头指针结点
self.length = 0# 初始链表长度，头指针节点不计入长度
def __len__(self):# 重写特殊方法返回self.length
return self.length链表初始化之后，开始定义链表方法
链表头部插入节点：
调用Node()传入待插入的值value创建待插入节点
判断当前链表是否为空链表，链表为空：
链表不为空：
def head_insert(self, value): # 链表头部插入
node = Node(value)
if self.head.next == None:
self.head.next = node
node.next = None
else:
# 插入元素指针域指向原head元素
tmp_head = self.head.next # 原头指针节点存储到tmp_head
self.head.next = node # 新head指针指向node
node.next = tmp_head # 新插入节点指向原头指针节点
self.length += 1链表头部删除节点：
依旧是先判断链表是否为空，为空则返回False
链表不为空时：
def head_del(self): # 删除头结点,返回头结点的值
if self.head.next == None:
return False
else:
# 头指针指针域指向自己
self.head = self.head.next
self.length -= 1
return self.head.value链表尾部添加节点：
创建待插入节点对象
判断链表是否为空，为空则头指针节点就是待插入节点，也是尾节点
链表不为空：
def append(self, value): # 链表尾部添加结点
# 创建新插入的结点对象
node = Node(value)
if self.length == 0:
self.head.next = node # 只有一个节点，指针指向自己
else:
curnode = self.head.next # 变量curnode存放指针
while curnode.next != None:
curnode = curnode.next
curnode.next = node # 当为最后一个节点时，指针指向新插入节点
self.length += 1指定位置后面插入节点：
这里方法接受两个位置参数，index插入位置和value插入值
依旧创建新节点对象
判断是否为空
在链表不为空的条件下：
def insert(self, index, value):
node = Node(value)
if self.length == 0:
self.head.next = node
else:
i = 0
cur_node = self.head.next
while i != index:
cur_node = cur_node.next
i += 1
node.next = cur_node.next
cur_node.next = node
self.length += 1给定值删除该值节点：
删除链表中给定的值我们需要遍历整个链表，因此需要创建一个可迭代对象
定义节点迭代方法
def iter_node(self):
cur_node = self.head.next#当前节点
while cur_node.next != None:# 对除最后一个节点进行可迭代化处理
yield cur_node
cur_node = curnode.next
if cur_node.next == None:# 对尾节点进行可迭代化处理
yield cur_node重写特殊方法–iter–，用来声明这个类是一个迭代器
def __iter__(self): # 遍历列表节点
for node in self.iter_node():
yield node.value首先定义一个Flag变量(默认为False)，用来表示删除状态
依旧判断链表是否为空
链表不为空时：
def delete_node(self, value):
Flag = False
if self.length == 0:
return False
else:
previous_node = self.head # 初始化前置节点为头结点
for node in self.iter_node():
if node.value == value:
previous_node.next = node.next # 前置节点指针指向当前节点的后继节点
del node
self.length -= 1
Flag = True
else:
previous_node = node # 更新前置节点的值
return Flag完整代码：
# 定义链表节点类
class Node(object):
def __init__(self, value=None, next=None):
self.value = value # 节点元素
self.next = next # 指针
# 单链表类
class LinkedList(object):
def __init__(self):
self.head = Node() # 创建头结点
self.length = 0 # 初始化链表长度
def __len__(self):
return self.length
def __iter__(self): # 遍历列表节点
for node in self.iter_node():
yield node.value
def iter_node(self):
curnode = self.head.next
while curnode.next != None:
yield curnode
curnode = curnode.next
if curnode.next == None:
yield curnode
def head_insert(self, value): # 链表头部插入
node = Node(value)
if self.head.next == None:
self.head.next = node
node.next = None
else:
# 插入元素指针域指向原head元素
tmp_head = self.head.next # 原头指针节点存储到tmp_head
self.head.next = node # 新head指针指向node
node.next = tmp_head # 新插入节点指向原头指针节点
self.length += 1
def head_del(self): # 删除头结点,返回头结点的值
if self.head.next == None:
return False
else:
# 头指针指针域指向自己
self.head = self.head.next
self.length -= 1
return self.head.value
def append(self, value): # 链表尾部添加结点
# 创建新插入的结点对象
node = Node(value)
if self.length == 0:
self.head.next = node # 只有一个节点，指针指向自己
else:
curnode = self.head.next # 变量curnode存放指针
while curnode.next != None:
curnode = curnode.next
curnode.next = node # 当为最后一个节点时，指针指向新插入节点
self.length += 1
# 这里的insert是指定值后面插入不是指定位置
def insert(self, index, value):
node = Node(value)
if self.length == 0:
self.head.next = node
self.length += 1
else:
for nd in self.iter_node():
if nd.value == index: # 如果nd节点值等于index，则插入到nd后
tmp_node = nd.next # 将nd的指针存放到中间变量
nd.next = node # nd节点指向插入节点
node.next = tmp_node # 插入节点指向原nd.next节点
self.length += 1
return True
return False
def replace(self, old_value, new_value):
index = 0
if self.length == 0:
return False
else:
for node in self.iter_node():
if node == old_value:
node.value = new_value
index += 1
if index != 0:
return index # 替换节点数量(存在节点值相同情况)
else:
return False # 替换失败，未找到替换值
def delete_node(self, value):
Flag = False
if self.length == 0:
return False
else:
previous_node = self.head # 初始化前置节点为头结点
for node in self.iter_node():
if node.value == value:
previous_node.next = node.next # 前置节点指针指向当前节点的后继节点
del node
self.length -= 1
Flag = True
else:
previous_node = node # 更新前置节点的值
return Flag
# 测试
l = LinkedList()
l.append(1)
l.append(2)
l.append(7)
l.append(5)
l.append(6)
l.append(7)
l.head_insert(3)
print("当前链表长度：%s" %l.length)
#print("删除头结点为：%d"% l.head_del())
print("当前链表长度：%s" %l.length)
i = 1
#l.delete_node(7)
for node in l:
print("第%d个链表节点的值: %d"%(i, node))
i += 1运行结果：
当前链表长度：7
当前链表长度：7
第1个链表节点的值: 3
第2个链表节点的值: 1
第3个链表节点的值: 2
第4个链表节点的值: 7
第5个链表节点的值: 5
第6个链表节点的值: 6
第7个链表节点的值: 7
希望本文所述对大家Python程序设计有所帮助。
Powered By python教程网 鲁ICP备18013710号
python博客 - 小白学python最友好的网站!