Implementing a Linked List in Java - Part Three

Alright, back to implementing our linked list!

Add a function which inserts an element into a certain position in the list. The function definition looks as follows:

public void insert(int index, T data) {

}

Consider the use cases for our function:

1. An empty list (head is equal to null)
2. A negative index (less then zero)
3. An index of zero
4. An index > 0 and < size
5. An index equal to the size
6. An index greater then the size

Here is how we will handle each use case:

1. If the index is zero declare a newNode and add set it to be the new head and increment the size. If the index is not zero then do nothing.
2. Do nothing since the index is invalid. Alternatively a different way to handle this would be to throw an exception, but our implementation will not do this.
3. Declare a newNode and it to the beginning of the list. This means to set newNode.next to the head and the head to be equal to newNode. Increment size by 1.
4. Declare a newNode that contains the inputted data. Insert the new node in the correct position in the list. This will be done by iterating through the list while keeping track of both the previous and next nodes. Once the position in the list is correct set the prev.next to the newNode and the newNode.next to the next node. (this effectively adds the node to the list in the correct spot). Increment size by 1.
5. If the index is equal to the size then we add the newNode to the end of the list since that is the correct spot for it. Increment size by 1.
6. Do nothing since the index is invalid. Alternatively a different way to handle this would be to throw an exception, but our implementation will not do this.

First add code to return if the index is negative (< 0):

	if(index < 0)
		return;

Next add code to declare a newNode:

	Node<T> newNode = new Node<T>(data);

Handle if the index is equal to zero. We put our code to handle this case before the code to handle an empty list since for this case an empty list is still valid input.

	if(index == 0) { //add it to the beginning of the list
		newNode.next = head;
		head = newNode;
		size++;
		return;
	}

We simply set the next node of the newNode to be the current head and the new head is set to the newNode. We also increment the size and then return to finish executing the function.

Handle if the list is empty (head is equal to null):

	if(head == null)
		return;

Declare position, n, and prev variables. Position will hold the current position, n the next node, and prev the previous node in the list. These will be updated when we iterate through the list:

	int position = 0;
	Node<T> n = head.next;
	Node<T> prev = head;

Iterate through the list while updating position, n, and prev accordingly. We will exit the loop if our current position is equal to the index (ie we’re at the current position in the list to insert):

	while(n != null) {
		position++;
		if(position == index)
			break;
		n = n.next;
		prev = prev.next;
	}

At the end of this loop if n is equal to null then we have hit the end of the list.

Add an if statement to check for if we need to add the node to the end of the list or to a position in the middle of the list. If n is equal to null and the position is equal to index-1 then it means we need to add the node to the end of the list (ie. index is equal to size). If the position is equal to index then we need to add it in between our prev and n nodes.

	if(n == null && position == index-1) {
	//add code to add the node to the end of the list here
	} else if(position == index) {
	//add code to add the node to the correct spot in the middle of the list here
	}

If neither of the conditions in the if statement are meant then it means the index is greater then the size of our list. Therefore we do not add a new node in that case.

Set prev.next equal to the newNode and increment size by one. This will add the newNode to the end of the list:

		prev.next = newNode;
		size++;

Set prev.next equal to the newNode and newNode.next equal to n. Increment the size by one. This adds the newNode in the middle of the list in between the prev and n nodes.

		prev.next = newNode;
		newNode.next = n;
		size++;

The completed function looks as follows:

public void insert(int index, T data) {
	if(index < 0)
		return;
	Node<T> newNode = new Node<T>(data);
	if(index == 0) { //add it to the beginning of the list
		newNode.next = head;
		head = newNode;
		size++;
		return;
	}
	if(head == null)
		return;
	int position = 0;
	Node<T> n = head.next;
	Node<T> prev = head;
	while(n != null) {
		position++;
		if(position == index)
			break;
		n = n.next;
		prev = prev.next;
	}
	if(n == null && position == index-1) { //add it to the end
		prev.next = newNode;
		size++;
	} else if(position == index) { //add it to the correct spot in the middle of the list
		prev.next = newNode;
		newNode.next = n;
		size++;
	}
}

That is all for today! We will cover how to implement the Iterable interface for our linked list in Implementing a Linked List in Java - Part Four.

Data Structures