Results 1 to 6 of 6
  1. #1
    cjw92 is offline Member
    Join Date
    Feb 2011
    Posts
    11
    Rep Power
    0

    Default Recursive Linked List method: RemoveAll

    The problem is: Remove all occurrences of a value from a linked list recursively.

    The method header is: private static Node removeAll(Node head, String value)

    Node head is the head of the list, String value is the value to be checked for removal.

    The code I have so far is:

    private static Node removeAll(Node head, String value)
    {
    if(head == null) return null;
    if(head.next == null)
    {
    if(head.value.equals(value))
    return null;
    else return head;
    }
    else
    {
    Node probe = head;
    if (probe.value.equals(value))
    {
    head = head.next;
    return removeAll(probe.next, value);
    }
    else
    {
    return removeAll(probe.next, value);
    }
    }
    }

    I think the right way to do this is that probe is supposed to find the spot to remove, and then I do head = head.next to actually remove it from the list. However, I am removing all elements but the last one when I run it. If anyone could tell me what I'm doing wrong I would appreciate it. Thanks.

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    You are making it much harder than it needs to be. Here is one stategy:
    Java Code:
    removeAll(Node head, String value) {
        if(head != null) {
            removeAll(head.next, value); // recursion all the way to the tail
            // delete nodes on the way back up
            if(....) {
                // delete node
            }
        }
    }

  3. #3
    cjw92 is offline Member
    Join Date
    Feb 2011
    Posts
    11
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    You are making it much harder than it needs to be. Here is one stategy:
    Java Code:
    removeAll(Node head, String value) {
        if(head != null) {
            removeAll(head.next, value); // recursion all the way to the tail
            // delete nodes on the way back up
            if(....) {
                // delete node
            }
        }
    }
    I don't understand how that would work, is the if(...) statement

    if(head.value.equals(value))
    {
    head = head.next;
    return removeAll(head.next, value);
    }

  4. #4
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    Is the list single or double linked? The pseudocode I provided is for a double linked list.

  5. #5
    cjw92 is offline Member
    Join Date
    Feb 2011
    Posts
    11
    Rep Power
    0

    Default

    Quote Originally Posted by Junky View Post
    Is the list single or double linked? The pseudocode I provided is for a double linked list.
    Oh that makes so much more sense now. Yeah I did not know there were double linked list, so is that the standard? And yeah it is a single linked list.

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    Since you have a single LinkedList what you have to do is build up a new List with the undesired Nodes omiitted.

    Lets say we have the following list: 1,9,2,9,3 and we want to remove all the 9's. Your recursion takes you all the way to the tail, ie the 3 node. Since there are no more node you return the current node (3 node). Your recursion goes back one level to the 9 node. Since this is a node you want to omit just return the node you got from the recursive call (ie the 3 node). Now go back another level to the 2 node. You return the current node PLUS the node you got from the recursive call (ie the 3 node). Back another level to the 9 node which you want to omit etc etc

Similar Threads

  1. Replies: 9
    Last Post: 11-04-2011, 03:09 AM
  2. Replies: 4
    Last Post: 02-21-2011, 09:34 AM
  3. Replies: 12
    Last Post: 10-10-2010, 11:17 PM
  4. Revised Linked List printing method question
    By CirKuT in forum New To Java
    Replies: 7
    Last Post: 12-12-2008, 10:21 PM
  5. Linked List removeAll Help
    By unc123w in forum New To Java
    Replies: 13
    Last Post: 09-30-2008, 02:41 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •