1

私はこの本を読んでいて、好きなリストに関するこの章があり、単一のリンクされたリストの実装から始まり、次のようになります:

リンクされたリストの作成:

class Node {
    Node next = null;
    int data;

    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

私の質問:

最初：これがどのように機能するのか理解できません。これを理解するのは本当に複雑ですか、それとも何か不足していますか?

2 番目: この「ノード」クラスは、リンクされたリストと見なすことができますか? いくつかの機能が欠けていることは知っていますが、これはそれ自体がリンクされたリストですか?

3 番目: LinkedList の実装を Java でグーグル検索し、Java API の元のクラスを一瞥しましたが、これはまったく異なるアプローチです。どのアプローチに固執する必要がありますか？

4

3 に答える 3

2

このコードの問題点は、Nodeクラスがノードであると同時にリンク リストでもあり、混乱を招くことです。それ以外は、かなり簡単なはずです。

class Node {
    Node next = null;
    int data;

はnext、リスト内の次のノードを保持します。最後のノードであれば、 を保持しますnull。はこのdataノードに関連付けられたデータであり、この場合はタイプですint(BTW である必要がありますfinal)。

public Node(int d) {
    data = d;
}

constructorこれは、引数をそのフィールドにコピーするだけの単純なものです。リストの先頭とリスト自体を表します。

void appendToTail(int d) {        
    Node n = this;
    while (n.next != null) {
        n = n.next;
    }

これは出会いを見つける場所です。分かりやすいようにコードを少し整理しました。このappendToTailメソッドは、リストの and にノードを追加します。上記のコードでは、最後のノード (フィールドが に設定されているノードthis) を見つけるために、リスト (リストの先頭から開始) をトラバースします。nextnull

    Node end = new Node(d);
    n.next = end;
}

ここで、新しいノードが作成され、現在の最後のノードの次のノードとして追加され、リストの最後のノードになります。

于 2012-11-27T22:12:55.807 に答える
1

次は、次のデータへのリンクです。

[データ|次へ->][データ|次へ->]....[]

次はポインタのようなもので、次のノードを指します。

appendToTailは、ノードとリンクを作成します。

于 2012-11-27T22:15:04.003 に答える
0

通常、Nodeクラスはできるだけ小さくする必要があります。ノードの主な機能は次のとおりです。

  • Node の値を格納する
  • 次の Nodeインスタンスへの参照 (またはポインター) を格納する

Node クラスを作成する最も簡単な方法は、上記と同様です。

public class Node<E> {
    protected E value;
    protected Node<E> next;

    public Node(E value) {
        this.value = value;
    }
}

次に、この汎用Nodeクラスを使用してカスタムLinkedList実装を作成できます。

あなたの質問の特定のサンプル コードでは、 Nodeクラス内に追加メソッドが実装されていますが、これは私の意見では適切な方法ではありません。代わりに、そのメソッドはNodeクラスの責任ではないため、追加はLinkedListクラスにある必要があります。

LinkedList の Append メソッド

ソースごとに実装されるメソッドは異なる場合があります。しかし、append メソッド自体はほとんど同じように見えます。実装する前に、append メソッドのロジックを理解する必要があります。

リンクされたリストが空の場合、ヘッドは null 値を指します。Head はフィールドであり、Linked List の開始ノードを格納する LinkedList クラスのメンバーです。

リンク リストに値を追加すると、最初に追加された値が head に格納され、次に 2 番目の値が新しいノードになり、head の次の参照またはポインターが指します。等々。以下の状態を確認できます。

// Initial state of the Linked List
// Head is null

HEAD = NULL

// Append 40 to the Linked List 
// Head stores value 40, but next reference is null.

HEAD(40) --> NULL

// Append 10

HEAD(40) --> (10) --> NULL

// Append 20

HEAD(40) --> (10) --> (20) --> NULL

// Append 50

HEAD(40) --> (10) --> (20) --> (50) --> NULL

// Append 100

HEAD(40) --> (10) --> (20) --> (50) --> (100) --> NULL

明らかなように、Linked List は常に NULL 参照で終了します。これは、リスト内をトラバースするときに非常に便利です。「ここは道の終点です。この道を横断するのはやめてください」という意味のポイント、マークがなければなりません。

この例のために私が書いた最小限の単純なリンク付きリストの実装を以下で確認することもできます。

LinkedList の最小限の実装

public class CustomLinkedList<E> {

    private Node<E> head;

    public CustomLinkedList() {
        this.head = null;
    }

    public void appendToList(E value) {
        if(head == null)
            head = new Node<E>(value);
        else {
            Node<E> temp = head;

            // get the end node into the temp
            while(temp.next != null)
                temp = temp.next;

            // temp is the tail now
            // append new Node next to the tail
            temp.next = new Node<E>(value);
        }
    }

    public void printList() {
        if(head == null)
            return;

        System.out.print("List: ");

        Node<E> temp = head;
        while( temp != null ) {
            System.out.print(temp.value.toString() + " ");
            temp = temp.next;
        }

        System.out.println();
    }

}

デモコード

public class DemoCustomLinkedList {

    public static void main(String[] args) {
        CustomLinkedList<Integer> linkedList = new CustomLinkedList<>();

        linkedList.appendToList(40);
        linkedList.appendToList(10);
        linkedList.appendToList(20);
        linkedList.appendToList(50);
        linkedList.appendToList(100);

        linkedList.printList();
    }

}

デモ出力

List: 40 10 20 50 100
于 2016-03-12T22:26:32.253 に答える