Double Linked List Javaを再帰的に検索する

Question

用語のためにJavaの二重リンクリストを検索し、見つかったらそれを返します。ここに私のコードは、これまでのところです：

private class Node { 
    public String content; 
    public Node up; 
    public Node left; 
    public Node right; 
} 

private Node searchList(String term, Node node) { 
    while (node != null) { 
     System.out.print(node.name + " - "); //To see process 

     if (node.content.equals(term)) { 
      return node; 
     } else if (node.right != null) { 
      return searchList(term, node.right); 
     } 

     node = node.left; 
    } 

    return null; 
} 

私のアルゴリズムは、基本的には次のとおりです。

• の要素がある場合は、検索用語
• と一致した場合にノードがnull
• チェックはありませんが彼は正しく、再帰でそれをスキャンする
• 両方のポイントは現在nullで、アイテムは存在しません

私の質問で編集、申し訳ありません： 私は下のレベルを検索し、私が間違っている場所を理解するのに困っていることができません。

助けていただけたら幸いです！

Answer 1

あなたのアルゴリズムは左に移動し、すべての右のノードを繰り返し見つけるので、同じノードを何回か計算すると思います。

開始ノードから2方向にそれぞれ検索することでノードを見つけることができます。

private Node internalSearchList(String term, Node node, int direction) { 
    if (node == null) { 
    return null; 
    } 
    if (term.equals(node.content)) { 
    return node; 
    } else { 
    return internalSearchList(term, direction == 0 ? node.left : node.right, direction); 
    } 
} 

private Node searchList(String term, Node node) { 
    // search to left side 
    Node result = internalSearchList(term, node, 0); 
    if (result != null) { 
    return result; 
    } else { 
    return internalSearchList(term, node, 1); 
    } 
} 

また、Node.leftとNode.rightのタイプはNodeである必要があります。

private class Node { 
    public String content; 
    public Node up; 
    public Node left; 
    public Node right; 
} 

Answer 2

私はあなたの質問が不明であるというコメントに同意しました。 しかし、二重リンクリスト（ヌル要素が許可されていない）で再帰的検索を実装する方法を探しているだけであると仮定します。もう1つの答えは既に言及しているので、私は、PageタイプをNodeのサブタイプにすると仮定します。実際、私は以下の例でそれを置き換えます。

二重リンクリストの実装と再帰そのものに関する誤解があるようですので、私は凝縮しているが実行中の例を挙げます。

提示しているコードには、再帰の終了条件がありません。残念ながら、ikichaのソリューションにも当てはまります。これを達成するための1つの方法（例えば、ヘルパーメソッドを使用して、不変式（start要素など）またはカウンタを再帰の1回の繰り返しから次の繰り返しに渡すことです。

この例の行node = node.leftは効果がありません。双方向で検索を行いたいのであれば（私がスケッチしたように）、なぜあなたの方向性が重要なのか興味があります。

public class DoubleLinked { 

private Node first; 
private Node last; 
private int size; 

private class Node { 
    public String content; 
    public Node left; 
    public Node right; 

    public Node(String content) { 
     this.content = content; 
    } 
} 

private void addElement(Node addedNode) { 
    if (first == null) { 
     first = addedNode; 
     last = addedNode; 

    } else { 
     last.right = addedNode; 
     addedNode.left = last; 
     addedNode.right = first;    
     last = addedNode; 
    } 
    size++; 
} 

private Node searchList(String term, Node node) { 
    int tries = 0; 
    if (node != null) { 
     return searchHelper(term, node.right, tries); 
    } 
    return null; 
} 

private Node searchHelper(String term, Node node, int tries) { 
    if (node == null || tries >= size) { 
     return null; 
    } 

    if (node.content.equals(term)) { 
     return node; 
    } else { 
     return searchHelper(term, node.right, tries); 
    } 
} 

public static void main(String[] args) { 
    DoubleLinked list = new DoubleLinked(); 

    list.addElement(list.new Node("first")); 
    Node startNode = list.new Node("second"); 
    list.addElement(startNode); 
    list.addElement(list.new Node("third")); 
    list.addElement(list.new Node("forth")); 

    Node r = list.searchList("forth", startNode); 
    System.out.println(r!=null?r.content:"term not found"); 
} 
}