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(1) ではなく O(n) です。それが彼らの働き方です。

スキップ リストを使用することで状況を改善できますが、状況がより複雑になり、より多くのメモリが必要になります。

各ノードにインデックスを保存するよりも悪いことに注意してください。最初のインデックスにノードを挿入すると、インデックスが保存されていない場合は O(1) になるはずですが、インデックスがあると O(n) になります。インデックスをインクリメントするリスト。このインデックスを格納することにより、基本的に、リンクされたリストと配列リストの両方から悪い部分を取得しています。

標準を使用せずに、リンクされたリストを実装するのはなぜjava.util.LinkedListですか?

于 2013-04-03T13:07:24.273 に答える