Arrays are great for storing data. We have also seen that any element of an array can be read in O(1) time. But arrays are fixed in size. Changing the size of an array means creating a new array and copying all the elements to the original array. The simplest recourse to the resizing problem is to store each element in a different object and then hold a reference in each element to the next element. This way, the process of adding a new element will just involve creating the element and attaching it at the end of the last element of the original linked list. In another variation, the new element can be added to the beginning of the existing linked list:
Figure 3: An example of a linked list
Figure 3 shows an example of a linked list. The arrows represent a reference. Each element is stored in a wrapper object that also holds a reference to the next element wrapper. There are two additional references to the first and last elements, which are required for any operation to start. The last reference is optional, but it improves the performance of appending to the end vastly, as we shall see.
To begin the discussion, let's create a linked list node in the following way:
public class LinkedList<E> implements Iterable<E>, Visualizable { First, we create a Node class inside the LinkedList class, which will act as a wrapper for the elements and also hold the reference to the next node:
protected static class Node<E> {
protected E value;
protected Node next;
public String toString(){
return value.toString();
}
}
int length = 0;
Node<E>[] lastModifiedNode; Then, we must have references for the first and last elements:
Node<E> first;
Node<E> last; Finally, we create a method called getNewNode() that creates a new empty node. We will need this if we want to use a different class for a node in any of the subclasses:
protected Node<E> getNewNode() {
Node<E> node = new Node<>();
lastModifiedNode = new Node[]{node};
return node;
}
}At this point, the unfinished class LinkedList will not be able to store any element; let's see how to do this, though. Notice that we have implemented the Iterable interface. This will allow us to loop through all the elements in an advanced for loop.
Appending at the end is achieved by simply creating a link from the last element of the original linked list to the new element that is being appended and then reassigning the reference to the last element. The second step is required because the new element is the new last element. This is shown in the following figure:
Figure 4: Appending at the end of a linked list
There is a small difference when you append an element to a linked list that is empty to start with. At this point, the first and last references are null, and this case must be handled separately. The following figure explains this case:
Figure 5: Appending to an empty linked list
We will achieve this by using the following simple code as is. We return the node that has just been added. This is helpful to any class that is extending this class. We will do the same in all cases, and we will see the use of this while discussing doubly linked lists:
public Node<E> appendLast(E value) {
Node node = getNewNode();
node.value = value; We try to update the reference of the current last node only if the list is not empty:
if (last != null)
last.next = node;Then, we must update the last reference as the new element is not going to be the last element:
last = node;
Finally, if the list is empty, the new element must also be the first new element and we must update the first reference accordingly, as shown in the preceding figure:
if (first == null) {
first = node;
}
length++;
return node;
}Notice that we also keep track of the current length of the list. This is not essential, but if we do this, we do not have to traverse the entire list just to count how many elements are in the list.
Now, of course, there is this important question: what is the time complexity of appending to a linked list? Well, if we do it the way we have done it before—that is, by having a special reference to the last element—we don't need any loop, as we can see in the code. If the program does not have any loops, all operations would be one-time operations, hence everything is completed in constant time. You can verify that a constant function has this complexity: O(1). Compare this with what was appended at the end of an array. It required the creation of a new array and also had O(n) complexity, where n was the size of the array.
Inserting an element at the beginning of a list is very similar to appending it at the end. The only difference is that you need to update the first reference instead of the last reference:
public Node<E> appendFirst(E value) {
Node node = getNewNode();
node.value = value;
node.next = first;
first = node;
if (length == 0)
last = node;
length++;
return node;
}Insertion at an arbitrary position can be achieved in the same way we perform an insertion in the first element, except that we update the reference of the previous element instead of the first reference. There is, however, a catch; we need to find the position where we need to insert the element. There is no way to find it other than to start at the beginning and walk all the way to the correct position while counting each node we step on.
Figure 6: Insertion of an arbitrary element into a linked list
We can implement the idea as follows:
public Node<E> insert(int index, E value) {
Node<E> node = getNewNode(); First, we take care of the special cases:
if (index < 0 || index > length) {
throw new IllegalArgumentException("Invalid index for insertion");
} else if (index == length) {
return appendLast(value);
} else if (index == 0) {
return appendFirst(value);
} else { As mentioned earlier, we walk all the way to the desired position while counting the nodes, or in this case, counting the index in the opposite direction:
Node<E> result = first;
while (index > 1) {
index--;
result = result.next;
} Finally, we update the references:
node.value = value;
node.next = result.next;
result.next = node;
length++;
return node;
}
}What is the complexity of this algorithm? There is a loop that must run as many times as the index. This algorithm seems to have a running time that is dependent on the value of the input and not just its size. In this case, we are only interested in the worst case. What is the worst case then? It is when we need to step on all the elements of the list, that is, when we have to insert the element at the end of the list, except for the last element. In this case, we must step on n-1 elements to get there and do some constant work. The number of steps would then be T(n) = C(n-1)+K for some constants C and K. So, T(n) = O(n).
Finding the value of an arbitrary element has two different cases. For the first and last element, it is simple. Since we have direct references to the first and last element, we just have to traverse that reference and read the value inside it. I leave this for you to see how it could be done.
However, how do you read an arbitrary element? Since we only have forward references, we must start from the beginning and walk all the way, traversing references while counting steps until we reach the element we want.
Let's see how we can do this:
public E findAtIndex(int index) { We start from the first element:
Node<E> result = first;
while (index >= 0) {
if (result == null) {
throw new NoSuchElementException();
} else if (index == 0) { When the index is 0, we would have finally reached the desired position, so we return:
return result.value;
} else { If we are not there yet, we must step onto the next element and keep counting:
index--;
result = result.next;
}
}
return null;
}Here too, we have a loop inside that has to run an index a number of times. The worst case is when you just need to remove one element but it is not the last one; the last one can be found directly. It is easy to see that just like you insert into an arbitrary position, this algorithm also has running time complexity of O(n).
Figure 7: Removing an element in the beginning
Removing an element in the beginning means simply updating the reference to the first element with that of the next element. Note that we do not update the reference in the element that has just been removed because the element, along with the reference, would be garbage-collected anyway:
public Node<E> removeFirst() {
if (length == 0) {
throw new NoSuchElementException();
} Assign the reference to the next element:
Node<E> origFirst = first;
first = first.next;
length--; If there are no more elements left, we must also update the last reference:
if (length == 0) {
last = null;
}
return origFirst;
}Removing an arbitrary element is very similar to removing an element from the beginning, except that you update the reference held by the previous element instead of the special reference named first. The following figure shows this:
Figure 8: Removing an arbitrary element
Notice that only the link in the linked list is to be reassigned to the next element. The following code does what is shown in the preceding figure:
protected Node<E> removeAtIndex(int index) {
if (index >= length || index < 0) {
throw new NoSuchElementException();
} Of course, removing the first element is a special case:
if (index == 0) {
Node<E> nodeRemoved = first;
removeFirst();
return nodeRemoved;
} First, find out the element just before the one that needs to be removed because this element would need its reference updated:
Node justBeforeIt = first;
while (--index > 0) {
justBeforeIt = justBeforeIt.next;
} Update the last reference if the last element is the one that is being removed:
Node<E> nodeRemoved = justBeforeIt.next;
if (justBeforeIt.next == last) {
last = justBeforeIt.next.next;
} Update the reference held by the previous element:
justBeforeIt.next = justBeforeIt.next.next;
length--;
return nodeRemoved;
}It is very easy to see that the running time worst case complexity of this algorithm is O(n)—which is similar to finding an arbitrary element—because this is what needs to be done before removing it. The operation of the actual removal process itself requires only a constant number of steps.
Since we are working in Java, we prefer to implement the Iterable interface. It lets us loop through the list in a simplified for loop syntax. For this purpose, we first have to create an iterator that will let us fetch the elements one by one:
protected class ListIterator implements Iterator<E> {
protected Node<E> nextNode = first;
@Override
public boolean hasNext() {
return nextNode != null;
}
@Override
public E next() {
if (!hasNext()) {
throw new IllegalStateException();
}
Node<E> nodeToReturn = nextNode;
nextNode = nextNode.next;
return nodeToReturn.value;
}
}The code is self-explanatory. Every time it is invoked, we move to the next element and return the current element's value. Now we implement the iterator method of the Iterable interface to make our list an iterable:
@Override
public Iterator<E> iterator() {
return new ListIterator();
}This enables us to use the following code:
for(Integer x:linkedList){
System.out.println(x);
}The preceding code assumes that the variable linkedList was LinkedList<Integer>. Any list that extends this class will also get this property automatically.