Linked List Insertion

There are 3 possible ways to insert a new element into an existing linked list.

1. We can insert in the front (push)
2. We can insert at the end (append)
3. We can insert in between 2 nodes

1. Push Insert

• Inserting in the front of a linked list is also called the push operation.
• If you imagine a stack of plates and want to add another plate to it, you'll always add it to the top of pile of plates.  So when a list represents a stack of plates, the push operation is when the insert always happens in the front of the list.

Steps:

1. Create a new Node to hold the new element to be inserted
2. Set the next pointer of the new node to point to the current head of the list
3. Now make this new node the head of the list

      // Push  
      public void push(Type item) {  
           Node newNode = new Node(item, null);  
           newNode.next = head;  
           head = newNode;  
      }  

2. Append Insert

• Inserting in the tail or end of a linked list is also called the append operation.
• If you imagine yourself joining a queue of people, you'll join at the end of the queue.  So when a list represents a queue, the append operation is when the insert always happens in the end of the list.

Steps:

1. Create a new Node to hold the new element to be inserted
2. Create a pointer to traverse the list to the end
3. Check if the list is empty (head is null) in which case make the head as the new node and quit
4. If the list isn't empty, use the pointer to traverse to the end of the list.  The last element will have its next pointer point to null
5. Make the last node point to newNode

      // Append  
      public void append(Type item) {  
           Node current = head;  
           Node newNode = new Node(item, null);  
           if (head == null) {  
                head = newNode;  
                return;  
           }  
           while (current.next != null)  
                current = current.next;  
           current.next = newNode;  
      }  

3. Insert After Node

• Inserting between 2 nodes given a reference node involves traversal till the node is located and then insertion after that reference node.

Steps:

1. Create a new Node to hold the new element to be inserted
2. Make sure the reference Node after which insertion should take place is not null
3. Reset the newNode next pointer to point to the reference node's next pointer (In the figure the reference node is 4 ->2.  We want to make 5 -> 2 and 4 -> 5.
4. Reset reference node's pointer to point to newNode.

      // Insert after  
      public void insertAfter(Node refNode, Type item) {  
           if (refNode == null)  
                return;  
           Node newNode = new Node(item, null);  
           newNode.next = refNode.next;  
           refNode.next = newNode;  
      }