CODEWITHSUNDEEP
javalinked-listsingly-linked-listdoubly-linked-list
Drew
Drew

Reputation: 1261

understanding linked lists

I am having trouble understanding linked lists from my course. The biggest problem I seem to have is how the data is stored. I see the code mainly add(x) add a new node in the list but it does not seem to make sense.

The code for add. 

boolean add(T x) {
  Node u = new Node();
  u.x = x;
  if (n == 0) {
    head = u;
  } else {
    tail.next = u;
  }
  tail = u;
  n++;
  return true;
}

This is directly from the textbook of the course I am taking. I went online to find more resources and I found this code on GITHUB from a far more detailed textbook Source. The code is far to long to just paste.

so over all I see classes named 'Head' 'Tail' and 'u' storing information like [Head]->[u]->[Tail]. Further as I read the add method I visualize the stored information look like [Head]->[u]->[u]->[u]->[Tail].

How does each node know which 'u' node to look at. Each one is referencing u node. Either u is being over-rided each time, or getting u info will return all the u's value's. how does the node.next differentiate each u node? Shouldn't the code rather than:

add(x) {
  Node u = new Node();
  u.x = x;
}

be more like:

add(x,y) {
  Node y = new Node();
  u.x = x;
}

So each node has a different name to link to [Head]->[a]->[b]->[c]->[Tail]

Upvotes: 0

Views: 113

Answers (3)

Suat Keskin
Suat Keskin

Reputation: 114

From java.util.LinkedList the Node class described as below:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Node holds both next and prev nodes, so every node knows its previous and next node.

Upvotes: 0

Hugo Sousa
Hugo Sousa

Reputation: 1926

So, you want to add a node to your linked list.

This creates the node u, with the respective info x.

Node u = new Node();
u.x = x;

Now, there's 2 options:

A - this is the first node you're adding to the linked list

B - there are already node(s) on the list, and you're adding another one.

This is where the if enters. 

if (n == 0) {
  head = u;
} else {
  tail.next = u;
}

A - If n (the counter of nodes in the list) equals 0, then it's empty. So, the node u is the head of it.

B - Otherwise, you're adding a new node after the actual tail of it, so you add a reference to the actual tail saying this node will be the next one.

And finally, you have to say that the node you're adding is the new tail of the linked list (if it's empty, then u will be head and tailsimultaneously). You also need to increment the counter of nodes n.

tail = u;
n++;

Upvotes: 0

sh4nkc
sh4nkc

Reputation: 358

The variable names itself do not matter in the sense that you think they do. u is just pointing to an instance of Node.

Let's say you want to create a linked list of integers:

You do add(1). At this point, n=0. In the add method, a new node is initialized. We just refer to it as u. Now, we set the value to be 1. Till now, we have created a Node with its value equal to 1.

Since, n=0, our head will also now refer to this Node. We increment, n++, to keep track of the current length of the list. We also make our tail refer to the newly added node because we always add to the end of the list.

Now, you do add(2). At this point, n=0. In the add method, a new node is initialized. We just refer to it as u. Now, we set the value to be 1. We don't need to update the head since 1 is the first node of list.

But, we need to add 2 to the end of the list. This means that the tail has to refer to the newly created Node whose value is 2. So, how do we do that? Well, tail as of now has been referring to the node whose value is 1. So, we just update that node's next to point to the same node that u is pointing to (since this is the newly created Node that we want to add to the end of the list).

To finish off, we will increment n and set our tail to point to the node we just added.

Upvotes: 2

Related Questions