How to Implement Linked Lists in Java

If you’re someone who is even remotely into Java, there is no way that you are not familiar with Linked Lists. A vast majority of technical interviews would include at least one question from linked lists and it is one of the most fundamental data structures in Computer Science.

Today, we'll be looking at some of the theory behind a Linked List and also how to implement this in Java. Because we like you so much, we'll also throw in some of the common operations done using linked lists, so, let’s get started!

What is a Linked List?

Think of a linked list as a collection of nodes with each entity having a reference to the next one or both the next and the previous nodes (in case of a doubly-linked list). Try to think of various real-life scenarios where you’ve encountered linked lists.

An easy way to visualise a linked list would be to look at a goods train.

A goods train has an engine, which can be thought of as the HEAD node. This is linked to the next bogie (that is a frame placed under the trains onto which the wheels of the train are fixed) and so on. The last bogie is not linked to any, and this can be thought of as a NULL link. To add a new bogie at the beginning, you need to unlink the engine from the first bogie and add the new bogie in between and then link the new bogie to the existing first one. These operations hold true for removing a bogie as well. Let’s try and apply this same visualisation to the code as well.

The above class will represent each node of our linked list and is known as the node. This is just a common way to name them, but you can name them absolutely anything as long as you understand the concepts. There will be a data field that holds whatever data you need. In this case, you'll choose to go with integer data, but this can be anything simple or complex. The next field is the link that holds a reference to the next node. When a new node is created with some data, this field will be set to null. Then the next step is to write the actual class that houses the implementation code of the various operations.

The above class has just one field and that is the head of type Node. When creating a new instance of the LinkedList class, this would be set to null. This is exactly like a goods train with just the engine since it doesn’t have any links yet.

Adding a node to a linked list

Now, you'll look at how you can add a node to a linked list. For this, we will create a new instance of the LinkedList class and call it a list. you'll then create three nodes, node1, node2, and node3 with data 10, 11, and 13 respectively. After that, you set the node1 as the head. Then you link node2 to node1 and node3 to node2 using the next field. For a clearer visualisation, we have shown the references as abc, def, and ghi.

Before you know it, you have just created your first ever linked list. But what if you want to insert a node to an existing linked list at the beginning? For this, you have to create a new node with some data, check it out below:

Then, you'll need to set the next field of the newly created node with the value in the head node. Lastly, you set the new node’s value to the head node. With just three lines of code, you have inserted a node at the beginning of a linked list.

Deleting a node from a linked list

Since you've seen how to add a node to a linked list, let’s see how you can delete a node as well. This is one of the easiest operations to do on a linked list. The first step is to check whether the head is null. This means that the list is already empty and you cannot delete anything. The next check is to see if the first node is pointing to null. This means that the list has just one node and you can set the head as null. If that is also not the case, you will retrieve the value from the next field of the first node and set it as the new head. This will remove the link to the current first node and will be cleared up by the garbage collector in Java. The resulting linked list will look like this:

Wrapping Up

You've now seen what a linked list is, how to implement one in Java and do some of the basic operations like adding and deleting a node. Several other operations can be done on linked lists like adding nodes at specified positions, deleting from specified positions, checking for loops, finding the merge points, etc. There are also circular linked lists and doubly linked lists which are different variations of a linked list. We'll be exploring more about these in our future articles, so stay tuned!

Like what you've read or want more like this? Let us know! Email us here or DM us: Twitter, LinkedIn, Facebook, we'd love to hear from you.