CODEWITHSUNDEEP
javadata-structureslinked-list
Shan
Shan

Reputation: 381

Will adding a Node recursively work in any position of a Singly Linked List?

I learned that to add a Node to the front of the Singly Linked List the code is 

head = new Node(data,head);

I am confused behind the logic for if this will work for instance, in some random index in the middle of the list. I tried implementing the code:

 public void add(int index, int data) {
        if(index == 0) {
            head = new Node(data,head);
        } else {
            for(int pos = 0; pos < size; pos++) {
                if(pos == index) {
                        //Add it//
                        head = new Node(data,head);
                        size++;
                    } else {
                        //Go to the next Node//
                        head = head.getNext();
                    }
                }
            }
        }
    }

I'm still kind of confused on this logic, because I feel like this will cause the linked list after the adding has completed to lose it's data. So if I add in index 5 for example, then 6, 7,8,9, etc. will no longer be a part of the linked list.

Upvotes: 0

Views: 184

Answers (2)

i_v_harish
i_v_harish

Reputation: 161

You should be more clear on how a Singly Linked List works. I would suggest you go through some good article or a video tutorial. And what you are doing here is iteration, not recursion.

A head is pointer/reference to a node that is at the starting of the Linked List.

So, when does a head change?

When you insert a new node at the 0th (assuming you are starting from 0) or when you delete the first node.

In every other case, the head remains the same. Adding to the front of the Linked List would be same as adding a newNode where index=0. The logic to add a newNode at any index should be same. However, in case of adding to the 0th index, you should reset your head to the newNode.

Your code seems to be flawed. Take an input and try to go step by step. It might help you to pin down the flaw, if any. Cheers.

Upvotes: 1

Zarwan
Zarwan

Reputation: 5777

To add a node to the beginning of your linked list that line will work, assuming you have something like this in your constructor:

setNext(head);

This way you don't lose track of your list. If you simply reset your head without setting up the reference to the rest of the list you will lose it.

However your index 5 example doesn't apply here. In that case you're inserting a node into the middle of your linked list, not at the beginning, so the process would be different. For example, if you wanted to insert something in position 5 you would have to set the next of the node in position 4 to your new node and the next of your new node to the node currently in position 5. See this for a more detailed explanation: http://www.mycstutorials.com/articles/data_structures/linkedlists

Upvotes: 0

Related Questions