Implementing a Linked list in Java - Part Two

Lets start where we left off in the last post.

Add a function that removes nodes from the end of our linked list. Here’s what our function definition looks like:

public T remove() {

}

Before we get into writing the function itself, consider our use cases:

An empty list (head equals null)
A list containing only one element (list of size one)
A list containing two or more elements (list of size > one)

Here’s how we will handle each case:

Do nothing and return null since there are no elements to remove. An alternative way to handle this would be to throw an exception, but for this implementation we will not.
Set head to null and decrement our size (from one to zero). Return the data contained in the head of the list.
Iterate through our list while keeping track of the current node and the previous node. Continue iterating until the current node refers to the last node in the list. Set the next node of the previous node to be null (effectively remove the last node from the list). Decrement (subtract by one) the size of the list and return the data stored in the last node.

Add code to handle a removing from an empty list. We will check for a null head and return null if found:

	if(head == null)
		return null;

Next add code to declare our result, return our result, and decrement the size of our list:

	T result;
     //add code to the get correct result and remove the node from the list here
	size--;
	return result;

Next add our if statement to handle the 2nd and 3rd use cases. By checking if head.next is equal to null we will know if our list has a size of 1 or a size of greater then one:

	if(head.next == null) {
     //add code to handle use case 2 here
	} else {
     //add code to handle use case 3 here
	}

Add code to handle a list of size one. For this case the result is the data contained within the head of the list (the only node in the list). After getting the result we set the head to null to remove the node:

		result = head.data;
		head = null;

Add code to handle a list of size > one. We need to first declare a node n that represents the node to remove. We also need to declare a node prev that represents the node before the node to remove in the list. To start with n will be equal to head.next and prev will be equal to head. We know that both n and prev will not be equal to null since we have checked for those conditions already in our function.

		Node<T> n = head.next;
		Node<T> prev = head;

Iterate through the linked list. At each step we declare set both n and prev to the next node in the list. At the end of this while loop the n will be equal to the last node in the list and prev will be equal to the node before the last node in the list.

		while(n.next != null) {
			n = n.next;
			prev = prev.next;
		}

Now that the n and prev nodes are set correctly we can remove the last node from our list by declaring prev.next to be equal to null. We also update our result to be equal to the data in the node removed.

		prev.next = null;
		result = n.data;

The completed remove function looks as follows:

public T remove() {
	if(head == null)
		return null;
	T result;
	if(head.next == null) {
		result = head.data;
		head = null;
	} else {
		Node<T> n = head.next;
		Node<T> prev = head;
		while(n.next != null) {
			n = n.next;
			prev = prev.next;
		}
		prev.next = null;
		result = n.data;
	}
	size--;
	return result;
}

Add a function that returns the element at a specified position in the list. The function definition looks as follows:

public T get(int index) {

}

Consider the use cases of our function:

An empty list (head is equal to null)
A negative index value
An index equal to zero
An index > 0 and < size of the list
An index >= size of the list

Here’s how we will handle each use case:

Return null since there’s no elements to get. An alternative to this would be to throw an exception. We will not do this in our implementation however.
Return null since an index must be positive (invalid input). An alternative to this would be to throw an exception.
Return the data of the head node since an index of 0 refers the the first node in the list.
Iterate through the list while keeping track of the index of the current element. Once the current index is equal to the index return the data at that index.
Return null since the index is not contained within this list. An alternative to this would be to throw an exception.

If the index is negative return null:

	if(index < 0)
		return null;

If the list is empty (head is equal to null) return null:

	if(head == null)
		return null;

If the index is equal to zero return the data in the head of the list. Also return null if we get the end of our function without finding the index (ie index >= size):

	if(index == 0)
		return head.data;
	//add code to get the data at the correct position here
	return null;

Declare our position to be zero (the start of the list) and a node n to refer to the current node in the list. N will be initialized to head.next:

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

Iterate through our list for each element increment our position by one. If our position becomes equal to the index we are looking for break out of our for loop. We want our position to be the index of the element contained in n:

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

Finally after the while loop if our position and index are equal then return the data in n:

	if(position == index)
		return n.data;

The return null statement added earlier will handle the case if the position is not contained within the list (ie index >= size).

The completed function looks as follows:

public T get(int index) {
	if(index < 0)
		return null;
	if(head == null)
		return null;
	if(index == 0)
		return head.data;
	int position = 0;
	Node<T> n = head.next;
	while(n != null) {
		position++;
		if(position == index)
			break;
		n = n.next;
	}
	if(position == index)
		return n.data;
	return null;
}

We’ll continue the implementation of our linked list in Implementing a Linked List in Java - Part Three

Data Structures

Implementing a Linked list in Java - Part Two

RECENT POSTS