用python手把手教你实现单向链表
简介
- 选题 - 用python手把手教你实现单向链表
- 详细说明 链表在python中使用类（相当于C中的结构）实现链表，实现方法也同C语言一样，但是python中没有指针的概念，并且实践中还有其他大大小小的问题，希望可以看到大佬的实践步骤
在互换选题中想尝试着做一下这道题，之前在写C的项目经常有用到单链的相关的一些东西，在做动态扩展或者入参时参数不定长，通常用单链来操作相关内容，在python还没有考虑相关的或者说尝试过一些相关的东西。看到这道选题，还是比较有兴趣尝试的。
思路
拿到选题的时候第一反应是：在python中有一个原生库用来兼容或者引用c库，就是 ctypes ，使用ctypes来实现相关功能，后来考虑一下，拿 ctypes 来实现单链其实没有什么意义或者说绕了远路。就需要考虑另一个种方式来实现单链。
单链在C中的表现形式常常为
代码语言：c复制struct node{
void* value;
node* next;
}关键点为 node*,指针成员。指针的本质来说就是地址的相关操作，所以只需要考虑在python中可不可以获取到变量或者说对象的地址，让我们可以根据地址来索引到操作对象的值，然后思路就很明确了，其中有2个关键点
- 获取操作对象的地址
- 根据地址获取操作对象或者操作对象的值
第一个关键点：在python中每一个对象有一个基本属性 id(),id(object)既可以获取对象的地址。
第二个关键点：python中没有相关方法根据地址获取操作对象的值，可以变动一下，自己做一个字典或者相关容器map之类的来保存 id还有 obj,做一个地址索引或者说一对一索引表。
代码实现
根据上述思路，第一步先实现索引表，这里我选择的是字典。
地址字典
在关于单链的实现中，字典具有全局唯一的属性，但是在全局中可能随时进行增删等相关操作，这里就需要考虑 单例模式来实现字典。
地址的类型为int,所以在字典元素key入参时，需要校验id类型是否为int类型。
字典要实现关于item的增删功能。即代码如下:
代码语言：python代码运行次数：0复制class IdList:
#实现单例模式
_instance = None
def __new__(cls):
if not cls._instance:
cls._instance = super().__new__(cls)
return cls._instance
def __init__(self):
self.id_list = {}
#增加元素
def add_item(self, item):
self.id_list[id(item)] = item
#获取元素
def get_item(self, item_id):
if item_id in self.id_list:
return self.id_list.get(item_id)
else:
return "null"
#删除元素
def del_item_id(self, item_id):
self.id_list.pop(item_id)
def clean(self):
self.id_list.clear()第二步，实现单链节点
单链Node
在链表中，单链节点的表现形式通俗意义上是 值以及下一个节点的地址，即单个节点要有如下属性:
1. 值的设置与获取 2. 地址的设置与获取，且当地址有效时地址类型必须为int类型
在python中，因为增加了地址字典，所以又有一个新增特性
- node同步到地址字典
即代码实现如下：
代码语言：python代码运行次数：0复制class LinkList:
def __init__(self):
#初始化默认为空，可以随意自定义
self.item_value = "null";
self.item_id = "null";
#设置值
def set_value(self, item_value):
self.item_value = item_value
#设置关联地址字典
def set_list(self, item_list):
self.id_list = item_list
#设置下一节点地址
def set_id(self, item_id):
#校验地址类型
if not isinstance(item_id, int):
return
if self.id_list.get_item(item_id) == "null":
return
self.item_id = item_id
#获取下一节点地址
def get_id(self):
return self.item_id
#获取值
def get_value(self):
return self.item_value剩下的就是具体功能特性的实现以及测试
测试
有了上诉的基础属性之后，就可以着手进行单链的实现与测试了。
单链不管在任何场景中，使用的功能特性基本为增加节点，删除节点，插入节点，修改指定节点值 所以基本围绕着这几个功能特性来实现相关代码即可。
代码demo如下：
- 增加节点
def add_node(node_value):
node = LinkList()
node.set_value(node_value)
node.set_list(id_list)
id_list.add_item(node)
if nodes.get_id() == "null":
nodes.set_id(id(node))
return
buf_node = nodes
while buf_node.get_id() != "null":
buf_node = id_list.get_item(buf_node.get_id())
if buf_node.get_id() == "null":
buf_node.set_id(id(node))
break- 删除节点
在删除节点中，有2个特殊点需要注意一下，删除第一个节点还有删除最后一个节点
代码语言：python代码运行次数：0复制def del_node(node_index):
last_id = id(nodes)
last_node = nodes
buf_node = nodes
if node_index == 0 and buf_node.get_id() != "null":
buf_value = buf_node.get_value()
buf_node = id_list.get_item(buf_node.get_id())
nodes.set_value(buf_value)
nodes.set_id(buf_node.get_id())
id_list.del_item_id(last_id)
return
index = 0
while buf_node.get_id() != "null":
if index == node_index:
if buf_node.get_id() != "null":
last_node.set_id(buf_node.get_id())
else:
last_node.set_id("null")
id_list.del_item_id(last_id)
return
last_id = buf_node.get_id()
last_node = buf_node
buf_node = id_list.get_item(buf_node.get_id())
index = 1- 插入节点
在插入节点中，有一个特殊点需要注意，插入节点为第一个节点。
代码语言：python代码运行次数：0复制def insert_node(node_index, node_value):
node = LinkList()
node.set_value(node_value)
node.set_list(id_list)
id_list.add_item(node)
last_id = id(nodes)
last_node = nodes
buf_node = nodes
if node_index == 0:
buf_value = nodes.get_value()
buf_id = nodes.get_id()
nodes.set_value(node.get_value())
nodes.set_id(id(node))
node.set_id(buf_id)
node.set_value(buf_value)
print("insert node sucess!")
return
index = 0
while buf_node.get_id() != "null":
if index == node_index:
last_node.set_id(id(node))
node.set_id(last_id)
print("insert node sucess!")
return
last_id = buf_node.get_id()
last_node = buf_node
buf_node = id_list.get_item(buf_node.get_id())
index = 1- 修改指定节点值
def modify_node(node_index, node_value):
buf_node = nodes
index = 0
while buf_node.get_id() != "null":
if index == node_index:
buf_node.set_value(node_value)
print("node_index value modify sucess!")
return
buf_node = id_list.get_item(buf_node.get_id())
index = 1
print("node_index value is error!")测试场景如下：
代码语言：python代码运行次数：0复制#test -- add node
add_node("2")
add_node("3")
add_node("4")
print_nodes()
#test -- del node
del_node(0)
print_nodes()
#test -- add node
add_node("何其不顾四月天")
add_node("单链表")
print_nodes()
#test -- modify node value
modify_node(0, "云 社区")
modify_node(1, "互换选题活动")
modify_node(2, "测试演示")
print_nodes()
#test -- insert node
insert_node(0, "insert test")
print_nodes()
insert_node(2, "insert test 1")
print_nodes()测试结果输出为：
代码语言：shell复制-------------
0 1
1 2
2 3
3 4
-------------
0 1
1 3
2 4
-------------
0 1
1 3
2 4
3 何其不顾四月天
4 单链表
node_index value modify sucess!
node_index value modify sucess!
node_index value modify sucess!
-------------
0 云 社区
1 互换选题活动
2 测试演示
3 何其不顾四月天
4 单链表
insert node sucess!
-------------
0 insert test
1 云 社区
2 互换选题活动
3 测试演示
4 何其不顾四月天
5 单链表
insert node sucess!
-------------
0 insert test
1 云 社区
2 insert test 1
3 互换选题活动
4 测试演示
5 何其不顾四月天
6 单链表附言
在实际的工程代码中，我所实现的是一个很基础的demo，在具体的功能特性中，也可以单独封一个实现类，继续向上层抽象，提升代码的复用。也可以我的代码为模板继续实现各种链表结果，因为链表的本质还是对上下节点的地址索引，双向链表再增加一个地址属性既可。
我的基本思路如上，如果有其它的看法或者更好的实现方法可以留言或者邮件沟通。
附录-代码
其中有两个代码文件：
文件一：link_list.py
代码语言：python代码运行次数：0复制'''
Author: 何其不顾四月天
Date: 2023-11-28 10:11:43
LastEditors: 何其不顾四月天
LastEditTime: 2023-11-28 12:32:19
FilePath: pythonlink_list.py
Description: python生成单链表
Copyright (c) 2023 by 779508400@qq.com.
'''
import os
class IdList:
_instance = None
def __new__(cls):
if not cls._instance:
cls._instance = super().__new__(cls)
return cls._instance
def __init__(self):
self.id_list = {}
def add_item(self, item):
self.id_list[id(item)] = item
def get_item(self, item_id):
if item_id in self.id_list:
return self.id_list.get(item_id)
else:
return "null"
def del_item_id(self, item_id):
self.id_list.pop(item_id)
def clean(self):
self.id_list.clear()
class LinkList:
def __init__(self):
self.item_value = "null";
self.item_id = "null";
def set_value(self, item_value):
self.item_value = item_value
def set_list(self, item_list):
self.id_list = item_list
def set_id(self, item_id):
if not isinstance(item_id, int):
return
if self.id_list.get_item(item_id) == "null":
return
self.item_id = item_id
def get_id(self):
return self.item_id
def get_value(self):
return self.item_value文件二：test.py
代码语言：python代码运行次数：0复制from link_list import *
#item字典初始化
id_list = IdList()
#创建节点
nodes = LinkList()
nodes.set_value("1")
nodes.set_list(id_list)
#字典添加元素
id_list.add_item(nodes)
def add_node(node_value):
node = LinkList()
node.set_value(node_value)
node.set_list(id_list)
id_list.add_item(node)
if nodes.get_id() == "null":
nodes.set_id(id(node))
return
buf_node = nodes
while buf_node.get_id() != "null":
buf_node = id_list.get_item(buf_node.get_id())
if buf_node.get_id() == "null":
buf_node.set_id(id(node))
break
def del_node(node_index):
last_id = id(nodes)
last_node = nodes
buf_node = nodes
if node_index == 0 and buf_node.get_id() != "null":
buf_value = buf_node.get_value()
buf_node = id_list.get_item(buf_node.get_id())
nodes.set_value(buf_value)
nodes.set_id(buf_node.get_id())
id_list.del_item_id(last_id)
return
index = 0
while buf_node.get_id() != "null":
if index == node_index:
if buf_node.get_id() != "null":
last_node.set_id(buf_node.get_id())
else:
last_node.set_id("null")
id_list.del_item_id(last_id)
return
last_id = buf_node.get_id()
last_node = buf_node
buf_node = id_list.get_item(buf_node.get_id())
index = 1
def insert_node(node_index, node_value):
node = LinkList()
node.set_value(node_value)
node.set_list(id_list)
id_list.add_item(node)
last_id = id(nodes)
last_node = nodes
buf_node = nodes
if node_index == 0:
buf_value = nodes.get_value()
buf_id = nodes.get_id()
nodes.set_value(node.get_value())
nodes.set_id(id(node))
node.set_id(buf_id)
node.set_value(buf_value)
print("insert node sucess!")
return
index = 0
while buf_node.get_id() != "null":
if index == node_index:
last_node.set_id(id(node))
node.set_id(last_id)
print("insert node sucess!")
return
last_id = buf_node.get_id()
last_node = buf_node
buf_node = id_list.get_item(buf_node.get_id())
index = 1
def modify_node(node_index, node_value):
buf_node = nodes
index = 0
while buf_node.get_id() != "null":
if index == node_index:
buf_node.set_value(node_value)
print("node_index value modify sucess!")
return
buf_node = id_list.get_item(buf_node.get_id())
index = 1
print("node_index value is error!")
def print_nodes():
buf_node = nodes
index = 0
print("-------------")
print(index, buf_node.get_value())
while buf_node.get_id() != "null":
index = 1
buf_node = id_list.get_item(buf_node.get_id())
print(index, buf_node.get_value())
#test -- add node
add_node("2")
add_node("3")
add_node("4")
print_nodes()
#test -- del node
del_node(0)
print_nodes()
#test -- add node
add_node("何其不顾四月天")
add_node("单链表")
print_nodes()
#test -- modify node value
modify_node(0, "云 社区")
modify_node(1, "互换选题活动")
modify_node(2, "测试演示")
print_nodes()
#test -- insert node
insert_node(0, "insert test")
print_nodes()
insert_node(2, "insert test 1")
print_nodes()
