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

程序员文章站 2023-12-24 08:15:21

...

回复内容：

我只说一下 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中的例子

class TreeNode:
# 类的结构已经包含了指向关系
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

l1 = TreeNode(0) 
l2 = TreeNode(1)
l3 = TreeNode(2)

# 引用表示指向关系
l1.left  = l2
l1.right = l3

这个可以怒答一发，因为刚用java实现了一下链表，这里针对java和链表，python不发表意见

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

先上节点的代码

private class Node {
    public Node next;
    public T data;
    public Node(T d,Node 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的简单链表实现：

# -*- coding: utf-8 -*-

class Node(object):

    def __init__(self, datum, next):
        self.__datum = datum
        self.__next = next

    @property
    def datum(self):
        return self.__datum
        
    @property
    def next(self):
        return self.__next

    @next.setter
    def next(self, next):
        self.__next = next


class LinkedList(object):

    def __init__(self):
        self.__head = None
        self.__tail = None

    @property
    def head(self):
        return self.__head

    @property
    def tail(self):
        return self.__tail

    def purge(self):
        self.__head = None
        self.__tail = None

    def is_empty(self):
        return self.__head is None

    def append(self, item):
        #Generates the node.
        datum = Node(item, None)
        #For the first node in a linked list, it will change the head.
        if self.__head is None:
            self.__head = datum
        else:
            self.__tail.next = datum
        self.__tail = datum

    def remove(self, item):
        pointer = self.__head
        prepointer = None
        #Finds the item
        while pointer and pointer.datum != item:
            prepointer = pointer
            pointer = pointer.next
        #Raise the error when not finding the item.
        if pointer is None: raise KeyError
        #When the linked list has one node, it will sets the head.
        if pointer == self.__head:
            self.__head = pointer.next
        else:
            prepointer.next = pointer.next
        if pointer == self.__tail:
            self.__tail = prepointer