如何在不使用指针的情况下实现链表？

在你有指针的C++中，很容易实现链表。但他们如何在其他语言（如java，python等）中实现。我不想使用内置类（在JAVA中支持）链接列表，但我想要的是如何替换指针来创建链接列表？如何在不使用指针的情况下实现链表？

2012-08-24 mak04

阅读本文，看看它是否足以解决您的问题：http://stackoverflow.com/questions/7480783/pointers-in-java –

@asawyer Python和Java中的引用都没有通过。在许多使用同一意义上的引用的其他语言中都没有。 – delnan

@asawyer：同意delnan。 Java是通过价值传递的。总是。该值可能是一个参考值，但值是通过的值。 –

它们是使用基本上（不包括语法）指针的引用实现的，您不能使用指针运算（在某些语言中它们也不能为null）。在很多语言中，引用是使用变量的默认方式，与默认值为by的C++不同。

2012-08-24 18:55:53

+1我喜欢这种参考解释。它非常快速，简单和准确，除了对C老兵们显而易见并给他人一个理解编程方面的理由之外。 – delnan

用其他语言处理与指针密切相关的引用。

2012-08-24 18:54:53

当你写自己的类，说class node，并让每个node举行现场下一node，你居然抱到下一个节点的引用（或空，如果这是最后一个）

2012-08-24 18:56:37

代替如前所述，指向一块内存的指针被使用。所以就像你在C++

Struct Node { 
    Node *last; 
    Node *next; 
}

它应该是这样的：

Struct Node { 
    Node last; 
    Node next; 
    }

2012-08-24 18:59:45

最后一句话是不幸的。如果我们将它作为面值，即“节点是一个值类型”，这意味着你的第二个节点定义是无效的，因为它的大小是无限的。引用不是地址，但它们*是*间接引用。 – delnan

我只注意到你的第二个例子是无效的，甚至忽略了现在删除的解释。（如果它应该是C++的话）。 – delnan

它简直就是假想的可视化。 Struct只是来自他在C++中的背景 –

一个很好的数据结构类会显示该链表可以用任何语言使用数组，如实施FORTRAN。

而不是使用指针，你可以使用其他方法来找到下一个链接。使用数组，而不是指针可以使用下一个元素的索引。

因此，您可以通过使用文件位置而不是指针来实现随机访问文件中的链接列表。

2012-08-24 19:09:04

我不确定这是否算作链表。它与基于指针的实现具有不同的特性，因为它更加有限。除此之外，这完全与此无关，因为您可以*通过引用构建“常规”链表（以及所有其他依赖于间接引用的数据结构）。 – delnan

这是一个列表，它被链接。它不使用指针来链接节点。它是一个链接列表的不同实现*。我在大学的数据结构课上教过这些。 –

您可能在本书中找到一个很好的答案 - http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 - 我会总结一下我记得的东西。

基本上你会有两个相同大小的数组（希望大于n，其中n =你想存储的元素的数量）。我们将它们称为阵列A和阵列B.

阵列A [i]保存数据值。数组B [i]保持'下一个'值'k'，使得A [i] - > next = A [k]。

希望这会有所帮助。

2012-08-24 19:13:03 jimf

查看我对托马斯马修的回答的评论。 – delnan

记住链表的概念是，你可以从一个元素获取到另一个元素。你怎么做可以是非常不同的。

在C++中，例如你提到的你可以使用指针。这说另一种方式将是你使用对象的内存地址。

但这只是一种方式。如果您的所有对象都是从数组中引用的，那么您将能够通过它在该数组上的索引来引用对象。因此，链表中的每个元素都会有一个整数，指定它所连接的对象的索引。

给你另一个例子。如果你有一个字典，你可以用字符串关联对象。然后你可以使用字符串来引用对方。

链接列表的核心概念不是指针，而是列表中的元素负责跟踪它所连接的元素。

2016-01-08 18:34:43

回答