LinkedList from Scratch Featuring Java.
LinkedLists belong to a big list of data structures which can also include Arrays, Binary Search Trees, Graphs, Queues, and Stacks. It is used to store data in a linear fashion much like an array. However, the elements in a LinkedList are not stored in a contiguous place in memory.
Each element in the LinkedList is represented by a node. These can have many properties inside but a must-have for every node is a pointer to the next node; represented by the “next” property. The head represents the beginning of the list and the tail represents the end. The tail’s next property points to null since the tail is at the end of the list. If the list contains only one node, that node will be the head and the tail.
Java’s LinkedList is packaged with tons of useful methods. We are only focusing on a couple of them.
- add(): add’s a node to the end of the list.
- getFirst(): retrieves the head.
- getLast(): retrieves the tail.
- contains(): verifies the existence of a value within the list.
- removeFirst(): removes the head of a list.
- removeLast(): removes the tail of the list.
Alright, Let’s start building this LinkedList.
Prerequisites
- IntelliJ | Eclipse | VsCode installed
- Willingness to learn
I will be using IntelliJ for the rest of this tutorial. You can use any IDE of your choice.
Let’s create a new project, you can call it whatever you please. I called my project “celebrities” since my list’s values would consist of different celebrities. Make sure you are on the new project tab on the left side menu. I created a git repository to track my changes. Since we are coding in Java, be sure to select Java in the languages section. We will be using the IntelliJ build system. Afterward, click on create.
Let’s create a new package under the src directory. Right-click on the src directory, hover over new and select Package. It will prompt you to enter a name for the package. Let’s call it, LinkedList.
In Java, our program will start with the Main class, so let’s add that as our entry-point. You can add a class by right-clicking the LinkedList package and hovering over new and then clicking the Java Class option. It will then prompt you to enter a name for the class, we will call it Main. There are options below, be sure to select the Class option.
If you decided to use Git along with this project, it will ask if you would like to add the file to Git. Press Ok. Then we should have some code like this.
Within the main class, we need to invoke LinkedList. Type this out, don’t import java.util.LinkedList. Let’s create the main function, we won’t return anything so we will use the void keyword. Inside the main function, we will create a variable called celebrities with the type LinkedList and assign it to LinkedList() with the “new” keyword. Do not worry if red squiggly lines appear below the names, that will resolve itself when we create the LinkedList class and its constructor.
Let’s also invoke the add method and pass in “Kanye West” as an argument.
Let’s begin creating our LinkedList class by following the steps that we used to create the Main class.
If you remember from the beginning of this tutorial, a LinkedList needs a head and a tail. Let’s add two properties named head and tail, both with type Node. We will create the Node later in this tutorial, do not import anything. Let’s also create a size property to track the amount nodes within our list. Give it the type int and assign it to zero.
Now let’s create the constructor for the LinkedList. Make sure the constructor has the same name as the class. Within the constructor block, we will assign null to both head and tail. It’s null because we have no nodes within the list so far. This will change when we add nodes.
Let’s include the code blocks for the methods that will be used in this tutorial.
Let’s start with the add() method. We are not expecting any in return, so we will use void as the return type. We are expecting an argument so we will add a parameter called var with the type String.
Both removeFirst() and removeLast() won’t return anything, and nor would it expect any arguments. For both, we will use void as their return types and leave the parenthesis empty.
Both getFirst() and getLast() return a node. So for the return type, we will utilize the Node type. These methods are also not expecting any type of arguments.
For the size method, we will return an integer and we are not expecting arguments. Let’s use the int as the return type.
So far we should have something like this…
Now we are going to move on to creating the Node class within the LinkedList class. Create a class called Node. We only need two properties in this class; value and next. In our use case, value is type String and next is type Node. Do not assign it to anything just yet.
Creating its constructor is similar to creating the constructor for the LinkedList. However, for this constructor, we are expecting a string argument, let’s add a val parameter with the type String within the parenthesis. Within the constructor code block, we will assign value to val. Then we will assign next to null.
Now that we have finished creating the Node class, let us move on to coding out the add method. The goal of this method is to add a node at the end of the list. We have to keep in mind that as we add a node we have to reassign the tail property to the new node. We also have to assign the head if there are no nodes in the list.
First, let’s create a variable called node with the type Node, we will assign this to the “new” Node(). Make sure you pass in val as the argument here. Since we are adding a node let’s add one to the size property. We should have something like this.
First, we will check if the head is null. If this is true, this means that the list is empty and we would need to assign the head to the node. Let’s add an if statement, in the condition we will check if the head is null, within the if statement block we will reassign the head to null. The tail is reassigned every time we add a node, we will handle this in a different manner. Let’s create an if statement and check if the tail is not null within the condition. If it’s not null we will then reassign the tail’s next property to the node. During this execution, you can think of the current tail as the previous node to the newest node. After the if statement, we will reassign the tail to the newest node. Now we should have this…
Now let’s move on to the removeFirst() method. The goal of this method is to remove the current head from the list. We have to keep in mind that we would need to reassign the head property to the next node. We also need to check if the head is the only one on the list and if the head is null. Keep in mind that the tail also points to the head if there is only one node in the list. Do not forget to subtract the size by one.
First, let’s add an edge case. Here we will check if the head is null, if so we will return immediately since there is nothing to modify. Then we add another if statement that verifies if head.next is equal to null. If this is true, we will reset both head and tail to null. Let’s return immediately since we won’t need to execute more code. Now, let's move on to the case where the list contains more than one node. Under the if statement, let’s reassign head to head.next. let’s also subtract the size property by one. This can be put after the edge case.
Let’s move on the removeLast(). This method differs from removeFirst() because we would need to iterate through the list so we can reassign the tail to the node before it. We also have to reassign the previous node’s next property to null. We can use the previous if statements from removeFirst since the behavior is similar.
Within the removeLast() code block, let’s copy the edge-cases from removeFirst, we should also include subtracting the size by one. Now let’s declare two variables with type Node and assign both of them to the head. We will call them prevNode and node. Next, let’s create a while loop which will run as long as the node is not null. Within the while loop’s brackets, we will add an if statement that verifies if node is not null. If it is true, then we will assign the tail to the prevNode and then assign tail.next to null. Let’s move outside of the if statement and assign prevNode to the current node, and then assign node to node.next. With this, we should be able to remove the last node and reassign the tail. It should look something like this.
Let’s add a contains method. The goal of this method is to verify if the value exists within the LinkedList. We are expecting a boolean to be returned, so we will use the boolean return type. An argument String var is also needed, so be sure to add that as a parameter. We will copy the loop and the variables from the removeLast() method. We will replace the while loop’s if statement condition to verify if the current node’s value is the same as the argument. We can use String.equals() for this and pass in the argument var as the argument. If it’s true we will return true. When the while loop expires we will return false shortly after.
Great! We have finished creating a LinkedList! Let’s check our work!
In the Main class, we already declared celebrities to be a new LinkedList, and we invoked the add method. Let’s check if “Kanye West” or another value of your choice is actually there. Use System.out.println() to check the value. In my example, the way I access the value is celebrities.head.value.
Here is the output:
Let’s add more to this list, you can add as much as your memory allows. I am going to repeat the add() method a couple more times so I can showcase the other methods. Then remove the tail a couple of times. Here are my short tests.
Here is my output.
As you can see, with the added methods, LinkedLists can be versatile. Here are the time complexities for each method.
- O(1) constant time complexity: add(), getFirst(), getLast(), and removeHead()
- O(n) linear time complexity: removeLast() and contains()
I hope this tutorial aided you in picturing LinkedLists more effectively and in understanding how to access its information. There are more methods to a LinkedList, this tutorial’s focus was only a few. What we built is a singly LinkedList, if you are up for the challenge create a doubly LinkedList.
Follow me if you want to see more!
