Python数据结构(二)·单链表
单链表是一种链式的数据结构，链表中的数据用结点表示，保持了数据之间的逻辑关系，但存储空间不一定是按照顺序存储。
链表的基本元素有：
- 节点：包括数据域和指针域，数据域存放数据，指针域存放指向下一个元素的指针
- head：头结点
- tail：尾结点
- None：链表最后一个结点的指针域为None
Python中没有显式的指针，但是有引用啊，所以我们可以通过定义节点类和引用来实现链表！
链表分为单链表和单循环链表，双向链表和双向循环链表，本篇先讲一下单链表：
2.1 定义节点类
节点类中包括节点数据和下一个节点地址，即引用
# 节点类
class Node(object):
# 单个节点 初始化 输入一个值data，将值变为一个节点
def __init__(self, data):
self.data = data
self.next = None
# 打印对象中具体的属性值
def __str__(self):
# 测试基本功能，输出data
return self.data
# 输出data
print(Node('data'))这里的__str__可以不用写，这里是在进行测试，在后面的具体实现部分可以不用这个，str函数可以方便我们打印对象中具体的属性值，也是很nice了！具体使用如上
2.2 获取链表的长度
# 获取链表的长度
def length(self):
cur = self.head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count2.3 头插元素
# 头部添加元素
def add_fist(self, data):
node = Node(data)
node.next = self.head
self.head = node2.4 尾插元素
# 尾部添加元素
def add_last(self, data):
node = Node(data)
# 如果链表为空，需要特殊处理
if self.is_empty():
self.head = node
else:
cur = self.head
while cur.next is not None:
cur = cur.next
# 退出循环的时候，curl指向尾结点
cur.next = node2.5 指定位置插元素
# 在指定位置添加元素
def insert_node(self, index, data):
node = Node(data)
if index < 0 or index > self.length():
return False
elif index == 0:
self.add_fist()
elif index == self.length():
self.add_last()
else:
cur = self.head
count = 0
while count < (index - 1):
count += 1
cur = cur.next
# 退出循环的时候，cur指向index的前一个位置
node.next = cur.next
cur.next = node2.6 删除节点
# 删除指定节点
def remove_node(self, data):
cur = self.head # 指针指向的结点
pre = None # 指针指向结点的前一个
if self.head == data:
self.head.next = self.head
else:
while cur.data is not data:
# 不是要找的元素，移动游标
pre = cur
cur = cur.next
pre.next = cur.next2.7 查找节点
# 查找节点
def search_node(self, data):
cur = self.head
while cur is not None:
if cur.data == data:
return True
else:
cur = cur.next
return False2.8 打印链表
# 遍历 打印链表
def traverse_to_print_node(self):
# cur = self.head
# while cur is not None:
# print(cur.data, end = " ")
# cur = cur.next
print_list = []
cur = self.head
while cur is not None:
print_list.append(str(cur.data))
cur = cur.next
print('->'.join(print_list))2.9 测试代码
# 测试
if __name__ == '__main__':
list = SingleLinkedList()
list.add_fist(2)
list.add_fist(1)
list.add_last(4)
list.insert_node(2, 3)
list.traverse_to_print_node()
print(list.is_empty())
print(list.length())
list.remove_node(4)
print(list.search_node(3))
list.traverse_to_print_node()结果图：
结果图
2.10 完整代码
#!usr/bin/env python
# encoding:utf-8
# 节点类
class Node(object):
# 单个节点 初始化 输入一个值data，将值变为一个节点
def __init__(self, data):
self.data = data
self.next = None
# 打印对象中具体的属性值
def __str__(self):
# 测试基本功能，输出data
return self.data
class SingleLinkedList(object):
# 创建一个单链表
def __init__(self):
self.head = None
# 判断链表是否为空
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 add_fist(self, data):
node = Node(data)
node.next = self.head
self.head = node
# 尾部添加元素
def add_last(self, data):
node = Node(data)
# 如果链表为空，需要特殊处理
if self.is_empty():
self.head = node
else:
cur = self.head
while cur.next is not None:
cur = cur.next
# 退出循环的时候，curl指向尾结点
cur.next = node
# 在指定位置添加元素
def insert_node(self, index, data):
node = Node(data)
if index < 0 or index > self.length():
return False
elif index == 0:
self.add_fist()
elif index == self.length():
self.add_last()
else:
cur = self.head
count = 0
while count < (index - 1):
count += 1
cur = cur.next
# 退出循环的时候，cur指向index的前一个位置
node.next = cur.next
cur.next = node
# 删除指定节点
def remove_node(self, data):
cur = self.head # 指针指向的结点
pre = None # 指针指向结点的前一个
if self.head == data:
self.head.next = self.head
else:
while cur.data is not data:
# 不是要找的元素，移动游标
pre = cur
cur = cur.next
pre.next = cur.next
# 查找节点
def search_node(self, data):
cur = self.head
while cur is not None:
if cur.data == data:
return True
else:
cur = cur.next
return False
# 遍历 打印链表
def traverse_to_print_node(self):
# cur = self.head
# while cur is not None:
# print(cur.data, end = " ")
# cur = cur.next
print_list = []
cur = self.head
while cur is not None:
print_list.append(str(cur.data))
cur = cur.next
print('->'.join(print_list))
# 测试
if __name__ == '__main__':
list = SingleLinkedList()
list.add_fist(2)
list.add_fist(1)
list.add_last(4)
list.insert_node(2, 3)
list.traverse_to_print_node()
print(list.is_empty())
print(list.length())
list.remove_node(4)
print(list.search_node(3))
list.traverse_to_print_node()本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-07-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
