4

ゼロからの整数のリンク リストを実装する必要があります (既存の LinkedList クラスを使用しないでください)。

これはコードです：

単一のリンク クラス

public class Link {
    public int data;
    public Link nextLink;

    public Link(int d1) {
        data = d1;      
    }

    public void printListElements(){
        System.out.println(data);
    }
}

および LinkedList クラス

public class LinkedList {
    private Link first;
    public LinkedList(){
        first = null;
    }

    public void add(int data1){
        Link linklist = new Link(data1);
        linklist.nextLink = first;
        first = linklist;
    }

    public void printList(){
    Link current=first;
    System.out.println("List Elements are ");
    while(current!=null){
       current.printListElements();
       current=current.nextLink;
    }
  }
}

ご覧のとおり、既にaddおよびprintListメソッドが追加されています。しかし、特定のインデックスの値を返す get() メソッドを作成するにはどうすればよいですか。

これは私が意味するものです：

public static void main(String args[]){
    LinkedList MyList = new LinkedList();

    MyList.add(1);
    MyList.add(2);
    MyList.add(3);
    MyList.add(4);

    System.out.println("MyList.get(0)"); // should get 1
        System.out.println("MyList.get(1)"); // should get 2 etc
}

前もって感謝します。

4

4 に答える 4

7

ええと、それはリンクリストなので、最初の要素以外の要素に直接アクセスする方法はありませんよね？したがって、それを行う唯一の方法は、そこから開始し、インデックスで指定された要素に到達するまで（次の要素へのリンクを連続してたどることによって）ステップスルーし、それを返すことです。これを行う最も簡単な方法は、ループを使用することです。

于 2012-10-02T17:31:10.377 に答える
6

現在の実装ではそれを行うことはできません。すべての新しいノードをヘッドノードとして追加しているためです。

add()すべての新しいノードが最後のノードとして追加されるようにを変更すると、ループカウンターとしてindex渡された値を使用してそれを行うことができます。get()

于 2012-10-02T17:32:54.557 に答える
1

デュアル リンク リストを使用することをお勧めします。

class Node<T> {
   Node<T> next;
   Node<T> prev;
   T data;
}

class LinkedList<T> {
   Node<T> head;
   Node<T> tail;
   int count;
}

add メソッドは、実際には新しいノードを作成し、それをテールの「次の」ポインターにアタッチし、テールを再割り当てし、カウントを増やします。(はい、テール ポインターがある限り、単一のリンクされたリストでこれを行うことができます)

このアプローチでは、 add は一定時間の操作であり、挿入順序を保持します (挿入順序が保持されない単一のリンクされたリストのアプローチとは異なります)。

また、「取得」を最適化して、要求されたインデックスが先頭または末尾に近いかどうかを確認し、適切な端からトラバースして必要なノードを取得することもできます。

これは宿題だと思うので、コード全体を公開したくありません。

于 2012-10-02T18:53:15.353 に答える
1

LinkedList では、要素が元に戻されています。

public int get(int i) {
    int n = indexOf(first); // count-1 actually
    Link current = first;
    while (n > i) {
        --n;
        current = current.nextLink;
    }
    return current.data;
}

private int indexOf(Link link) {
    if (link == null) {
        return -1;
    }
    return 1 + indexOf(link.nextLink);
}
于 2012-10-02T17:43:38.943 に答える