Adding node at end of list

[wilsonz91]

Hello,
First off, i did try looking around the forum but i couldn't understand. Here's a few question which i need help with:

1) (adding node at head) i don't know how does the head will hold the reference to the next node, the code is like this:

//at node class, part of the code:
void setNext(Node next)
  {
      this.next = next;
    }

//at linklist class part of the code:
void addNode(int item)
    {
        Node newNode = new Node(item,null);
        
        newNode.setNext(head);
        head = newNode;
        
        System.out.println(" Node added into the list........");
        
    }

How does the head hold the reference to the next node?

2) (Adding node at end of list) I read that to do so, you have an object tail which you keep track. And then you assign the the newNode to the pointer of tail and then assign pointer of tail to tail.
i tried:

//tail was initialized to null in the first place.
if (head == null){
            head = newNode;
        }
        else{
            tail.next= newNode;
            tail = tail.next;
            }

someone(sorry i forgot who) suggested this method in another post. But it comes out the error "Null pointer exception, null"

So my question is, what is wrong with the code above and how do I keep track of the tail?

[Taywin]

OK, you have not shown what you have in your class's variable. From what I look at your code, I am assuming that you have your class declared as followed:

class YourClassName {
  private Node head;
  private Node tail;

  public YourClassName() {
    head=null;
    tail=null;
  }
  public YourClassName(Node newNode) {
    head = newNode;
    tail = newNode;
  }
}

Now, the head is holding a node reference (actually it is an object reference). Then when you add it in the head, you need to move your reference to the new node.

//at node class, part of the code:
void setNext(Node next) {
  this.next = next;
}

//at linklist class part of the code:
void addNode(int item) {
  Node newNode = new Node(item,null);
  newNode.setNext(head);
  head = newNode;
  System.out.println(" Node added into the list........");
}

// now what it looks like inside addNode() should be like this...
// current link list you have
//     head -> nextNode1 -> nextNode2 -> null
// you create a new node which would not link to anything yet
//     newNode -> null
// now you set the next of newNode to head
//     newNode -> head -> nextNode1 -> nextNode 2 -> null
// now you move your head to hold on the newNode reference
//     head -> oldHead -> nextNode1 -> nextNode2 -> null
// Because your old head still have its nextNode pointing to nextNode1
// doesn't mean that it will disappear. What you did is to just change
// the reference pointing to the oldHead to the newNode. The newNode
// is holding the oldHead reference in its next, so nothing is lost here.

So the same thing happens with tail node... Though, why do you need head & tail anyway??? If you want capability to add to tail, you could simply traverse to the end of the node and add it. Would it speed up the process to have a tail node? To me, it is insignificant.

[kramerd]

It is significant if you have a million nodes. You won't need to traverse to the end of the list if you simply maintain a tail reference to the last node.

[wilsonz91]

Ok i get what you mean. So now how do i point to the previous one using tail? something like the one i put up? because to me it seems fine but it pops out error

[kramerd]

Think about what the list looks like at each step when you have an empty list, one node, two nodes, three nodes, etc. I find it helps to draw pictures when working with linked lists.

To begin with, both head & tail are null.
When one node is added, both head and tail point to that node.
When two nodes are added, head points to the 1st, 1st points to 2nd and tail also points to 2nd.
When 3 nodes are added, head points to 1st, 1st points to 2nd, 2nd points to 3rd and tail also points to 3rd.

Make sure you are accounting for all of the conditions above. In particular, when the first node is added, are you making both head and tail point to it?

[Taywin]

It is significant if you have a million nodes. You won't need to traverse to the end of the list if you simply maintain a tail reference to the last node.

Still doesn't make sense. If I want the node right before the last node (million-1), does it really help because you still have to traverse almost the whole list except one anyway??? Unless the list is a doubly linked list, it would make sense.

[kramerd]

Taywin, you are right. It makes more sense if you have a doubly linked list.

[wilsonz91]

I've a question, the setNext() method is to put a reference or setting the next Node? eg:

[value, reference]

node 1: [10, points to 2]
node 2: [20, points to 3]
node 3: [30, points to 4]
node 4: null

For adding at end of list, i tried:

Node newNode = new Node(item,null);
        
        
        if (head == null){
            head = newNode;
            tail = newNode;
        }
        else{
           for (int i=1;i<=listCount;i++)
                 tail = tail.getNext();
            
            newNode.setNext(tail);
            }
            listCount++;

problem is at the tail = tail.getNext() . Shouldn't the tail point to null and then we assign the newNode to it?

[kramerd]

First of all, if you maintain a pointer to the tail, you don't need a loop to get to the end. In your example list, head would point to node 1 and tail would point to node 3. So to add a new node at the end of the list, you would first make tail.next point to item, and then make tail itself point to item. The first step hooks up the new node to the end of the list by making node 3's next point to it (because tail points to node 3). The second step updates the tail pointer to make sure it always points to the last node in the list.

[Taywin]

Are you trying to add the node to the tail? Hmm.. Let me try to draw it out for you.

/*
This is the case when the list is empty...
1) head & tail are null
  head = null
  tail = null

2) create a new node
  newNode -> null

3) hook it up
  newNode -> null
     ^
   head
   tail


This is the case when there exist at least one node in the list...
current list:
  node1 -> node2 -> node3 -> null
    ^                 ^
  head               tail

add a new node at tail:
1) create a new node
  newNode -> null

2) hook the node
 2.1) insert the node to tail

  node1 -> node2 -> node3 -> newNode -> null
    ^                 ^
   head              tail

 2.2) change the reference of the tail to point to the new tail

  node1 -> node2 -> node3 -> newNode -> null
    ^                          ^
   head                       tail
*/

[Lior_1]

try an add to tail code

final* chain(final* first, Dust* info)
{
    final* END = (final*)malloc(sizeof(final));
END->avgs = info->totals / info->size;
END->x = (info->x1 - info->x0) / 2;
END->y = (info->y1 - info->y0) / 2;
END->size = info->size;
END->move = NULL;
final* temp = first;
while (temp->move != NULL)
{
    temp = temp->move;
}
    temp->move = END;
    return first;
}

[JamesCherrill]

Hi Lior

You have just joined an old thread about Java programming.

If you want relevant answers, please start a new thread of your own, explain what help you want, and tag it with the appropriate language.