This blog covers all you need to know about Linked List in Java. We will explain how Linked List works and the different types of methods we can implement on Linked List in Java. Further, we will be discussing the advantages of Linked List in Java.
Table of Contents
Watch the video below to understand linked lists in data structures:
Overview of Linked List in Java
Linked List is a linear data structure in which we can store elements without continuous allocation of memory. We can implement Linked List in Java using a custom class, or we can use the collection framework present in java.util package. The Java Linked List class belongs to the Java Collections Framework. This Linked List class is an implementation of list and deque interfaces. It works at its core based on the doubly Linked List data structure. For storing elements using the Linked List class in Java, Insertion() method is used. Linked List in Java also supports duplicate elements.
One thing to keep in mind is that, in Linked List in Java, we cannot access any element randomly; we can access elements only in sequential order. To access any element in a Linked List, we can iterate the Linked List either from the start (head node) or the end (tail node), depending on which element we want to access.
As we know, Linked List is made up of nodes. A node is the fundamental unit of Linked List; linking them together will give the Linked List. There are two parts of a node: the first part stores the data, and the second part stores the address of the next node, as shown in the image below.
Based on memory allocation, a Linked List is of two types: single or normal and doubly Linked List.
- Singly or Normal Linked List in Java
It is a type of Linked List that is unidirectional, which means we can traverse it from the start node (head node) towards the last node (tail node). As you can see in the below image, it consists of a head node that only contains the address of the first node, and it has one tail node that is the last node of the Linked List, and in the pointer or address part, it stores ‘NULL.’ As shown in the image below, the nodes are linked together by storing the address of the next node. This way, multiple nodes are stored as objects in code and linked one after the other to form a Linked List.
Here is the basic syntax for declaring a Linked List in Java:
// creating Integer type linked list
LinkedList<Integer> linkedlist = new LinkedList<>();
// creating String type linked list
LinkedList<String> linkedlist = new LinkedList<>();
- Doubly Linked List in Java
As we can guess by its name, it contains the address of both the next and previous node. The node of a doubly Linked List has three parts: the first part contains the address of the previous node, the second part contains the data, and the third part contains the address of the next node. This way, we can traverse this type of Linked List from both directions.
As we can see in the above image, the “prev” part denotes the address of the previous node, and the “next” part denotes the address of the next node.
Here is the syntax for declaring a doubly Linked List in Java using a class:
//Creating a node of the doubly linked list
class node{
int value;
node previous;
node next;
public node(int value) {
this.value = value;
}
}
Interested in learning Java? Enroll in our Java Training now!
How to Create a Linked List in Java
The creation of Linked List in Java includes defining a ‘node’ class. Then, we will use the class ‘node’ to create a Linked List structure with nodes in the form of objects. Here, we have explained the steps to create Linked List in Java:
Step 1: Creating a ‘node’ Class
This node class represents a single element in Linked List, and it consists of two fields:
- data: This contains the actual value to be stored in the node.
- next: This contains the address of the next node.
class node {
int data;
node next;
public node(int data) {
this.data = data;
this.next = null;
}
}
Step 2: Creation of the First node
The head node is the starting point of Linked List. Here is the syntax to create a head node:
node head = new node(10);
Step 3: Creating and Connecting Nodes with Each Other
We connect nodes with each other with the help of the ‘next’ pointer, which stores the address of the next node.
node secondnode = new node(20);
head.next = secondnode;
node thirdnode = new node(30);
secondnode.next = thirdnode;
Step 4: Accessing nodes
To access each node inside Linked List, we need to traverse the entire list to the point where we get the element we want to access. We do this task with the help of any loop, as follows:
node currentnode = head;
while (currentnode != null) {
System.out.println(currentnode.data);
currentnode = currentnode.next;
}
Enroll in this Full Stack Developer Course and start your journey now!
Code for Linked List in Java
The following code for Linked List in Java denotes how we can declare nodes of singly Linked List along with adding new nodes at the end of Linked List, and then we will traverse each element of Linked List.
//node structure
class node {
int data;
node next;
};
class LinkedList {
node head;
LinkedList(){
head = null;
}
//Add new element at the end of the list
void push_back(int newElement) {
node newnode = new node();
newnode.data = newElement;
newnode.next = null;
if(head == null) {
head = newnode;
} else {
node temp = new node();
temp = head;
while(temp.next != null)
temp = temp.next;
temp.next = newnode;
}
}
//display the content of the list
void PrintList() {
node temp = new node();
temp = this.head;
if(temp != null) {
System.out.print("The list contains: ");
while(temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
} else {
System.out.println("The list is empty.");
}
}
};
With the help of the following code, we test if we have correctly coded Linked List in Java or not.
/ test the code
public class Implementation {
public static void main(String[] args) {
LinkedList MyList = new LinkedList();
//Add three elements at the end of the list.
MyList.push_back(10);
MyList.push_back(20);
MyList.push_back(30);
//traverse to display the content of the list.
MyList.PrintList();
}
}
Here is a program for creating a doubly Linked List in Java:
In the above code, to represent individual nodes of the doubly linked list, a ‘Node’ class is defined. The ‘Doubly Linked List’ class is created to perform operations like inserting nodes at the end and displaying the elements of the linked list. In the ‘main’ method, a doubly linked list is created, and elements (5, 10, and 15) are inserted at the end. Finally, this program will display the elements of the doubly linked list.
Want to ace your next Java interview? Check out our recent blog post about the most common Java interview questions and answers!
Operational Methods of Linked List in Java
Let’s explore the various operations performed on Linked List in Java. These are the most commonly used operations of Linked List in Java; one must be familiar with these operations to use Linked List in Java efficiently in the code.
Operation 1: Inserting Elements at the End
The following code will insert a node at the end of a Linked List in Java:
public void addAtEnd(node head, int newData) {
node newnode = new node(newData);
if (head == null) {
head = newnode;
return;
}
node currentnode = head;
while (currentnode.next != null) {
currentnode = currentnode.next;
}
currentnode.next = newnode;
}
Operation 2: Inserting Elements at the Beginning
The following code will insert a node at the start of Linked List in Java:
Operation 3: Inserting Elements at a Specific Position
The following code will insert a node at the user-specified position of Linked List in Java:
This output indicates that the user inserted the element 25 at position 2 in the existing linked list; thus, the modified Linked List will be 5 25 10 15.
Operation 4: Updating the Value of an Element
For updating a particular element, we need to traverse each element, starting from the head node, until we do not get the element we want to replace with the new element.
node head = new node(10);
node secondnode = new node(20);
head.next = secondnode;
node thirdnode = new node(30);
secondnode.next = thirdnode;
// Update the value of the second node
secondnode.data = 50;
// Print the updated linked list
node currentnode = head;
while (currentnode != null) {
System.out.println(currentnode.data);
currentnode = currentnode.next;
}
Operation 5: Deleting an Element at the Beginning
The following code will delete a node from the start of Linked List in Java:
Operation 6: Deleting Element at End
The following code will delete a node at the end of a Linked List in Java:
Operation 7: Deleting an Element at a Particular Index
The following code will delete the node at the particular index given by the user:
Constructors of Linked Lists in Java
Linked List class in Java provides constructors to create instances of a linked list. Here are the constructors available in the Linked List class:
- LinkedList(): Constructs an empty linked list
- LinkedList(Collection<? extends E> c): Constructs a linked list, containing the elements of the specified collection, in the order they are returned by the collection’s iterator
For example, to create an empty Linked List, the syntax will be as follows:
LinkedList<String> linkedList = new LinkedList<>();
To create a Linked List, from an existing collection, the syntax will be as follows:
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
LinkedList<Integer> linkedListFromCollection = new LinkedList<>(arrayList);
Read the Top 50 Data Structures Interview Questions to ace your next interview!
Advantages of Using Linked List in Java
When flexibility in size, efficient insertion and deletion operations, and dynamic memory allocation are required in the data structure, we use Linked List. The following advantages make Linked Lists a suitable choice in Java:
- Dynamic Size: Due to the dynamic structure of linked lists, it is easy to add or remove the data from the beginning, end, or any position within the list.
- Memory Allocation: In the linked list, each element (node) contains a reference to the next node, and because of this, we can efficiently use memory. The benefit of this is that it does not require contiguous memory allocation like an array.
- Implementation of Queue and Deque: With the help of Linked List, we can implement both Queue and Deque interfaces in Java. This enables adding elements to the end (enqueue) and removing elements from the beginning (dequeue), which are queue operations.
- Iterator and ListIterator: Linked List supports the use of both Iterator and ListIterator, which helps in efficient traversal and manipulation through the list that enables operations such as sequential access and removal.
Go through these most frequently asked Java Collection Interview Questions for 2024 that will prepare you for the job interviews.
Conclusion
The Linked List data structure in Java offers a dynamic and versatile solution for managing data. Its ability to efficiently handle insertion, deletion, and dynamic resizing makes it an invaluable choice in various programming languages. Because of its node-based structure, Linked Lists provides flexibility that helps in the easy implementation of queue and deque functions. Overall, it is a pool of various dynamic functions for developers to make their code more efficient.