How to create Java LinkedList from scratch
This tutorial is intended to help understand better how Java LinkedList works. The best way to do it is by creating this data structure yourself. So in this tutorial, we will make our simple linked list.
What is a linked list?
The linked list is a data structure consisting of nodes. A node is the smallest unit of a linked list and it contains the value and the address (reference) to the next node. The linked list has 3 different types of nodes, a simple node mentioned before painted white in the picture below. The head node (green) is the special type of node it marks the beginning of the linked list. In other words, there are no nodes that point to this node. Last but, not least is the tail node (red). This node is the last in the linked list. The special thing about this node is that it doesn’t point to any other node, the address part of the node equals null.
When a linked list has only one node this node is a head and the tail at the same time, when a linked list has two nodes then the first node is a head and the second is a tail and it doesn’t have any simple node in between. Any given linked list can have at most one head and one tail and from zero to many simple nodes located between a head and a tail.
Defining the contract by interface
As a first step, we will define the interface (contract) for our custom linked list with the following methods.
package com.polovyi.ivan.tutorials;
public interface CustomLinkedList<E> {
int size();
void addFront(E value);
void addBack(E value);
E get(int index);
E getFirst();
E getLast();
void removeFirst();
void removeLast();
void removeValue(E value);
void clear();
}To guarantee the type safety we will use generics in our interface. In other words, our custom linked list will be able to store the elements of the type defined during its creation. Each method has a self-explanatory name and doesn’t need to be explained in the detail at this point. We will look closely at each method during implementation.
Interface (contract) implementation
Now we create a class CustomLinkedListImpl, that will implement the interface. But before the implementation we have to create a static inner class, that will represent a node. This class will have two variables — one for storing the value and another for storing the reference of another node.
package com.polovyi.ivan.tutorials;
public class CustomLinkedListImpl<E> implements CustomLinkedList<E> {
private static class Node<E> {
private E value;
private Node<E> next;
public Node(E value) {
this.value = value;
}
}
}Our linked list has to keep track of its size and has to know its head node. For this, we will add two variables and our class will look like the below:
package com.polovyi.ivan.tutorials;
public class CustomLinkedListImpl<E> {
private int size;
private Node<E> head;
private static class Node<E> {
private E value;
private Node<E> next;
public Node(E value) {
this.value = value;
}
}
}Size method
The most straightforward implementation is a size method implementation, we have to create a method that returns the size of the Linked list.
@Override
public int size() {
return this.size;
}Add front method
To add a new node as a head, we have to create a new node, point the next node reference to the head, and then switch the reference of the head variable from the previous head to a new head and last but not least increment the size of the linked list.
When the head of the linked list is equal to null, it means that there are no elements (nodes) in the LinkedList so we directly point the head to the new node. Now our class looks like below.
@Override
public void addFront(E value) {
Node<E> node = new Node(value);
if (this.head == null) {
this.head = node;
this.size++;
return;
}
node.next = this.head;
this.head = node;
this.size++;
}Add back method
To add the node to the back of the linked list first we have to create a new node, then we have to check if the head of the list equals null. If it is, it means that the list doesn’t have any elements, so the new node becomes the head of the list. In case when our list has a head already we have to find the tail of the list and point the tail to the new node. After this operation the previous tail node will point to the new node and the new node will point to nothing, hence will become the tail of the list. In the end, we have to increase the size of the list.
As I’ve mentioned before we have to find the tail in our list. Unlike the head, we don’t keep track of the tail of the list. So to find it we have to loop over it until the node point to the null. As you already know if the node points to nothing this node is the last in the list, hence it is a tail node.
@Override
public void addBack(E value) {
Node<E> node = new Node(value);
if (this.head == null) {
this.head = node;
this.size++;
return;
}
Node<E> currentNode = head;
while (currentNode.next != null) {
currentNode = currentNode.next;
}
currentNode.next = node;
this.size++;
}Remove first method
When we remove the element from the front of the list we remove the head of the list and make the next node a new head. As the last step, we decrease the size of the list.
If the list is empty we just return, it because there is nothing to remove.
@Override
public void removeFirst() {
if (this.size == 0) {
return;
}
Node<E> currentHead = this.head;
this.head = this.head.next;
currentHead.value = null;
currentHead.next = null;
this.size--;
}Remove last method
To remove the last element we have to find the element before the last one and turn it the tail. So for this, we loop over the list and when we find the needed element we point it to the null. A good practice is to remove the value from the previous tail, it will make it available for garbage collection. As the last step, we decrement the list size.
When the list is empty we simply return, it because it has nothing to remove.
@Override
public void removeLast() {
if (this.size == 0) {
return;
}
Node<E> currentNode = this.head;
while (currentNode.next != null) {
currentNode = currentNode.next;
if (currentNode.next.next == null) {
currentNode.next.value = null;
currentNode.next = null;
this.size--;
return;
}
}
}Clear method
When we need to remove all elements from the list we call the clear method. This method removes the head until the size of the list equals zero.
@Override
public void clear() {
while (this.size != 0) {
this.removeFirst();
}
}Get first method
If we need to obtain the first element from the list we call the get first method. This method is really simple it just returns the value from the head.
@Override
public E getFirst() {
return (E) this.head.value;
}Get last method
When we need to get the last value from the list we have to loop to the end of the list and return the value of a tail.
@Override
public E getLast() {
Node<E> currentNode = this.head;
while (currentNode.next != null) {
currentNode = currentNode.next;
if (currentNode.next == null) {
return (E) currentNode.value;
}
}
return null;
}Get method
It is possible to implement a method that returns the value from the node by its index. Unlike in an array or in an array list where each element has its index, the index in the context of the linked list is a sequential number of the node. When the list is empty or the index passed to the method is too large the method returns null. This is the simplest way to handle those kinds of situations. Of course, we could throw an exception, but I will keep it simple. If the index is zero then we return the value of the first node, which happens to be the head of a linked list.
If the index is not a zero the method will instantiate the variable which represents a current index, starting from zero. Then it will loop over the list incrementing the current index for each iteration and comparing it to the index received as a parameter. When a match is found it is returned from the method. The code is below:
@Override
public E get(int index) {
if (this.size == 0 || index > this.size - 1) {
return null;
}
if (index == 0) {
return (E) this.head.value;
}
int currentIndex = 0;
Node<E> currentNode = this.head;
while (currentNode.next != null) {
currentNode = currentNode.next;
if (++currentIndex == index) {
return (E) currentNode.value;
}
}
return null;
}Remove value method
When we need to remove a node by the value we use the remove value method. This method as a first step will check if the list is empty, if it is it will return and stop the execution. If the head value is equal to the received value it means that the head has to be removed and the next to the head node has to become a new had. If the value is not equal to the value in the head the method will loop over the list and compare the values of nodes to the received one. When the match is found it removes the node by pointing the previous one to the next one.
@Override
public void removeValue(E value) {
if (this.head == null) {
return;
}
if (this.head.value == value) {
this.head = this.head.next;
this.size--;
return;
}
Node<E> currentNode = this.head;
while (currentNode.next != null) {
if (currentNode.next.value == value) {
currentNode.next = currentNode.next.next;
this.size--;
return;
}
currentNode = currentNode.next;
}
}The entire class looks like below:
package com.polovyi.ivan.tutorials;
public class CustomLinkedListImpl<E> implements CustomLinkedList<E> {
private int size;
private Node<E> head;
@Override
public int size() {
return this.size;
}
@Override
public void addFront(E value) {
Node<E> node = new Node(value);
if (this.head == null) {
this.head = node;
this.size++;
return;
}
node.next = this.head;
this.head = node;
this.size++;
}
@Override
public void addBack(E value) {
Node<E> node = new Node(value);
if (this.head == null) {
this.head = node;
this.size++;
return;
}
Node<E> currentNode = this.head;
while (currentNode.next != null) {
currentNode = currentNode.next;
}
currentNode.next = node;
this.size++;
}
@Override
public void removeFirst() {
if (this.size == 0) {
return;
}
Node<E> currentHead = this.head;
this.head = this.head.next;
currentHead.value = null;
currentHead.next = null;
this.size--;
}
@Override
public void removeLast() {
if (this.size == 0) {
return;
}
Node<E> currentNode = this.head;
while (currentNode.next != null) {
currentNode = currentNode.next;
if (currentNode.next.next == null) {
currentNode.next.value = null;
currentNode.next = null;
this.size--;
return;
}
}
}
@Override
public void clear() {
while (this.size != 0) {
this.removeFirst();
}
}
@Override
public E getFirst() {
return (E) this.head.value;
}
@Override
public E getLast() {
Node<E> currentNode = this.head;
while (currentNode.next != null) {
currentNode = currentNode.next;
if (currentNode.next == null) {
return (E) currentNode.value;
}
}
return null;
}
@Override
public E get(int index) {
if (this.size == 0 || index > this.size - 1) {
return null;
}
if (index == 0) {
return (E) this.head.value;
}
int currentIndex = 0;
Node<E> currentNode = this.head;
while (currentNode.next != null) {
currentNode = currentNode.next;
if (++currentIndex == index) {
return (E) currentNode.value;
}
}
return null;
}
@Override
public void removeValue(E value) {
if (this.head == null) {
return;
}
if (this.head.value == value) {
this.head = this.head.next;
this.size--;
return;
}
Node<E> currentNode = this.head;
while (currentNode.next != null) {
if (currentNode.next.value == value) {
currentNode.next = currentNode.next.next;
this.size--;
return;
}
currentNode = currentNode.next;
}
}
private static class Node<E> {
private E value;
private Node<E> next;
public Node(E value) {
this.value = value;
}
}
}And the test class for all implemented methods:
package com.polovyi.ivan.tutorials;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertTrue;
public class CustomLinkedListTest {
@Test
public void shouldCreateEmptyLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
int size = customArrayList.size();
// then
assertEquals(0, size);
}
@Test
public void shouldAddOneElementToLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
customArrayList.addFront('A');
// then
assertEquals(1, customArrayList.size());
}
@Test
public void shouldAddElementToLinkedListAsHeadWhenIsNoElements() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
char a = 'A';
customArrayList.addFront(a);
// then
assertTrue(a == customArrayList.get(0));
assertEquals(1, customArrayList.size());
}
@Test
public void shouldAddElementToLinkedListAsHead() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
customArrayList.addFront('A');
customArrayList.addFront('B');
char c = 'C';
customArrayList.addFront(c);
// then
assertTrue(c == customArrayList.get(0));
assertEquals(3, customArrayList.size());
}
@Test
public void shouldAddElementToLinkedListAsHeadCallingAddBackWhenIsNoElements() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
char a = 'A';
customArrayList.addBack(a);
// then
assertTrue(a == customArrayList.get(0));
assertEquals(1, customArrayList.size());
}
@Test
public void shouldAddElementToLinkedListAsTailCallingAddBack() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
char c = 'C';
customArrayList.addFront('B');
customArrayList.addFront('A');
// when
customArrayList.addBack(c);
// then
assertTrue(c == customArrayList.get(2));
assertEquals(3, customArrayList.size());
}
@Test
public void shouldRemoveFirstElementFromLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addBack('A');
customArrayList.addBack('B');
customArrayList.addBack('C');
// when
customArrayList.removeFirst();
// then
assertTrue('B' == customArrayList.get(0));
assertEquals(2, customArrayList.size());
}
@Test
public void shouldDoNothingWhenRemoveFirstFromLinkedListCalledOnEmptyList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
customArrayList.removeFirst();
// then
assertEquals(0, customArrayList.size());
}
@Test
public void shouldRemoveFirstElementFromLinkedListWithOnlyOneElement() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addFront('A');
// when
customArrayList.removeFirst();
// then
assertEquals(0, customArrayList.size());
}
@Test
public void shouldRemoveLastElementFromLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addBack('A');
customArrayList.addBack('B');
customArrayList.addBack('C');
// when
customArrayList.removeLast();
// then
assertTrue('A' == customArrayList.get(0));
assertTrue('B' == customArrayList.get(1));
assertEquals(2, customArrayList.size());
}
@Test
public void shouldDoNothingWhenRemoveLastFromLinkedListCalledOnEmptyList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
customArrayList.removeLast();
// then
assertEquals(0, customArrayList.size());
}
@Test
public void shouldDoNothingWhenClearCalledOnEmptyLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
customArrayList.clear();
// then
assertEquals(0, customArrayList.size());
}
@Test
public void shouldClearLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addBack('A');
customArrayList.addBack('B');
customArrayList.addBack('C');
// when
customArrayList.clear();
// then
assertEquals(0, customArrayList.size());
}
@Test
public void shouldGetFirstElementFromLinked() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addFront('B');
Character firstElement = 'A';
customArrayList.addFront(firstElement);
// when
Character first = customArrayList.getFirst();
// then
assertTrue(firstElement.equals(first));
}
@Test
public void shouldGetLastElementFromLinked() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
Character lastElement = 'B';
customArrayList.addFront(lastElement);
customArrayList.addFront('A');
// when
Character last = customArrayList.getLast();
// then
assertTrue(lastElement.equals(last));
}
@Test
public void shouldReturnNullWhenGetMethodCalledOnEmptyLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
Character character = customArrayList.get(0);
// then
assertNull(character);
}
@Test
public void shouldReturnNullWhenGetMethodCalledWithIndexLargerThenLastOneLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addBack('A');
customArrayList.addBack('B');
customArrayList.addBack('C');
// when
Character character = customArrayList.get(customArrayList.size());
// then
assertNull(character);
}
@Test
public void shouldReturnTailWhenGetMethodCalledWithLastIndex() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addBack('A');
customArrayList.addBack('B');
customArrayList.addBack('C');
// when
Character character = customArrayList.get(customArrayList.size() - 1);
// then
assertTrue(character.equals('C'));
}
@Test
public void shouldReturnHeadWhenGetMethodCalledWithZeroIndex() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addBack('A');
customArrayList.addBack('B');
// when
Character character = customArrayList.get(0);
// then
assertTrue(character.equals('A'));
}
@Test
public void shouldRemoveValueFromHeadOfLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addBack('A');
customArrayList.addBack('B');
// when
customArrayList.removeValue('A');
// then
assertTrue(customArrayList.get(0).equals('B'));
assertEquals(1, customArrayList.size());
}
@Test
public void shouldRemoveValueFromLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
customArrayList.addBack('A');
customArrayList.addBack('B');
customArrayList.addBack('C');
customArrayList.addBack('D');
customArrayList.addBack('E');
customArrayList.addBack('F');
// when
customArrayList.removeValue('E');
// then
assertTrue(customArrayList.get(0).equals('A'));
assertTrue(customArrayList.get(4).equals('F'));
assertEquals(5, customArrayList.size());
}
@Test
public void shouldDoNothingWhenRemoveValueCalledOnEmptyLinkedList() {
// given
CustomLinkedListImpl<Character> customArrayList = new CustomLinkedListImpl<>();
// when
customArrayList.removeValue('A');
// then
assertEquals(0, customArrayList.size());
}
}The complete code can be found here:
Conclusion
In this tutorial, I've implemented the custom linked list. Consider it as a draft that can be improved. This implementation will help you to understand how a linked list works under the hood. You can try to implement it yourself. It doesn't have to be the same way, you can improve it and add more methods, figure out different algorithms for methods, etc.
Thank you for reading! Please like and follow. If you have any questions or suggestions, please feel free to write in the comments section or on my LinkedIn account.
Become a member for full access to Medium content.
