讲师中心 微信公众号

工具推荐

视频效率加速
SoundView
SoundView

字幕擦除翻译、配音口型同步

AniShort
AniShort

AI短剧协同制作平台

updream

一键生成高质量推广成片

Laper
Laper

剧本策划到成片协作

Java、Python中没有指针,怎么实现链表、图等数据结构?

浅涛吖_3675

浅涛吖_3675

发布时间:2016-06-06 16:23:24

|

3951人浏览过

|

来源于php中文网

原创

回复内容:

我只说一下 Java :虽然没有指针,但每个变量,如果不是基本数据类型(int float 等),那么就是一个引用(reference)。

引用类似指针,只是不能进行指针运算,比如 p + 1 指向下一个元素之类的。

各种语言的链表实现:

Singly-linked list/Element definition
Singly-linked list/Element insertion 实现基本的数据结构时指针唯一的作用就是指向,不涉及指针运算(pointer arithmetic)(这也不叫 const pointer),所以 Java / Python 的引用已经足够做到这一点了。就算实现 B-tree 什么的,配个数组也够了。
随手写个 Python 的链表节点,Java 的下面有人贴例子了,都是一样的道理。
需要
class Node(object):
    def __init__(self, value, nextnode=None):
        self.value = value
        self._nextnode = nextnode

    def append(self, n):
        if not isinstance(n, Node):
            n = Node(n)
        self._nextnode, n = n, self._nextnode
        self._nextnode._nextnode = n
Python里直接用dict套dict就可以表示图,graph[u][v]=w,表示从u到v的有向边,边权(或者其他需要标记的信息)为w。
如果是无向图,可以限定u如果u到v有多条边,那就是dict套dict套set,graph[u][v]={w0,w1..}
如果要求存留边之间的或者节点之间的顺序关系,就把dict/set改为ordereddict。

以上做法相当于hash表示的邻接表,适合稀疏图。稠密图可以考虑用NumPy存储邻接矩阵以减小额外开销。

想看成熟的Python库怎样设计处理图的API的话,看Overview — NetworkX。 方法有很多:
  • 用内置数据结构(list, dict, tuple等)的嵌套/组合,它们隐式地包含了指向/嵌套关系,如上面回答中的graph[u][v]={w0,w1..}
  • 类的成员变量、嵌套类可能包含了指向/嵌套关系;
  • 引用表示指向关系,只不过引用不能像指针一样运算,比如 p + 1 指向下一个元素,所以可能限制颇多。
  • ...
Leetcode中的例子
<span class="k">class</span> <span class="nc">TreeNode</span><span class="p">:</span>
<span class="c"># 类的结构已经包含了指向关系</span>
    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">x</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">val</span> <span class="o">=</span> <span class="n">x</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">left</span> <span class="o">=</span> <span class="bp">None</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">right</span> <span class="o">=</span> <span class="bp">None</span>

<span class="n">l1</span> <span class="o">=</span> <span class="n">TreeNode</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span> 
<span class="n">l2</span> <span class="o">=</span> <span class="n">TreeNode</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
<span class="n">l3</span> <span class="o">=</span> <span class="n">TreeNode</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span>

<span class="c"># 引用表示指向关系</span>
<span class="n">l1</span><span class="o">.</span><span class="n">left</span>  <span class="o">=</span> <span class="n">l2</span>
<span class="n">l1</span><span class="o">.</span><span class="n">right</span> <span class="o">=</span> <span class="n">l3</span>
这个可以怒答一发,因为刚用java实现了一下链表,这里针对java和链表,python不发表意见

首先,楼上的大大们都说了,引用差不多是受限的指针,完全可以实现指针的功能

先上节点的代码
private class Node<T> {
    public Node<T> next;
    public T data;
    public Node(T d,Node<T> n) {data = d; next = n;}
}
java的引用就不说了,python里所有的变量其实都是对象的引用(连基本类型都是如此),而这个引用,说白了就是个指向实例的指针。

所以并不是没有指针,而是全都是指针只不过你看不出来而已。

做链表当然可以,对于python而言就一个类里两个属性,next仍旧是next,指向下个节点的实例就可以了。 Python和Java的“引用”就是不能运算的指针。

其实我更喜欢go语言的理念,没有任何“引用”,所以就避免了混淆的“传引用”概念。所有的值传递都是传值,指针就是指针,但是不能运算。 其实Java, python完全可以看成在语言层用语法糖隐藏了指针。

Java中,假设class A有 属性 int a, B(class B) b,那A实例化(b在A实例化新开辟而不是通过外部赋值),内存开辟一段包含一个int a和 一个b 的reference地址,b实例化和A一样,然后把地址抛给A中b的reference。其实这个和C/C++中的A中有个B* b差不多。所以链表、图等数据结构在C/C++中的实现转义到Java中也就是改改语法糖的表示。

Python中,链表、树等数据结构大致对应Python自带list、tuple、dict。Python这种动态语言用C实现,拿Python的list来讲,用一个struct PyListObject 实现,看看源码指针随处都是。

C/C++这样的语言比较接近早期抽象计算机数据的思维方式,指针其实就是我们抽象数据并且这个数据是聚合但是实际内存离散的胶合层产物。后来出的语言通过其他的方式来抽象数据表示,将指针这个概念隐藏了,显得友好了,但是其实他还在那。 基本上没有指针会有更灵活的方式进行,回收机制直接丢弃可以自动释放内存,写起来也简单,一码胜千言,贴张python的简单链表实现:
<span class="c"># -*- coding: utf-8 -*-</span>

<span class="k">class</span> <span class="nc">Node</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>

    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">datum</span><span class="p">,</span> <span class="nb">next</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__datum</span> <span class="o">=</span> <span class="n">datum</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__next</span> <span class="o">=</span> <span class="nb">next</span>

    <span class="nd">@property</span>
    <span class="k">def</span> <span class="nf">datum</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__datum</span>
        
    <span class="nd">@property</span>
    <span class="k">def</span> <span class="nf">next</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__next</span>

    <span class="nd">@next.setter</span>
    <span class="k">def</span> <span class="nf">next</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="nb">next</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__next</span> <span class="o">=</span> <span class="nb">next</span>


<span class="k">class</span> <span class="nc">LinkedList</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>

    <span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__head</span> <span class="o">=</span> <span class="bp">None</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__tail</span> <span class="o">=</span> <span class="bp">None</span>

    <span class="nd">@property</span>
    <span class="k">def</span> <span class="nf">head</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__head</span>

    <span class="nd">@property</span>
    <span class="k">def</span> <span class="nf">tail</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__tail</span>

    <span class="k">def</span> <span class="nf">purge</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__head</span> <span class="o">=</span> <span class="bp">None</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__tail</span> <span class="o">=</span> <span class="bp">None</span>

    <span class="k">def</span> <span class="nf">is_empty</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
        <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">__head</span> <span class="ow">is</span> <span class="bp">None</span>

    <span class="k">def</span> <span class="nf">append</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
        <span class="c">#Generates the node.</span>
        <span class="n">datum</span> <span class="o">=</span> <span class="n">Node</span><span class="p">(</span><span class="n">item</span><span class="p">,</span> <span class="bp">None</span><span class="p">)</span>
        <span class="c">#For the first node in a linked list, it will change the head.</span>
        <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="n">__head</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">__head</span> <span class="o">=</span> <span class="n">datum</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">__tail</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">datum</span>
        <span class="bp">self</span><span class="o">.</span><span class="n">__tail</span> <span class="o">=</span> <span class="n">datum</span>

    <span class="k">def</span> <span class="nf">remove</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
        <span class="n">pointer</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__head</span>
        <span class="n">prepointer</span> <span class="o">=</span> <span class="bp">None</span>
        <span class="c">#Finds the item</span>
        <span class="k">while</span> <span class="n">pointer</span> <span class="ow">and</span> <span class="n">pointer</span><span class="o">.</span><span class="n">datum</span> <span class="o">!=</span> <span class="n">item</span><span class="p">:</span>
            <span class="n">prepointer</span> <span class="o">=</span> <span class="n">pointer</span>
            <span class="n">pointer</span> <span class="o">=</span> <span class="n">pointer</span><span class="o">.</span><span class="n">next</span>
        <span class="c">#Raise the error when not finding the item.</span>
        <span class="k">if</span> <span class="n">pointer</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span> <span class="k">raise</span> <span class="ne">KeyError</span>
        <span class="c">#When the linked list has one node, it will sets the head.</span>
        <span class="k">if</span> <span class="n">pointer</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">__head</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">__head</span> <span class="o">=</span> <span class="n">pointer</span><span class="o">.</span><span class="n">next</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="n">prepointer</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">pointer</span><span class="o">.</span><span class="n">next</span>
        <span class="k">if</span> <span class="n">pointer</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">__tail</span><span class="p">:</span>
            <span class="bp">self</span><span class="o">.</span><span class="n">__tail</span> <span class="o">=</span> <span class="n">prepointer</span>
其实完全不用指针也可以实现这种结构。
参见:cons
python速学教程(入门到精通)
python速学教程(入门到精通)

python怎么学习?python怎么入门?python在哪学?python怎么学才快?不用担心,这里为大家提供了python速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
讯飞智作

讯飞智作是一款AI视频创作工具,AI文本配音工具,数字人课程、营销视频制作。

超级麦吉

一款通过数字员工协作完成调研、数据分析与文档制作的AI办公平台。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

Seko
Seko Hot

一款AI视频创作工具,主要用于商汤科技推出的创编一体的AI短视频创作Agent,适合需要提升相关任务效率的用户。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

笔灵降AI

一款AI论文写作工具,主要用于论文降AI神器,适配知网及维普!一键降至安全线,100%保留原文格式;无口语化问题,文风更学术,降后字数控制最佳!,适合需要提升相关任务效率的用户。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

咔片AIPPT

一款在线AI演示文稿制作工具,可根据主题和内容需求辅助生成PPT结构与页面,提高演示材料制作效率。

PixPix
PixPix Hot

PixPix是一款面向电商视觉生产的AI商品图生成工具。

相关专题

更多
Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

20

2026.11.20

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

20

2026.11.20

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

0

2026.11.20

PHP8.6数组与数据处理教程
PHP8.6数组与数据处理教程

本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

60

2026.11.20

PHP8.6升级迁移教程
PHP8.6升级迁移教程

本专题汇总PHP8.6升级迁移与弃用接口改造教程,涵盖反射调用、对象属性赋值、标识符更名、构造函数与__debugInfo调整,以及插件类名检查、常量导出、ArrayIterator排序、SPL和DTO查询参数转换,帮助梳理弃用提示并完成代码兼容改造。

0

2026.11.20

PHP8.6安装配置与FPM运维教程
PHP8.6安装配置与FPM运维教程

本专题汇总PHP8.6正式版安装部署与FPM运维教程,涵盖Linux并存安装、独立ini配置、扩展重新编译、Nginx切换与回滚、FPM状态监控和慢日志排查,以及环境变量、请求超时、OPcache刷新和预加载配置。

40

2026.11.20

Nginx CVE-2026-123007排查与防护指南
Nginx CVE-2026-123007排查与防护指南

Nginx HTTP/2漏洞该怎么修复?本专题围绕CVE-2026-123007,介绍安全版本升级、模块兼容检查和配置恢复方法,以及日志排查、权限设置等后续加固操作,方便你按实际部署情况查找对应教程。

40

2026.11.20

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

80

2026.11.17

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

100

2026.11.17

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn