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:
Before we get into writing the function itself, consider our use cases:
Here’s how we will handle each case:
Add code to handle a removing from an empty list. We will check for a null head and return null if found:
Next add code to declare our result, return our result, and decrement the size of our list:
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:
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:
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.
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.
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.
The completed remove function looks as follows:
Add a function that returns the element at a specified position in the list. The function definition looks as follows:
Consider the use cases of our function:
Here’s how we will handle each use case:
If the index is negative return null:
If the list is empty (head is equal to 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):
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:
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:
Finally after the while loop if our position and index are equal then return the data in n:
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:
We’ll continue the implementation of our linked list in Implementing a Linked List in Java - Part Three