Inserting a Node at the End of a Linked List

Suppose we want to add a new node with data as the last node of the list.

Algorithm to insert a new node at the end of a linked list

Step 1: IF AVAIL = NULL
          Write OVERFLOW
          Go to Step 10
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL.NEXT
Step 4: SET NEW_NODE.DATA = VAL
Step 5: SET NEW_NODE.NEXT = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR NEXT != NULL
Step 8: SET PTR = PTR.NEXT
       [END OF LOOP]
Step 9: SET PTR NEXT = NEW_NODE
Step 10: EXIT


we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. In the while loop, we traverse through the linked list to reach the last node. Once we reach the last node, in Step 9, we change the NEXT pointer of the last node to store the address of the new node. Remember that the NEXT field of the new node contains NULL, which signifies the end of the linked list.

Java Example:

class Node{
Node next;
int data;
}

Node insert_end(Node start, int num)
{
Node ptr, new_node;
int num;
new_node = new Node();
new_node.data = num;
new_node.next = null;
ptr = start;
while(ptr.next != null)
ptr = ptr.next;
ptr.next = new_node;
return start;
}