Inserting into a Single Linked List

Note - The code examples used in this post are located at my GitHub account - Single Linked Lists

We have previously covered the process of performing a search on a single linked list. In that post, we used a pre-constructed list to provide the basis of our search operation.  Whilst that demonstrated how to go about searching through a single linked list, it didn't shed much light on how we could build our own lists from scratch. In this post, we'll cover the second of the three basic operations of a single linked list, insertion. 


Hints: 

There are a couple of things to take note of about inserting an item into a linked list.

1. Insertion requires us to manipulate the nextNode pointer reference. This means that when we create our new node with the data we want, we also need to set its nextNode to point to the current list. If there is no list, the new node becomes the head otherwise, we need to connect our new node to the existing list to keep it "linked".


2. With linked structures, there is generally no need to worry about the order in which the data is stored, therefore we can make the insertion operation easier by adding the new node to the front of existing list. This avoids us having to keep a pointer to the tail of the list, or to always traverse it to insert into the end.


3. As with the search operation, it is important to keep a reference to the head of our linked list since it is our access point. 

Inserting into an empty list:

Figure 1 - Inserting the new node (Jerry) into an empty list.

Jerry becomes the head of the list.

Inserting into Non Empty List:

Figure 2 - Inserting the new node (Jerry) into an non-empty list. 

Jerry becomes the head of the list, Jerry's nextNode now points to the rest of the list.

Note - The dotted lines in the figures above, illustrate the insertion operation that is required to link the newly created node to either the head or the existing list.

Data Structure Representation:

The data structure is the same as the one that we used with the search operation, however we'll be adding the following method(s) - 

1. setNextNode(Node newNodeTmp) - Set the nextNode pointer of the current node to point to the new node. This will allow us to change where a node points to.

/**
 * The Node class represents a single node
 * in a linked structure.
 * 
 * A node acts as container to allow us to
 * store data.
 * 
 * @author Sze Yick.
 */
public class Node {

 /**
 * The data that this node holds.
 */
 private String name;

 /**
 * The pointer to the next node.
 */
 private Node nextNode;
 
 /**
 * The constructor to initialise the new node.
 * @param nameTmp - The name to store in this node.
 */
 public Node(String nameTmp) {
    name = nameTmp;
    nextNode = null;
 }
 
 /**
 * Getter method to return the data in the name field.
 * @return The name in this node as a {@link String}
 */
 public String getName() {
    return name;
 }
 
 /**
 * Getter method to return the next node. The node
 * to be returned is the one that this node points to.
 * @return The next node as a {@link Node}
 */
 public Node getNext() {
    return nextNode;
 }

 /**
 * Set the pointer for this node to point
 * to another node, creating the link.
 * @param nextNodeTmp - The node to connect to.
 */
 public void setNext(Node nextNodeTmp) {
    nextNode = nextNodeTmp;
 }
}

Figure 3 - Updated node structure with setNext(Node nextNodeTmp).

Inserting into the head of a Single Linked List -

Since it does not really matter where we insert an item into our linked list, for this example we'll always insert the new item at the front of the list. This means that each time we insert an item, we'll need to ensure that -

1. If the list is previously non-empty, the nextNode pointer of our new node needs to point to the rest of the list. This will "link" our new node with the rest of the list, if we do not do this, then we'll lose the connection. 


2. Our new node will become the head of the list, meaning that we need to ensure that the head reference is updated to point to our new node. For non-empty lists, point #1 needs to be done first, otherwise by overwriting the reference to head, we'll lose the only reference to the start location of the rest of the list. 

Since we're inserting an item to the front of the list, we won't need to loop through the list itself, therefore reducing the number of steps required in our algorithm to the following.

1. Create a new node object and initialise it with the new data.


2. Get current head of the list and set it to the nextNode of our newly created node.


3. Update the current head reference to our newly created node. 

If we implement the above steps in code, we'll produce the following insertion method - 

/**
 * Insert an item into a linked list.
 * 
 * @param head - The current head of the list.
 * @param name - The item to insert into the new node.
 * @return newNode - The new node, that is the head of the list.
 */
 private static Node insertItemIntoList(Node head, String name) {
    Node newNode = new Node(name); // Create the new item
  
    // Update the current head of the list to be the nextNode of
    // the newly created node.
    newNode.setNext(head); 
  
    // Return the newly created node with the updated nextNode reference.
    return newNode;
 }

Figure 4 - Method to insert an item into a linked list.

As you can see, there are not many steps involved with inserting an item to the start of a linked list. In Figure 4, the newly created node is returned to the caller to allow for the head to be updated. 

Depending on the implementation, it is also possible to update the head reference within the method itself.

Inserting into the tail of a Single Linked List -

Although I did mention before that there is no real need to maintain insertion order with linked structures, we'll see in later posts that this might not always hold true when we come to the implementation of abstract data types such as queues and stacks. 

Even though there might not be a need to be able to insert an item to the tail (end) of a linked list, it's useful to know about how to do it anyway. There are generally two ways of inserting an item to the tail of a linked list, we'll cover both but only go through the code of one.

Recursively/Iteratively insert to the tail - 

Since we always have a reference to the head of the list, we can modify the methods from searching through a linked list to insert an item into the end by - 

1. Looping through the entire linked list to find where the nextNode is null (denotes the end of the list) and assigning our new node to it. 

This is definitely an easy way of inserting an item to the end of our list, since it re-uses knowledge that we have obtained from implementing the search methods. However it isn't the most efficient.

Inserting into the tail by keeping a reference -

Another way to insert an item to the end of a linked list is to always maintain a reference to the tail. This is essentially the opposite of what we've been doing up until this point by always maintaining a reference to the head.

In this case, instead of updating the head to point to our new node, we'll update the tail to point to our new node each time we insert. 

/**
 * Insert an item to the end of a linked list. 
 * 
 * We require a null check for the tail in the case
 * for an empty list. 
 * 
 * @param currentTail - The current reference to the last node.
 * in the list.
 * @param name - The item to insert.
 * @return newNode - The new node, that is the tail of the list.
 */
 private static Node insertItemIntoTail(Node currentTail, String name) {
    Node newNode = new Node(name); // Create the new item.
  
    // Update the nextNode of the current end to point to our
    // new node. 
    if (currentTail != null) {
        currentTail.setNext(newNode);
    }
  
    // Return the newly created node, this now becomes the end of our list.
    return newNode;


}

Figure 5 - Inserting an item to the end of the linked list.

Complexity - 

The worst case time complexity to insert an item into the head of a single linked list is O(1) constant time. This is because we always have a reference to the head, and irrespective of the size of our list, it is always going to take the same amount of time to insert an item at the beginning.

The worst case time complexity to insert an item into the tail of a single linked list is also O(1), since the insertion operation is to just update a reference. However it is not truly reflective of its performance against  inserting to the beginning of the list.

Recursively or iteratively inserting an item into the tail of a list requires at least a O(n) search operation to find the end of the list before the insertion is done. Although this initial search is not counted towards the time complexity to insert, in practice there would be a noticeable performance impact on significantly large lists in comparison to inserting it into the beginning of the list. There is an additional space complexity cost if this is performed recursively. 

If we maintain a tail reference we can also keep the worst case complexity to O(1) on insertion that can execute the task with the same performance as inserting it to the head. However in this instance we sacrifice on space by maintaining an additional reference to the tail of our list. In most cases this isn't too much of a problem, however if space is significantly limited, then this could cause an issue.

Summary - 

Inserting an item into a single linked list involves the creation of a new node and then updating either the head or tail pointers, depending on the chosen implementation. Care must be taken especially when updating the reference to the head of the list when we insert an item to the beginning of the list. If we accidentally update the reference before we append the rest of the list to the new node, we'll lose the connection to the rest of the list. If inserting into the end of the list, space and time complexity needs to be considered when choosing an implementation method as it could affect the responsiveness of an method.  In the next post, we'll cover the last of the three basic operations of a linked list, deletion.

Exercises - 

1. Implement the recursive/iterative method for inserting an item into a single linked list.


2. Run the code from InsertIntoEndOfSingleLinkedList and InsertIntoHeadOfSingleLinkedList classes and observe the differences in the output in the different insertion methods. Add additional items and observe the results.