CODEWITHSUNDEEP
javadata-structureslinked-list
BritneyLar22
BritneyLar22

Reputation: 3

Understanding linked lists (Java)

can someone please tell me if I am correct? I am studying for a midterm.

x is a variable pointing to a linked-list node and not the last node on the list. t points to a new node that is not in the list. 

x.next = t; 
t.next = x.next;

I believe when it comes time to update t.next, x.next is no longer the original node following x, but is instead t itself. So it create a cycle in the list

t = x.next 
x = t;

I believe this does nothing to the list.

Thank you in advance!!

Upvotes: 0

Views: 1499

Answers (3)

Grim
Grim

Reputation: 2030

You can also do it threadsafe like this:

t.next = x.next; // let t and x point to the SAME next.
x.next = t;  // change the x.next to t(who has the old next)

Upvotes: 1

Niroshan
Niroshan

Reputation: 2064

You already have object x. This probably the current last element of the linked list. Now, you create a new object T and link it as the element after X

X    // Lets assume X.next == NULL. So linked list looks like this  X -> Null
X.next = T // Now X.next == T and T.Next == NULL, So linked list looks like this  X -> T -> Null. 
T.next = X.next // Now T.next == T. So linked list is  X -> T <->T

This way, when you reach the end of the linked list, it will always return the last element instead of returning NULL.

If you are writing a simple algorithm for this, first you have to create an element and then point its next variable to it self.<First_element>.next = <First_element>. So the logic will work for all the instances.

Here is a simple experiment.

class Node{
   Node next = null;
   int id =-1;
}

public class LinkedList{
   public static void main (String args[]){
      Node x = new Node();
      x.id = 0;
      x.next = x;

      // Now add a new element
      Node t = new Node();
      t.id  =1;
      x.next = t;
      t.next = x.next; // Now we have a linked list of 2 elements

      Node mynode = x;//First element of linked list
      for(int i =0; i < 3; i++){
        System.out.println(mynode.id);
        mynode = mynode.next;
      }

   }
}

Output:

0
1
1

Upvotes: 0

Deepu--Java
Deepu--Java

Reputation: 3840

In this case store node in temp variable. It won't create the cycle.

Object temp = x.next;
x.next = t; 
t.next = temp;

First you have list like this..

X--->Y----->Z-->

You want to insert a node t after X

Right now t is

t---->null

Step 1- Now we have temp pointing to X's next

x---->y----->z----->
      ^
      |
temp--

Step 2- Now x's next is pointing to t

x----->t---->

now main list is like this

temp---->y---->z---->

Step 3- Now t's next is pointing to temp which is only next pointer

temp---->y--->z---->
^
|
----------
          |
x---->t---

So resulting list is

x--->t---->y---->z----->

Upvotes: 0

Related Questions