Recursive implementation of "append if not present" for linked list

Question

public bool add(int e)
    {
        if(head == null)
        {
            Node n = new Node 
            {
                element = e
            };
            head = n;
            return true;
        }
        Node t = head;
        if(t.next == null)
        {
            if(t.element == e)
            { return false; }
            Node n = new Node
            {
                element = e
            };
            t.next = n;
            return true;
        }
        t = t.next;
        this.add(e);

        return true;
    }

This is a code to add a new node in set. No duplicated values allowed. There is Main Class called Sets and one inner class called Nodes. I know Node t = head; is creating a problem is there anyway to make this recursive? Even passing extra optional parameters doesn't help.

I've changed title to match your code sample - looks like what you call "set" is actually singly linked list - Feel free to revert/change. Standard recursive implementation for it is "insert after first OR recursively call for list starting on second element". — Alexei Levenkov
– Alexei Levenkov, Commented Nov 25, 2013 at 3:30
It is linked list but i am using it to implement set. But i believe linked list is more general and will come up in search easily. — Shah
– Shah, Commented Nov 25, 2013 at 3:44

Pandacoder · Accepted Answer · 2013-11-25 03:43:36Z

If I understood your question correctly, to make it recursive you would need to split it into two functions, a public one for handling the head == null case, and a private one for handling n.next == null and is recursive.

public bool add(int e)
{
    if (head == null)
    {
        head = new Node { element = e };
        return true;
    }

    return add(head, e);
}

private bool add(Node n, int e) {
    if (n.element == e)
        return false;

    if (n.next == null) {
        n.next = new Node { element = e };
        return true;
    }

    return add(n.next, e);
}

However, I would suggest instead doing something akin to the following which does everything in one function:

public bool add(int e)
{
    if (head == null)
    {
        head = new Node { element = e };
        return true;
    }

    if (head.element == e)
        return false;

    Node n = head;
    while (n.next != null) {
        if (n.element == e)
            return false;
        n = n.next;
    }

    n.next = new Node { element = e };
    return true;
}

+1 this looks like almost what OP wants (pretty standard "recursively insert element into a list") - you may want to add support for predicate that checks if element already there in the list.
@AlexeiLevenkov I have added the predicate to check if the element already exists.

Collectives™ on Stack Overflow

Recursive implementation of "append if not present" for linked list

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related