用python手把手教你实现单向链表

原创

何其不顾四月天

发布于 2023-11-28 21:26:54

1550

发布于 2023-11-28 21:26:54

文章被收录于专栏：四月天的专栏四月天的专栏

用python手把手教你实现单向链表

简介

选题 - 用python手把手教你实现单向链表
详细说明链表在python中使用类（相当于C中的结构）实现链表，实现方法也同C语言一样，但是python中没有指针的概念，并且实践中还有其他大大小小的问题，希望可以看到大佬的实践步骤

在互换选题中想尝试着做一下这道题，之前在写C的项目经常有用到单链的相关的一些东西，在做动态扩展或者入参时参数不定长，通常用单链来操作相关内容，在python还没有考虑相关的或者说尝试过一些相关的东西。看到这道选题，还是比较有兴趣尝试的。

思路

拿到选题的时候第一反应是：在python中有一个原生库用来兼容或者引用c库，就是 ctypes ，使用ctypes来实现相关功能，后来考虑一下，拿 ctypes 来实现单链其实没有什么意义或者说绕了远路。就需要考虑另一个种方式来实现单链。

单链在C中的表现形式常常为

struct node{
    void* value;
    node* next;
}

关键点为 node*,指针成员。指针的本质来说就是地址的相关操作，所以只需要考虑在python中可不可以获取到变量或者说对象的地址，让我们可以根据地址来索引到操作对象的值，然后思路就很明确了，其中有2个关键点

获取操作对象的地址
根据地址获取操作对象或者操作对象的值

第一个关键点：在python中每一个对象有一个基本属性 id(),id(object)既可以获取对象的地址。

第二个关键点：python中没有相关方法根据地址获取操作对象的值，可以变动一下，自己做一个字典或者相关容器map之类的来保存 id还有 obj,做一个地址索引或者说一对一索引表。

代码实现

根据上述思路，第一步先实现索引表，这里我选择的是字典。

地址字典

在关于单链的实现中，字典具有全局唯一的属性，但是在全局中可能随时进行增删等相关操作，这里就需要考虑 单例模式来实现字典。

地址的类型为int,所以在字典元素key入参时，需要校验id类型是否为int类型。

字典要实现关于item的增删功能。即代码如下:

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同步到地址字典

即代码实现如下：

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个特殊点需要注意一下，删除第一个节点还有删除最后一个节点

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!")

测试场景如下：

#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()

测试结果输出为：

-------------
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

'''
Author: 何其不顾四月天
Date: 2023-11-28 10:11:43
LastEditors: 何其不顾四月天
LastEditTime: 2023-11-28 12:32:19
FilePath: \python\link_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

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()

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python3