The Linked List data structure with Java and other programming languages is a fundamental type that is highly performant for adding or removing elements.
A Linked List works differently than an array. An array is stored in memory in a contiguous way where it’s very easy and performant to find an element by index. A Linked List on the other hand is a chain of objects and each object holds a random place in memory (not contiguous). Therefore, it’s impossible to find an element by index in the Linked List.
Singly Linked List Structure
Since a Linked List behind the scenes is a chain of objects, we will have a variable value with the value of the current element, and another variable next to point to the next object reference.
Let’s see how that works in a diagram:
As you can see in the above diagram each element from the Linked List holds a reference to the next element. Notice also that it’s only possible to go forward. Therefore, if we start from the first element we can only go to the next object reference from the Linked List.
First of all, to have a Linked List we need the Node object that will hold a value and the next object reference. The Node class is as simple as the following:
// Node from Linked List, contains value and next object reference
public class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
next = null;
}
}
Now that we have the Node class, let’s use it to store elements into our Linked List. In the following code, we will store the first and last elements into the Linked List. Then we will have a constructor initializing the Linked List with the first and last element.
That’s the code structure we need to add, remove, search or change an element:
public class SinglyLinkedList {
// First element
Node head;
// Last element
Node tail;
// headValue will be the first and last element
// when the Linked List is created
SinglyLinkedList(int value) {
Node newNode = new Node(value);
head = newNode;
tail = newNode;
}
}
Add Elements to Linked List
Let’s now explore how to add a new node in the next object reference, also the showElements method to traverse nodes and show their values.
Finally, we have a main method instantiating the Linked List, adding nodes and showing its elements:
Adding elements to a Linked List is pretty fast, it has the time complexity of O(1). That’s because the new element just need to be chained with the last element of the Linked List. There is no need to copy elements to a new array object for example.
public class SinglyLinkedList {
// Omitted instance variables and constructor
// Add new node to the next reference
// Add new node to the tail (end) of the Linked List
void add(int value) {
Node nodeValue = new Node(value);
tail.next = nodeValue;
tail = nodeValue;
}
}
Code analysis:
In the code above we create a new node with the passed value, then we set this value to the next pointer from the tail.
Notice that the tail (last element) at this moment holds the same object reference from the head (first element). That’s the reason the objects will be chained correctly.
Then, we add the element to the tail object since this is the last object from the Linked List.
Add Element to Linked List Time Complexity
Notice in the code above that the add operation in a Linked List is pretty simple. Therefore, the time complexity will be O(1) since we only do a value assignment. There is no need to traverse the Linked List.
Delete First Element from Linked List
Deleting the first element from a Linked List is also an easy operation. To accomplish that we need to pass the next object reference to the head instance variable. By doing that, we will be erasing the first element from the chain and putting the second element that contains the other objects from the chain:
public class SinglyLinkedList {
// Omitted instance variables, constructor and methods...
void deleteFirst() {
head = head.next;
}
public static void main(String[] args) {
SinglyLinkedList linkedList = new SinglyLinkedList(1);
linkedList.add(2);
linkedList.deleteFirst();
linkedList.showElements();
}
}
Output:
2
Delete First Element Linked List Time Complexity
Deleting the first element from the Linked List is also an operation that doesn’t require a loop. We have direct access to the head element. Therefore, the time complexity is imediate O(1).
Search Element from Linked List
To search an element in the Linked List we need to traverse and then check the value equality. Let’s see how that works in code:
public class SinglyLinkedList {
// Omitted instance variables, constructor and methods...
Node searchElement(int value) {
var currentNode = head;
while (currentNode != null) {
if (currentNode.value == value) {
return currentNode;
}
currentNode = currentNode.next;
}
return null;
}
public static void main(String[] args) {
SinglyLinkedList linkedList = new SinglyLinkedList(1);
System.out.println("Found element: " + linkedList.searchElement(1).value);
}
}
Output:
Found element: 1
In the code above, notice that we are passing the int value, then we start the traversing from the head.
To traverse the chain of objects, we check if the currentNode is different than null and within that loop we assign the next element to the current node until the currentNode reference is null.
Search Element in Linked List Time Complexity
Since we traverse the Linked List to search for the element, the time complexity is O(n).
Inserting Element in the middle of a Linked List
To insert an element in the middle of a Linked List, it’s necessary to traverse objects and then connect the element to the chain of objects.
Let’s see how that works in code:
public class SinglyLinkedList {
// Omitted instance variables, constructor and methods...
void addAfter(int searchValue, int value) {
var currentNode = head;
while (currentNode != null) {
if (currentNode.value == searchValue) {
Node newNode = new Node(value);
var nextNode = currentNode.next;
currentNode.next = newNode;
newNode.next = nextNode;
}
currentNode = currentNode.next;
}
}
public static void main(String[] args) {
SinglyLinkedList linkedList = new SinglyLinkedList(1);
linkedList.add(3);
linkedList.addAfter(1, 2);
linkedList.addAfter(3, 4);
linkedList.showElements();
}
}
Output:
1
2
3
4
As you can see in the above code, we are adding one element after another in the Linked List. To do so we need to traverse the Linked List, find the element we want to add a value after, then insert the new value within the nextNode pointers.
It’s important to remember that if we assign a value to currentNode won’t make a difference in the object chain, because the next pointer will be still holding the object reference. That’s the key for this algorithm, it’s necessary to change the right object reference to impact the object chain.
Inserting Element in the middle of a Linked List Time Complexity
Since we need to traverse the chain of objects to insert an element in the middle, the time complexity is O(n).
Doubly Linked List
Simply put, the doubly linked list will have a reference for the previous and next nodes. In other words, the Node class will have the next and previous object references.
With that, it’s possible to go forward and backward on a doubly-linked list. Let’s see the following diagram to understand it better:
Now let’s see how to represent a doubly linked list in code with Java. Let’s first see the Node object with the previous and next object references:
public class Node {
int value;
Node next;
Node previous;
public Node(int value) {
this.value = value;
next = null;
previous = null;
}
}
Now let’s explore the Doubly Linked List itself. It’s similar to the Singly Linked List with the difference that now we can traverse forward and backwards:
public class DoublyLinkedList {
Node head = null;
Node tail = null;
public void addNode(int element) {
Node newNode = new Node(element);
if (head == null) {
head = newNode;
tail = newNode;
head.previous = null;
} else {
tail.next = newNode;
newNode.previous = tail;
tail = newNode;
}
newNode.next = null;
}
public void showNodes() {
Node currentNode = head;
if(head == null) {
return;
}
while(currentNode != null) {
System.out.println(currentNode.value);
currentNode = currentNode.next;
}
}
public static void main(String[] args) {
DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
doublyLinkedList.addNode(1);
doublyLinkedList.addNode(2);
doublyLinkedList.addNode(3);
doublyLinkedList.addNode(4);
doublyLinkedList.showNodes();
}
}
Output:
1
2
3
4
Circular Linked List
The Circular Linked List is similar to the other ones but it has the capability of going from the last node to the first node immediately. That happens because the tail will hold an object reference to the head of the Linked List.
Let’s see how that works in a diagram:
Pros from Linked List
A Linked List is better than an array in some aspects, let’s explore what are they:
- It’s faster to add elements at the beginning or the end of the list. It will always take O(1).
- Dynamic data size, there is no need to define the initial space as an array.
- Use the space as required since the nodes are allocated dynamically, this also means flexibility.
- Good to insert a great amount of data because when adding or removing elements there won’t be a buffer.
- Flexibility, a Linked List is used to handle data structures such as Queue, Stack, and graphs.
Cons from Linked List
- Random Access, It’s not possible to access elements by index.
- It uses more memory than an array. That’s because it’s necessary to create object references between nodes. This means that the we need to create the next object reference. For a Doubly Linked List it’s the next and previous pointers.
- Complexity, traversing in a Liked List is difficult. It’s necessary to use algorithms that require beyond trivial programming knowledge. It’s necessary to really master concepts such as pointers and object references.
- Traversing back to back requires more memory usage since the next and previous pointers will have to be pointing to objects.
Summary
The Linked List data structure is vital to be understood by a software engineer since it’s vastly used in applications and coding interviews, of course! With a Linked List we can easily organize and change directories names or move songs from a player wherever we want since data is not contiguous as an array. Therefore, it’s easier to move data around or change data in the middle.
Let’s recap the highlights of this article:
- Singly Linked List has only the next pointer. Meaning that it’s possible to only traverse forward.
- Doubly Linked List has both the next and previous pointers. Meaning that we can traverse forward and backward.
- Circular Singly Linked List has only the next pointer. But the tail (last element) has the reference from the head (first element).
- Circular Doubly Linked List has the next and previous pointers. But the tail also includes the object reference from the head (first element).
- A Node will have the next pointer for Singly Linked List or next and previous for Doubly Linked List.
- The Linked List will have the tail and the head pointers.
- Linked List can’t access elements by index because data is stored dynamically, not contiguously as an array
- Linked List is better to handle a large amount of data since it’s dynamic.
- Linked List is flexible, therefore, great to handle stack, queue, and graphs.
- Linked List will always have the time complexity of O(1) to add or delete elements.
