8.6. Linked List Add Operation

The main benefit of a linked list implementation is the fact that these structures can easily increase size by adding a new, dynamically allocated node object. The images below demonstrate how this might be accomplished if the instruction myList.add(2, "F") is executed.

  1. The method starts off by creating a Node object referenced by newNode containing the String to be added. Also, in this step, a temporary reference, temp, refers to the first node in the List.

    first add image

  2. We move temp to the next node in the list. Now, temp is located at index 1. We avoid modifying head as to not change the list itself. If we were to lose the head reference, we would lose access to the first node in the list.

    second add image

  3. Now that temp is located at the index directly preceding where we want to add, we can start modifying the references to correctly add newNode to our list. In this step, we set the next reference of newNode to the next value of temp.

    third add image

  4. In this step, the next field of the object referenced by temp is set to newNode.

    fourth add image

  5. This image represents the same structure as the previous image just redrawn without any local variables with the nodes lined up cleanly.

    fifth add image

Compare the above steps to the array list add operation. When there is space in the array for the new item, the linked list is much slower, comparatively. However, if there is not enough space in the array for the new item, then the linked list add operation is usually much faster! This is because it avoids the creation of a new array object and the loop required to transfer the contents from the old array to the new one.