如何在不使用指針的情況下實現鏈表？

在你有指針的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

回答