1

次のコードは、2 つのリンクリストを構築し、それらの両方を渡して 3 つ目のマージされたリンクリストを構築します。ただし、マージされると、l1 と l2 (最初に構築された) リンクリストが変更されました。このコードのどこで l1 と l2 を null に設定する必要がありますか?

編集: null に設定する理由は、クライアントが変更された l1 または l2 を今後使用しないようにするためです。一度マージすると、新しい参照が作成され、以前の参照は無効になり、作成時にリンクリストであると誰かが信じて使用しないようにする明確な契約が必要です。

public class MergeLinkedList {
    Node first;
    Node last;

    public void add (int val) {
        final Node l = last;
        final Node newNode = new Node(val, null);
        last = newNode;
        if (first == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
    }

    public void displayList() {
        Node tempFirst = first;
        while (tempFirst != null) {
            System.out.print(tempFirst.item + " ");
            tempFirst = tempFirst.next;
        }
    }

    private static class Node {
        int item;
        Node next;

        Node(int element, Node next) {
            this.item = element;
            this.next = next;
        }
    }

    private Node mergeLinkedListRecursive(Node list1, Node list2) {
        if (list1 == null) {
           return list2; 
        }

        if (list2 == null) {
            return list1;
        }

        if (list1.item < list2.item) {
            list1.next = mergeLinkedListRecursive(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeLinkedListRecursive(list1, list2.next);
            return list2;
        }
    }

    public void mergeLinkedListRecursion(MergeLinkedList list1, MergeLinkedList list2) {
        first = mergeLinkedListRecursive(list1.first, list2.first);
    }



    public static void main(String[] args) {

        int[] a1 = {1, 3, 5};
        int[] a2 = {2, 4};

        MergeLinkedList l1 = new MergeLinkedList();
        for (int val : a1 ) {
            l1.add(val); 
        }

        MergeLinkedList l2 = new MergeLinkedList();
        for (int val : a2) {
            l2.add(val);
        }

        MergeLinkedList l3 = new MergeLinkedList();
        l3.mergeLinkedListRecursion(l1, l2);
        l3.displayList();
    }
}
4

3 に答える 3

2

l1およびによって命名されたオブジェクトを正しく使用する責任はl2、呼び出し元にあります。

つまり、呼び出し元はそれを想定しl1、l2常に同じ一連の項目に評価される可能性がありますが、その後l3.mergeLinkedListRecursion(l1, l2);はそうではありません。これは、メソッドが副作用を実行し、オブジェクトを変更するためです。

メソッドの呼び出し後は、呼び出し元が と を正しく使用する必要がl1ありl2ます。「正しい」使用法は、それらをまったく使用しないことです。(l1およびl2変数は、まだ 2 つのリストの先頭に評価されます。1 つはサブリストです。予想とは異なります。)

l1引数 ( and ) を nullに割り当てることができたとしても (l2つまり、call-by-reference セマンティクスを使用して)、前述の (変更された) オブジェクトに評価されるすべての変数/フィールドに null が割り当てられることを保証することは不可能です。

変数/フィールドは特定のオブジェクトの名前です。ソーダなど、特定のオブジェクトのすべての名前を追跡するにはどうすればよいですか?それともポップですか? コーラ？コークス？코카인?

この問題を回避する 1 つの方法は、不変リストを使用することです。この場合、マージされたリストには実際にはすべての新しいノードが含まれ、既存のノードは絡み合っていません。つまり、不変リストを使用すると、コンストラクターでのみnext設定できます。Haskell や Scala などの一部の言語は、このアプローチに従います。

別のアプローチ (提案するのをためらっています) は、「コンテナー コンテナー」を作成することです。nextリンクされたリストの場合、リストに対して「無効にする」操作が実行されたときにnullに割り当てられる「ダミーヘッドノード」である可能性があります。ただし、これはハック的で不要なソリューションであり、正しく実装するのが難しく、それ以外の場合は単純な可変リンクリスト実装を汚します。

根本的な問題は変異と副作用であり、非純粋なコードを書くことの醜い側面の 1 つにすぎません。少しのドキュメント (およびそのようなドキュメントの読み取り) は大いに役立ちます。また、単体テスト: テストは、誤った仮定から生じる可能性のある問題を検出できます。

于 2013-06-16T06:55:39.280 に答える
0

l1 と l2 を null に設定する理由がわかりませんが、それを行うには、次の行の後に配置する必要があります。

l3.mergeLinkedListRecursion(l1, l2);

それらをnullに設定したいのはなぜですか？

于 2013-06-16T06:33:43.920 に答える
0

Nodeオブジェクトが への引数として使用された後に無効になった場合、mergeLinkedListRecursive()これはノードが覚えておくべきことです:

class Node {
    ...
    boolean valid = true;
    void markInvalid() { valid = false; }
}

そして、mergeLinkedListRecursive()それらをそのようにマークします：

list1.markInvalid();
list2.markInvalid();

そしてもちろん、 makeNodeのメソッドは最初にそれが有効な状態にあることを確認します。

于 2013-06-16T06:44:36.807 に答える