リンクリストのコードレビューadd（i、x）メソッド

Question

現在、ADT実装、特にリンクリストの実装をブラッシュアップしようとしています（これを行うにはJava 5を使用しています）。

私は2つの質問があります。

を（1）私が正しいと効率的なアドオン（x iは、）のために書いたこの実装ですか？

public void add(int i, Object x) { 

    // Possible Cases: 
    // 
    //  1. The list is non-empty, but the requested index is out of 
    //  range (it must be from 0 to size(), inclusive) 
    // 
    //  2. The list itself is empty, which will only work if i = 0 
    // 
    // This implementation of add(i, x) relies on finding the node just before 
    // the requested index i. 

    // These will be used to traverse the list 
    Node currentNode = head; 
    int indexCounter = 0; 

    // This will be used to mark the node before the requested index node 
    int targetIndex = i - 1; 

    // This is the new node to be inserted in the list 
    Node newNode = new Node(x); 

    if (currentNode != null) { 

     while (indexCounter < targetIndex && currentNode.getNext() != null) { 

      indexCounter++; 
      currentNode = currentNode.getNext(); 
     } 

     if (indexCounter == targetIndex) { 

      newNode.setNext(currentNode.getNext()); 
      currentNode.setNext(newNode); 

     } else if (i == 0) { 

      newNode.setNext(head); 
      head = newNode; 
     } 

    } else if (i == 0) { 

     head = newNode; 
    }  
} 

（2）Iは、実施するには、この方法は非常に困難を発見しました。正直言って、それは数日かかった。私はプログラミングが大好きで、いくつかの言語やプラットフォームの中間レベルで自分自身を考えているので、これは認めがたいです。私は13歳（Apple IIcのApplesoft BASIC！）からCSを学んだのでプログラミングしてきました。私は現在、ソフトウェアテスターとして働いており、ある時点で開発者になる予定です。だから私の質問の第二の部分は、これは私が優れた仕事のタイプであると自分自身をだましているのだろうか？何かは、この方法を実装することに直面している熟練した開発者でさえ、難しいと感じています。

フィードバックとアドバイスをいただきありがとうございます。

Answer 1

私はそれは良いスタートだと思う...いくつかの提案：

• 私はあなたの現ノードが== nullの場合は、開始時の世話をして、返されるべきだと思うが。私は "if（currentNode！= null）の中にあるすべてが好きではありません"
• リンクリストのサイズをどこかで把握して、i> list_sizeを確認するだけです。
• I wouldn
• 必要なまでnewNodeを作成しないでください。
• 単体テストを書くと、簡単に変更でき、実装がまだ動作することがわかります。
• 不正な引数は無視しないでください。私< 0または>サイズインデックス場合は、この実装は効率的ではありませんが、操作の追加は、（i、x）の上効率的ではありませんので、これは一部である例外：IllegalArgumentExceptionかはIndexOutOfBoundsException（感謝@JB Nizet）

Answer 2

まず、単体テストを書くことをお勧めします。特に、リストの終わりを超えてノードを追加してみて、何が起こるかを確認してください。 ;）

ほとんどの開発者は、a）それを実装する方法がたくさんあり、b）通常は自分で書くものではないため、LinkedListを書くのが難しいと思います。通常は、動作する既存の実装の1つを使用します。 ;）

練習としては全く同じ良いアイデアです。私は組み込みのLinkedListのコードを読んで、どうやって別のことをするのかを考えてみることをお勧めします。例えばそれをどのように単純化するかは、スタートになる可能性があります。

Answer 3

を投げます通常のリンクされたリストリンクされたリストはランダムアクセスのためのものではありません。ハッシュテーブルなどを作成しておけば、おそらくリストに効率的なインデックスを作成できます。たとえば、マップを考えてみましょう。次に、map.ContainsKey（i-1）のmap.get（i-1）の挿入ルーチン（明らかにi = 0の特別なケースがあります）を使用すると、すぐ前のインデックスがあります。そして、もしi！= 0で、あなたはそのインデックスのためのキーを持っていなければ、すぐにあなたはエラーを知っています。マップは理論的にはO（1）であり、あまりにも多くの衝突がない場合は、毎回リストを反復するよりもはるかに効率的です（しかし、ディスクスペースを犠牲にして）。繰り返しますが、純粋なリンクリストはadd（i、x）に対してあまり効率的でないため、実際は依存します。

add（32、x）と言っていて、リストに15個の項目しかないと、静かに失敗するので、私はこのメソッドが特に気に入らない。挿入が失敗したことを示すためには、少なくとも例外をスローするか、falseを返すか、何かを返さなければなりません。

おそらく2つの特殊なケースをマージすることもできます。 newNode.setNext（NULL）が動作すると仮定すると、i == 0のチェックが1つだけ必要です。そしてnewNode.setNext（head）、head = newNodeを実行できます。リストが空の場合は、次のポインタをNULLに設定します。これにより、少なくとも重複したコードが削除されます。

1週間ほどかかっているようですが、最初にポインタ（javaspeakのよくあるクラスのリファレンス....）の周りに頭を抱えている人がたくさんいます。あなたが最終的に何かを得たという事実は正しい方向への大きな一歩です。