4 Replies - 898 Views - Last Post: 21 March 2012 - 09:38 PM Rate Topic: -----

#1 Giere Drachios  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 15-February 12

Iterative and Recursive Linked List problems

Posted 21 March 2012 - 09:19 AM

Alright, I ran into a few problems programming an iterative and recursive linked list. This is my first time ever using linked list, so I'm not exactly sure where I went wrong. I followed my notes exactly. Anyways, it seems the issue is when I go to append the list. Here are the appends I am trying to use, and that seem to be having problems.

Iterative:
public void appendIter(int dx)
    {
        Node nxp = new Node (dx);
        //list is empty
        if(head == null)
        {
            head = nxp;
            return;
        }
        //list not empty
        while(nxp.getNext()!= null)
        {
            nxp.getNext();
        }
        nxp.setNext(nxp);
    }

and Recursive:
 public void appendRec1(int dx)
    {
        head = appendRec2(head, dx);
    }
    public Node appendRec2(Node hp, int dx)
    {
        Node nxp;
        if(hp == null) //found end
        {
            nxp = new Node (dx);
            return nxp;
        }
        //list not empty
        hp.setNext(appendRec2(hp.getNext(),dx));
        return hp;
    }


Thank you in advance!

Is This A Good Question/Topic? 0
  • +

Replies To: Iterative and Recursive Linked List problems

#2 The Adrian  Icon User is offline

  • New D.I.C Head

Reputation: 16
  • View blog
  • Posts: 47
  • Joined: 09-January 12

Re: Iterative and Recursive Linked List problems

Posted 21 March 2012 - 09:46 AM

In your iterative approach, you loop through the nxp node, you should be looping through the head Node.

And does getNext() just get the next node, or does it get it and increment the node calling it?

If it's the first one, then this is good. Create a temp and set it equal to head, loop while the next Node is != null as you have above, but in the body actually increment the Node but setting it equal to the next Node.

Then set the next node to nxp

Also in the recursive approach, don't pass in the next node. Pass in the Node and check the next and execute logic based on that. Also, I don't think in the first function you should set the head equal to the returned value.
Was This Post Helpful? 1
  • +
  • -

#3 Giere Drachios  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 15-February 12

Re: Iterative and Recursive Linked List problems

Posted 21 March 2012 - 10:18 AM

Alright, working on trying to get the iterative append working. I got the recursive one working, and it seems that my method that gets the length of the list is broken. Or my delete methods aren't deleting things properly.
I am trying to add in 4 numbers into the list iteratively, then printing the list and it's length, then deleting 3 of them and printing again. Then I delete the last (thus having an empty list), and do it again recursively.
This is what I get as output:

Iterative:
(Add 1, 2, 3, and 4. Print Length and then List)
Length: 1
List Data:
1
Not found.
Deleted: 1
Not found.
Deleted: 2
Not found.
Deleted: 5
Deleted: 4
List Data:
Length: 1
List is empty.

Deleted: 3

Recursive:
(Re-add 1, 2, 3, and 4. Print Length and then List)
Length: 4
List Data:
1
2
3
4
Deleted: 1
Deleted: 2
Not found.
Deleted: 5
Deleted: 4
List Data:
3
Length: 4

Here is the length and then the recursive delete method I am using, as well. The iterative delete seems to work, just that the append still isn't...
Get List Length:
public int lengthRec1()
    {
        return(lengthRec2(head));
    }
    public int lengthRec2(Node hp)
    {
        //end of list
        if(hp == null)
        {
            return 0;
        }
        //else
        return(1 + lengthRec2(hp.getNext()));
    }

Delete Recursively:
public void deleteRec1(int dx)
    {
        head = deleteRec2(head,dx);
    }
    public Node deleteRec2(Node hp, int dx)
    {
        //empty
        if(hp == null)
        {
            System.out.println("Not found.");
            return null;
        }
        //somewhere in the list
        if(hp.getData() == dx)
        {
            return(hp.getNext());
        }
        hp.setNext(deleteRec2(hp.getNext(),dx));
        return hp;
    }

As for the getNext, I have a Node class I am using.
private Node next;
//...
public Node getNext()
{
    return(next);
}
public void setNext(Node nextx)
{
    next = nextx;
}


I searched Google for help on this, but I can't seem to find any similar problems, so I must be overlooking something...
Thank you so much again for the help! I appreciate it! ^_^
Was This Post Helpful? 0
  • +
  • -

#4 Giere Drachios  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 15-February 12

Re: Iterative and Recursive Linked List problems

Posted 21 March 2012 - 09:12 PM

I figured it out earlier. Just thought I'd reply. Thank you for all the help!
Was This Post Helpful? 0
  • +
  • -

#5 The Adrian  Icon User is offline

  • New D.I.C Head

Reputation: 16
  • View blog
  • Posts: 47
  • Joined: 09-January 12

Re: Iterative and Recursive Linked List problems

Posted 21 March 2012 - 09:38 PM

Ah. That's good. I was in class so I got completely swept away with work. Glad you got it working, have fun
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1