爪哇從提供的索引檢索列表有效載荷

我正在創建一個鏈表，我想知道如何編寫一個方法，將返回特定索引的節點有效載荷。只是向量如何得到（int index）我想實現類似的東西。同樣對於這個功能，我可以很容易地添加一個add（int index，e Element），這對於一個循環雙向鏈表來說是非常方便的。爪哇從提供的索引檢索列表有效載荷

在我DynamicNode文件我實現了這種方式：

public class DynamicNode { 
    private Object info; 
    private DynamicNode next, previous; 
    private int position; 

    public DynamicNode(Object x) { 
     info = x; 
    } 

    public Object getInfo() { 
     return info; 
    } 

    public DynamicNode getNext() { 
     return next; 
    } 

    public DynamicNode getPrevious() { 
     return previous; 
    } 

    public int getPosition() { 
     return position; 
    } 

    public void setInfo(Object x) { 
     info = x; 
    } 

    public void setNext(DynamicNode n) { 
     next = n; 
    } 

    public void setPrevious(DynamicNode m) { 
     previous = m; 
    } 

    public void setPosition(int x) { 
     position = x; 
    } 
}

我有一個計數器，因此指數被傳遞沿增加和減少節點數目我LinkedList.java文件。

我認爲get（int index）語句可以工作的唯一方法就是在get方法中運行一個檢查節點索引的循環，並在正確的索引匹配時返回與節點，但這似乎是一個非常密集的過程。

在此先感謝，如果有更多信息需要發佈，我會盡我所能填補空白。

我的插入方法

public void insert(DynamicNode node) { 
     //set node's previous node to the last node entered 
     node.setPrevious(last); 

     //set previous node's next to node 
     last.setNext(node); 

     //set node's next to first node 
     node.setNext(first); 

     //increase numNodes pool 
     numNodes++; 

     //sets new last node 
     last = node; 

     //sets node position 
     node.setPosition(numNodes); 
    }

來源

2013-04-03 pcort

這是鏈表的主要缺點：由索引隨機訪問爲O（n），而不是O（1）用於通過數組支持列表。這就是他們的工作方式。

你可以通過跳過列表來使事情變得更好，但它會使事情變得更加複雜，並且需要更多的內存。

注意比在每個節點中存儲索引更糟糕，因爲在第一個索引處插入一個節點（應該是O（1）而沒有存儲索引）會變成帶索引的O（n），因爲您需要訪問列表中的每個節點以增加其索引。通過存儲這個索引，你基本上從鏈接列表和數組列表中獲取更糟的部分。

你爲什麼要實現一個鏈表，而不是使用標準java.util.LinkedList？

來源

2013-04-03 13:07:24

要回答你的最後一個問題，這是爲類，我們必須創建我們自己的LinkedList文件。你能否解釋一下O（n）和O（1）？你的意思是說，訪問並不是按順序在數組中順序進入索引，而是基本遍歷整個列表以訪問索引？這很有道理，但我的想法是在插入節點時實現索引。我將用insert（）方法編輯我的OP，因爲它太長而不能響應。但是這樣，節點索引是信息，下一個和之前的負載的一部分。 – pcort

在鏈表的開始插入一個節點應該是一個常量時間操作（O（1））。您只需創建一個新節點，將其下一個指針設置爲當前的第一個節點，然後就完成了。由於您將每個節點的位置存儲在節點本身中，因此該操作變得更加複雜：您需要額外迭代列表中的所有節點以增加其位置。這使它成爲O（n）。通過這樣做，你會失去鏈表對數組列表的所有（小）優勢。我不明白你會得到什麼，因爲你必須遍歷節點來實現get（i） –

啊，我現在完全明白了。這是有道理的，但是當我添加一個節點時，我將它添加到列表的後面，而不是前面，所以在這方面，每次添加節點時都不是遞增位置，而是如果我添加節點名單的中間。我希望這可能是一個簡單的（ish）方法，我可以編寫這個方法來將節點拉到特定的索引處，但是如果要這樣做的方式是遍歷節點，直到找到節點。index（x），迭代節點的方法是node.getNext（）並計算++直到達到它。所以節點索引是浪費時間。謝謝！ – pcort

爪哇從提供的索引檢索列表有效載荷

回答

相關問題