鏈接列表的動態實現

class Nodetype 
{ 
    int info; 
    Nodetype next; 

    Nodetype(int i) 
    { 
    info=i; 
    next=null; 
    } 
}

我的課本有這段代碼來動態創建鏈接列表。問題是，當程序逐行執行時，它將變量'info'定義爲類型'int'&，然後將變量'next'定義爲Nodetype。鏈接列表的動態實現

這裏實際發生了什麼？

豈不是變「下一步」將包含 -

構造「節點類型」
INT資訊
節點類型「下一個」，其中「下一個」將再次擁有所有1,2,3 &然後3將再次有1,2,3 ...等等......直到無限？

我真的很煩，因爲我無法理解它是如何工作的，有人可以輕鬆解釋這一點嗎？

來源

2011-12-10 Siddharth Thevaril

第一個變量next沒有指向任何對象（它指向null）。在某個時候，您將使其指向next = new NodeType(number)的另一個節點。這個想法是，你使用組合 - 你有一個類的實例有一個對另一個實例的引用。這就像nodeA指向nodeB,nodeB指向nodeC。這裏有三個實例，第一個實例有第二個實例的引用，第二個實例有第三個實例的引用。第三種情況是最後一個，其下一個實例指向null。

來源

2011-12-10 11:27:43

非常感謝！ –

歡迎您:) –

該字段next是對Nodetype類型的對象的引用。起初它不會指向任何東西 - 因爲它被實例化爲null。當你給它賦值的時候，它只會指向那個值，除非你在列表中創建一個循環，否則任何東西都將無限地繼續下去。

來源

2011-12-10 11:28:14 yurib

您創建了類NodeType，並在類的內部定義了該類的對象。因此，該對象（在您的示例next）將具有int info變量NodeType next對象和構造函數。

來源

2011-12-10 11:28:18 MrD

next是對另一個Nodetype實例的引用。如果next == null表示當前元素是列表中的最後一個元素。

讓我們看一個例子：

Nodetype node = new Nodetype(0);  // i = 0, next = null 
Nodetype anotherNode = new Nodetype(1); // i = 1, next = null 
node.next = anotherNode;    // now the first node has a ref to the second

來源

2011-12-10 11:28:25

它將包含Null，作爲變量未初始化爲任意值。

來源

2011-12-10 11:28:26

Nodetype是您的類，它定義節點實例將包含的數據以及對鏈接列表中下一個節點的引用。對下一個節點的引用將是類型爲Nodetype的對象。這裏沒什麼太難，這是鏈接列表的經典實現。

你可能想看看斯坦福大學的great linked list resourc e。

來源

2011-12-10 11:28:42 buruzaemon

你的代碼很好地遵循list的定義：一個列表是null或者一個元素後跟一個列表。
在您的情況下，「元素」由int值定義，「其次」部分是next變量;在Java變量中（當它們不是文字時，因爲值爲int）實際上是指針，所以當它們未被初始化時，它們不存儲任何有效值並且它們不指向任何存儲區域（即它們的值是null），所以儘管next變量保持原樣，但您的元素之後沒有任何其他元素。動態地添加元素到列表中，你需要一個指向您添加的最後一個元素，否則你將無法再找到他們：

int i = 0; 
Nodetype head = new Nodetype(i++); 
Nodetype last = new Nodetype(i++); 
head.next = last; 
while (i<5) { 
    Nodetype temp = new Nodetype(i++); 
    last.next = temp; 
    last = temp; 
} 
while(head) { 
    System.out.println(head.info); 
    head = head.next; 
}

注意如何，隨着最後幾行，你失去了head指針並且您無法找回您的列表的起始點。請在使用列表時記住這一點;）

來源

2011-12-10 11:43:10 mccc

此方法的工作原理是該列表由單個元素組成，其中每個元素只有一個指向它的指針：

Nodetype next;

列表中的每個元素實際上所保存的信息是這樣的：

int info;

你可以認爲像一個「鏈」的列表：它不是一個真正的單個對象，但多個環節的複合對象。從每個鏈接，你只能看到下一個鏈接（或者，如果鏈接列表中有雙向引用：下一個鏈接和上一個鏈接），所以爲了使所有元素都可用，必須保留引用到「鏈條」中的第一個元素。

注意：List對象是單引用「鏈」的第一個鏈接的對象。

來源

2011-12-10 12:17:24

鏈接列表的動態實現

回答

相關問題