[解決済み】Java LinkedListでNodesを使用する

質問

最近買った本でコーディングの面接の標準的な質問を調べていたら、次のような質問と答えに出くわしました。

リンクリストの n 番目から最後の要素を見つけるアルゴリズムを実装しなさい。

これが提供された答えです。

public static LinkedListNode findNtoLast(LinkedListNode head, int n) { //changing LinkedListNode to ListNode<String>
        if(head == null || n < 1) {
            return null;
        }
        LinkedListNode p1 = head;
        LinkedListNode p2 = head;
        for(int j = 0; j < n-1; ++j) {
            if(p2 == null) {
                return null;
            }
            p2 = p2.next;
        }
        if(p2 == null) {
            return null;
        }
        while(p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

アルゴリズムやその仕組み、そしてなぜこの本がこれを答えとして挙げているのかは理解していますが、メソッドの引数として送るLinkedListNodesにアクセスする方法については、混乱しています。 私はLinkedListNodeクラスを作成しなければならないことを知っています（Javaにはまだないので）、しかし、私はそれを行う方法を見つけ出すことができません。 私はこれを行う方法を知っている必要があるように感じるので、それはイライラしています。 以下は、私が取り組んできたことです。 分かりやすい説明をしていただけると大変ありがたいです。 私のコードを拡張/コメントしたり、あなた自身の代替案を提供することができます。 ありがとうございます。

class ListNode<E> {
    ListNode<E> next;
    E data;

    public ListNode(E value) {
        data = value;
        next = null;
    }

    public ListNode(E value, ListNode<E> n) {
        data = value;
        next = n;
    }

    public void setNext(ListNode<E> n) {
        next = n;
    }
}

public class MyLinkedList<E> extends LinkedList {
    LinkedList<ListNode<E>> list;
    ListNode<E> head;
    ListNode<E> tail;
    ListNode<E> current;
    ListNode<E> prev;

    public MyLinkedList() {
        list = null;
        head = null;
        tail = null;
        current = null;
        prev = null;
    }

    public MyLinkedList(LinkedList<E> paramList) {
        list = (LinkedList<ListNode<E>>) paramList; //or maybe create a loop assigning each ListNode a value and next ptr
        head = list.getFirst();
        tail = list.getLast(); //will need to update tail every time add new node
        current = null;
        prev = null;
    }

    public void addNode(E value) {
        super.add(value);
        //ListNode<E> temp = tail;
        current = new ListNode<E>(value);
        tail.setNext(current);
        tail = current;
    }

    public LinkedList<ListNode<E>> getList() {
        return list;
    }

    public ListNode<E> getHead() {
        return head;
    }

    public ListNode<E> getTail() {
        return tail;
    }

    public ListNode<E> getCurrent() {
        return current;
    }

    public ListNode<E> getPrev() {
        return prev;
    }


}

LinkedListNodeはどのようにしてLinkedListから頭出しができるのですか？

更新：私の混乱の原因の一つは、mainメソッドに何を書くかということにあると思います。 ListNodeのLinkedListを作成する必要があるのでしょうか？ そうすると、ListNode同士はどのように接続するのでしょうか？ LinkedListコレクション・オブジェクトを使用せずに、どのようにそれらを接続するのでしょうか？ もし、誰かがmainメソッドをどのようにコーディングするか教えてくれれば、私の問題を解決するために、物事を十分に理解できるようになると思います。 以下は、mainメソッドに対する私の最新の試みです。

public static void main(String args[]) {
        LinkedList<ListNode<String>> list = new LinkedList<ListNode<String>>();
        //MyLinkedList<ListNode<String>> list = new MyLinkedList(linkedList);
        list.add(new ListNode<String>("Jeff"));
        list.add(new ListNode<String>("Brian"));
        list.add(new ListNode<String>("Negin"));
        list.add(new ListNode<String>("Alex"));
        list.add(new ListNode<String>("Alaina"));
        int n = 3;
        //ListIterator<String> itr1 = list.listIterator();
        //ListIterator<String> itr2 = list.listIterator();
        LinkedListNode<String> head = new LinkedListNode(list.getFirst(), null);
        //String result = findNtoLast(itr1, itr2, n);
        //System.out.println("The " + n + "th to the last value: " + result);
        //LinkedListNode<String> nth = findNtoLast(list.getFirst(), n);
        ListNode<String> nth = findNtoLast(list.getFirst(), n);
        System.out.println("The " + n + "th to the last value: " + nth);
    }

カスタムのリンクリストクラスを使用せずにノードを接続する試みとして、ListNodeクラスを以下のように編集しました。

class ListNode<E> {
    ListNode<E> next;
    ListNode<E> prev; //only used for linking nodes in singly linked list
    ListNode<E> current; //also only used for linking nodes in singly linked list
    E data;
    private static int size = 0;

    public ListNode() {
        data = null;
        next = null;
        current = null;
        if(size > 0) { //changed from prev != null because no code to make prev not null
            prev.setNext(this);
        }
        size++;
    }
    public ListNode(E value) {
        data = value;
        next = null;
        current = this;
        System.out.println("current is " + current);
        if(size > 0) {
            prev.setNext(current);//this line causing npe
        }
        else
        {
            prev = current;
            System.out.println("prev now set to " + prev);
        }
        size++;
        System.out.println("after constructor, size is " + size);
    }

    public ListNode(E value, ListNode<E> n) {
        data = value;
        next = n;
        current = this;
        if(size > 0) {
            prev.setNext(this);
        }
        size++;
    }

    public void setNext(ListNode<E> n) {
        next = n;
    }
}

今のままでは、ListNode の単一引数コンストラクタで prev.setNext(current); に到達するまで実行されます。 この行に到達した時点では、currentもprevもnullではありません。 何かアドバイスがあれば、よろしくお願いします。 ありがとうございます。

解決方法は？

実はLinkedListクラスを別に用意する必要はなく、ListNodeクラス は はリンクリストです。あるいは、別の言い方をすれば、リストの先頭への参照はリストへの参照となります。

投稿されたサンプルコードで head, tail, current, prev が使われているのは、双方向にリンクしているデータ型であるダブルリンクリストから来ています。これは、ある種のアプリケーション（最後のn番目の項目を見つけるなど）において、より効率的です。

そこで、ListNodeクラスの名前をLinkedListに変更し、ListNodeクラスの名前を next から tail .

リストに新しい項目を追加するには、新しい項目を先頭に持つ新しいリストを作成するメソッドが必要です。以下はその例です。

class LinkedList<E> {
    ...

    private LinkedList(E value, LinkedList<E> tail) {
        this.data = value;
        this.tail = tail;
    }

    public LinkedList<E> prependItem(E item) {
        return new LinkedList(item, this);
    }
}

次に、新しい項目を追加するために i から list を使用します。 list = list.prependItem(i);

何らかの理由で、常に最後に項目を追加する必要がある場合。

private LinkedList(E value) {
    this.data = value;
    this.tail = null;
}

public void appendItem(E item) {
    LinkedList<E> list = this;
    while (list.tail != null)
        list = list.tail;
    list.tail = new LinkedList<>(item);
}

しかし、これは長いリストでは明らかにかなり非効率的です。もしこれを行う必要があるなら、別のデータ構造を使うか、リストへの追加が終わった時点でリストを反転させればよいのです。

ちなみに、面白い副作用として、リストの任意の項目への参照はリンクリストへの参照となります。このため、再帰処理が非常に簡単になる。例えば、リストの長さを求める再帰的な解法は次のとおりです。

public int getLength(LinkedList list) {
    if (list == null) {
        return 0;
    } else {
        return 1 + getLength(list.getTail());
    }
}

そして、これを使うことで、あなたが提供した問題に対する簡単な（しかし非常に非効率的な！）解決策になります。その機能をより明確にするために、メソッドの名前を変更しました。

public LinkedList getTailOfListOfLengthN(LinkedList list, int n) {
    int length = getLength(list);
    if (length < n) {
        return null;
    } else if (length == n) {
        return list;
    } else {
        return getTailOfLengthN(list.getTail(), n);
    }
}

そして、リストを逆にすること。

public LinkedList<E> reverse() {
    if (tail == null) {
        return this;
    } else {
        LinkedList<E> list = reverse(tail);
        tail.tail = this;
        tail = null;
        return list;
    }
}

これで、ノードリストクラスを分離するよりもずっとエレガントなメソッドになることがおわかりいただけると思います。