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,807
    Rep Power
    10

    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,807
    Rep Power
    10

    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,807
    Rep Power
    10

    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, 04:09 AM
  2. Replies: 4
    Last Post: 02-21-2011, 10: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, 11: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
  •