CODEWITHSUNDEEP
javarecursionlinked-listdoubly-linked-list
Lucas
Lucas

Reputation: 173

Search Double Linked List Java Recursively

I am trying to search a doubly-linked list in Java for a term, and return it if found. Here is my code so far:

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;
}

My algorithm is basically:

Edit with my question, sorry: I cannot get it to search down to bottom levels and having trouble understanding where I have gone wrong.

Any help would be appreciated!

Upvotes: 0

Views: 1290

Answers (2)

Johnson
Johnson

Reputation: 358

I got to agree with the comments that your question is unclear. However, I assume you are just looking for a way to implement a recursive search on a double linked list (in which null elements are not allowed). As the other answer already mentions, I assume type Page to be a subtype of Node. In fact, I will substitute it in my example below.

Since there seems to be some misconception about implementing a double linked list and about recursion itself, I will give a condensed but running example.

The code you are presenting lacks a termination condition for the recursion. Which, unfortunately, also holds true for ikicha's solution. One way (amongst others) to accomplish this is to use a helper method to pass an invariant (eg. the start element) or counter from one iteration of the recursion to the next one.

The line node = node.left in your example has no effect. If you wanted to achieve a search in both directions (as ikicha sketched) I would be interested in why direction matters for you.

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");
}
}

Upvotes: 0

ikicha
ikicha

Reputation: 153

I think your algorithm computes same node several times because move left and find all right nodes of the left one repeatedly.

You can find node by search two direction each from start node.

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);
  }
}

And also I think the type of Node.left and Node.right must be Node.

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

Upvotes: 0

Related Questions