0

我正在创建一个链接列表，并且试图弄清楚如何编写一个方法来返回特定索引的节点有效负载。向量如何具有 get(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);
    }
4

1 回答 1

3

这是链表的主要缺点：对于由数组支持的列表，按索引进行随机访问是 O(n) 而不是 O(1)。他们就是这样工作的。

您可以通过使用跳过列表使事情变得更好，但它会使事情变得更复杂，并且需要更多的内存。

请注意，在每个节点中存储索引会使情况变得更糟，因为在第一个索引处插入一个节点，应该是 O(1) 没有存储索引，但会变成 O(n) 索引，因为你需要访问每个节点列表以增加其索引。通过存储此索引，您基本上从链表和数组列表中获取了最糟糕的部分。

你为什么要实现一个链表，而不是使用标准java.util.LinkedList？

于 2013-04-03T13:07:24.273 回答