CODEWITHSUNDEEP
javalinked-listnodes
digiHarmonious
digiHarmonious

Reputation: 53

Can someone explain why/how Nodes from LinkedLists change without changing them directly in Java?

Sorry, the title of this question may not be entirely clear. I'm just having trouble understanding this sample question from my upcoming exam:

The following Node points to the following list of chars: head -> [a] -> [b] -> [c] -> [d]

where the list nodes are instances of the following class

public class Node {
     public char value;
     public Node next;
}

What will be printed after the following code executes?

Node ptr1, ptr2, p;
ptr1 = head;
ptr2 = head.next;
ptr1.next = ptr2.next.next;
ptr2.next.next = ptr1;
p = head;
head = head.next;
while(p!=null){
    System.out.print(p.value + " ");
    p=p.next; 
}

Apparently the answer is a d. Can someone explain this to me?

These were my steps toward solving the problem:

ptr1 = head; //ptr1 -> [a]->[b]->[c]->[d]

ptr2 = head.next; //ptr2 -> [b]->[c]->[d]

prt1.next = ptr2.next.next; //prt1 -> [a]->[d]

prt2.next.next=prt1; //prt2 -> [b]->[c]->[a]->[d]

p=head; //p-> [a]->[b]->[c]->[d]

head=head.next; // head-> [b]->[c]->[d]

So I was thinking that the answer was just iterating over the original Node (a, b, c, d), which obviously isn't the case, I just don't understand at what point "head" became anything than it's original state. Do the Node variables change the original Node somehow? This doesn't make sense to me from everything I know about Java so far. Sorry if this is a stupid question I am just failing to understand and I haven't been able to find anything online regarding this. Thanks.

Upvotes: 1

Views: 51

Answers (2)

Andreas
Andreas

Reputation: 159086

You should draw it on paper, so you can see what's going on.

The sequence is as follows:

 head → [a] → [b] → [c] → [d]

ptr1 = head;

       ptr1
         ↓
 head → [a] → [b] → [c] → [d]

ptr2 = head.next;

       ptr1  ptr2
         ↓     ↓
 head → [a] → [b] → [c] → [d]

ptr1.next = ptr2.next.next;

       ptr1  ptr2
         ↓     ↓
         ↓    [b] → [c]
         ↓           ↓
 head → [a] → → → → [d]

ptr2.next.next = ptr1;

       ptr1  ptr2
         ↓     ↓
         ↓    [b] → [c]
         ↓           ↓
 head → → → → → → → [a] → [d]

p = head;

       ptr1  ptr2
         ↓     ↓
         ↓    [b] → [c]
         ↓           ↓
 head → → → → → → → [a] → [d]
                     ↑
                     p

head = head.next;

       ptr1  ptr2        head
         ↓     ↓           ↓
         ↓    [b] → [c]    ↓
         ↓           ↓     ↓
          → → → → → [a] → [d]
                     ↑
                     p

Upvotes: 2

Silvio Mayolo
Silvio Mayolo

Reputation: 70267

You're correct up to this point.

prt2.next.next=prt1; //prt2 -> [b]->[c]->[a]->[d]

Then, on this next step, head hasn't changed. You're right about that. Now, head is pointing to [a] and always has been, so it's still pointing to [a], even though [a] has moved somewhere else.

p=head; //p-> [a]->[d]

Then we assign head to head.next, but that doesn't even matter because we never use head again. So we're iterating over [a] then [d], hence the output.

Upvotes: 1

Related Questions