Implementing a Linked List in Java

Today we are going to have a look at an interesting data structure, the Linked List.
We’ll start of by describing the nature of a Linked List, before implementing a Linked List in Java.

What is a Linked List?

A linked list is a collection of data elements, stored in linear order.
Unlike arrays, linked lists are not organized based on their physical placement in the memory. Linked List elements (nodes from now on), are stored using pointers.
Each node in a Linked List is composed of two elements – the actual data element, and a pointer to the next node in the List.
Below you’ll see a simple visualization of a Linked List composed of three nodes:

visualization of a linked list

The above illustration is of a singly linked list – which is the type of linked list we focus on in this article.

Advantages and drawbacks of the LinkedList

You may be wondering why one would ever want to use a Linked List, instead of an array.
Surely, having data scattered all across your memory must be a huge drawback?
As you may already guessed; No, it is not!

Consider an array, which stores data continously.

Visualization of an array

Suppose you want to insert a new data element at the very front of the array.
If we were to do that, all the elements in the array must be shifted one position up. Thus, we’ll have to loop through the entire array! You don’t have to be an expert programmer to understand that for an array of 10000+ elements, this is very inefficient.

Now, suppose we perform the same operation on a Linked List. As we now know, a Linked List is composed of nodes, which have a pointer to the next node.
Insertion at the front of a Linked List only require us to make the inserted node point to the previous first node in the list.
The following figure illustrates this scenario quite nicely.

visualization of insertion into a linked list

Another quite nice advange of the Linked List is that the size is dynamic; we don’t have to specify the max number of elements. When it comes to arrays, this is something we have to do. If you’re somewhat unfamiliar with arrays, or need a quick refresh, check out my article on arrays here.
Disclaimer: The ArrayList from the Java Collections API doesn’t require that you specify an array size, but what happens under the hood here is out of scope for this article.

Okay, so the linked list does have some advantages over arrays. But what are the drawbacks?

When it comes to linked lists, random access (or direct access) is not something that can be done efficiently. Say for example that we want to access the K’th element in the list. To do that, we have to loop through the entire chain of nodes. With an array, you can simply call get(K).

On top of that, there is also the issue with extra memory space. Remember that each element in a linked list have a reference to the next element, which leads to what we call overhead, or extra memory space.

If you didn’t quite understand everything, don’t worry.  The following list sums it up quite nicely:

  •  The linked list consists of nodes.
  •  Each node consists of (at least) two parts: the actual data, and a pointer to the next node.
  • The nodes in a linked list are stored in a linear manner – not continously, as with arrays.
  • Linked lists have dynamic size, unlike arrays.
  • Insertion and deletion are performed very efficiently, in constant time, O(1).
  • Random / direct access to a linked list is not efficient, O(N). Consider using an array.

If you haven’t seen the notation O(1) and O(N), check out my article on Algorithm Analysis.

Implementation of a Linked List in Java

Now that you have a basic understanding of what a linked list is, lets do the fun part; writing some code!

Before diving right into it, let’s explain the supported methods:

  • Inserting x at the front of the list: 
    Store the current front element in a temporary variable, temp = front. Set front element to x, front = x. Make x.next = temp
  • Inserting x at the end of the list:
    Loop until the end. lastNode.next = x
  • Inserting y after x:
    Loop until x is found. Set y.next = x.next. Set x.next = y.
  • Inserting y before x:
    Loop until x is found. Make the node previous to x point to y.  Set y.next = x
  • Deleting x:
    Make the node previous to x point to x.next. In other words, we are bypassing x.

Note about the LinkedListIterator.

An iterator is used to iterate through a collection of data elements. In this custom implementation, we create a custom iterator. The iterator class, LinkedListIterator, is implemented as an inner class. The definition of an inner class is a class that is inside another class, but without the keyword static.
With inner classes, we can reference to outer class’ variables implicitly. This means that in our implementation, we write

private LinkedListIterator {
next = front
}

instead of

private LinkedListIterator(LinkedList ll){
    next = ll.front
}

As you see, with inner classes, we do not need to keep an explicit reference to the outer class.

One last thing about the LinkedListIterator; as the Java documentation for the Iterator-interface specificies, the Iterator should be invalidated if the current list is changed. Let’s assume we’re iterating through the Linked List. If the list changes, there is no way for the Iterator to know about the change. Thus, we have to throw an exception if the current list is modified. In our code, we keep track of these changes with a simple counter, which keeps track of number of modifications (insert and delete).

Please refer to the comments in the Java implementation for further information. Click on the classnames to see the implementation!

 

Tutorials will only get you so far..
If you wish to expand your Java skill-set and become an advanced Java developer, I personally recommend the Comprehensive Java Course by Edureka.
You can get 25% with the coupon code LIMITED25 😉

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *