This blog covers all you need to know about LinkedList in Java. We will explain how LinkedList works and the different types of methods we can implement on LinkedList in Java. Further, we will be discussing the advantages of LinkedList in Java.
Table of Contents
Watch the video below to understand linked lists in data structures:
Overview of LinkedList in Java
LinkedList is a linear data structure in which we can store elements without continuous allocation of memory. We can implement LinkedList in Java using a custom class, or we can use the collection framework present in java.util package. The Java LinkedList class belongs to the Java Collections Framework. This LinkedList class is an implementation of list and deque interfaces. It works at its core based on the doubly LinkedList data structure. For storing elements using the LinkedList class in Java, Insertion() method is used. LinkedList in Java also supports duplicate elements.
One thing to keep in mind is that, in LinkedList in Java, we cannot access any element randomly; we can access elements only in sequential order. To access any element in a LinkedList, we can iterate the LinkedList either from the start (head node) or the end (tail node), depending on which element we want to access.
As we know, LinkedList is made up of nodes. A node is the fundamental unit of LinkedList; linking them together will give the LinkedList. 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, LinkedList is of two types: singly or normal and doubly LinkedList.
- Singly or Normal LinkedList in Java
It is a type of LinkedList 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 LinkedList, 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 LinkedList.
Here is the basic syntax for declaring a LinkedList in Java:
// creating Integer type linkedlist
LinkedList<Integer> linkedlist = new LinkedList<>();
// creating String type linkedlist
LinkedList<String> linkedlist = new LinkedList<>();
- Doubly LinkedList 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 LinkedList 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 LinkedList 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 LinkedList 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 LinkedList in Java
The creation of LinkedList in Java includes defining a ‘node’ class. Then, we will use the class ‘node’ to create a LinkedList structure with nodes in the form of objects. Here, we have explained the steps to create LinkedList in Java:
Step 1: Creating a ‘node’ Class
This node class represents a single element in LinkedList, 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 LinkedList. 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 LinkedList, 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 LinkedList in Java
The following code for LinkedList in Java denotes how we can declare nodes of singly LinkedList along with adding new nodes at the end of LinkedList, and then we will traverse each element of LinkedList.
//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 LinkedList 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 LinkedList in Java:
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
Node head;
// Inserting a node at the end of the list
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.prev = temp;
}
}
// Display the elements of the linked list
public void display() {
Node current = head;
if (head == null) {
System.out.println("List is empty");
return;
}
System.out.println("Elements of the doubly linked list:");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertAtEnd(5);
dll.insertAtEnd(10);
dll.insertAtEnd(15);
dll.display();
}
}
In the above code, to represent individual nodes of the doubly linked list, a ‘Node’ class is defined. ‘DoublyLinkedList’ 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.
Operational Methods of LinkedList in Java
Let’s explore the various operations performed on LinkedList in Java. These are the most commonly used operations of LinkedList in Java; one must be familiar with these operations to use LinkedList 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 LinkedList 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 LinkedList in Java:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
// Method to insert at the beginning of the linked list
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
// Method to display the elements of the linked list
public void display() {
Node current = head;
if (head == null) {
System.out.println("List is empty");
return;
}
System.out.println("Elements of the linked list:");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
// Inserting elements at the beginning
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
// Displaying elements of the linked list
list.display();
}
}
Operation 3: Inserting Elements at a Specific Position
The following code will insert a node at the user-specified position of LinkedList in Java:
import java.util.Scanner;
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
// Inserting a node at the end of the list
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
// Display the elements of the linked list
public void display() {
Node current = head;
if (head == null) {
System.out.println("List is empty");
return;
}
System.out.println("Elements of the linked list:");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// Inserting a node at a specific position
public void insertAtPosition(int data, int position) {
Node newNode = new Node(data);
if (position == 0) {
newNode.next = head;
head = newNode;
} else {
Node current = head;
for (int i = 0; i < position - 1 && current != null; i++) {
current = current.next;
}
if (current == null) {
System.out.println("Position is out of range");
} else {
newNode.next = current.next;
current.next = newNode;
}
}
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
LinkedList list = new LinkedList();
// Existing linked list
list.insertAtEnd(5);
list.insertAtEnd(10);
list.insertAtEnd(15);
System.out.print("Enter element to insert: ");
int element = scanner.nextInt();
System.out.print("Enter position to insert: ");
int position = scanner.nextInt();
list.insertAtPosition(element, position);
list.display();
}
}
This output indicates that the user inserted the element 25 at position 2 in the existing linked list; thus, the modified LinkedList 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 LinkedList in Java:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
// Method to delete the first node in the linked list
public void deleteAtBeginning() {
if (head == null) {
System.out.println("List is empty. Nothing to delete.");
return;
}
Node temp = head;
head = head.next; // Move head to the next node
if (head != null) {
head.prev = null; // Update the new head's previous reference to null
}
System.out.println("Deleted element: " + temp.data);
}
// Method to display elements of the linked list
public void display() {
Node current = head;
if (head == null) {
System.out.println("List is empty");
return;
}
System.out.println("Elements of the linked list:");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.deleteAtBeginning(); // Deleting from an empty list
linkedList.head = new Node(5); // Adding elements
linkedList.head.next = new Node(10);
linkedList.head.next.next = new Node(15);
linkedList.display(); // Displaying elements before deletion
linkedList.deleteAtBeginning(); // Deleting the first element
linkedList.display(); // Displaying elements after deletion
}
}
Operation 6: Deleting Element at End
The following code will delete a node at the end of a LinkedList in Java:
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
Node head;
// ... (previous code for insertAtEnd and display methods)
// Deleting the last element from the list
public void deleteAtEnd() {
if (head == null || head.next == null) {
head = null;
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.prev.next = null;
}
}
public class Main {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.insertAtEnd(5);
dll.insertAtEnd(10);
dll.insertAtEnd(15);
System.out.println("Before deletion:");
dll.display();
dll.deleteAtEnd();
System.out.println("After deletion:");
dll.display();
}
}
Operation 7: Deleting an Element at a Particular Index
The following code will delete the node at the particular index given by the user:
public class DeleteElementLinkedList {
public static node deletenode(node head, int index) {
if (head == null || index < 0) {
return null;
}
if (index == 0) {
return head.next;
}
node prev = head;
node curr = head.next;
int count = 1;
while (curr != null && count < index) {
prev = curr;
curr = curr.next;
count++;
}
if (curr != null) {
prev.next = curr.next;
}
return head;
}
public static void main(String[] args) {
node head = new node(10);
head.next = new node(20);
head.next.next = new node(30);
head.next.next.next = new node(40);
System.out.println("Original Linked List:");
printLinkedList(head);
head = deletenode(head, 2);
System.out.println("\nLinked List after deleting at index 2:");
printLinkedList(head);
}
private static void printLinkedList(node head) {
node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
}
}
class node {
int data;
node next;
public node(int data) {
this.data = data;
this.next = null;
}
}
Constructors of LinkedList in Java
LinkedList class in Java provides constructors to create instances of a linked list. Here are the constructors available in the LinkedList 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 LinkedList, the syntax will be as follows:
LinkedList<String> linkedList = new LinkedList<>();
To create a LinkedList, 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 LinkedList in Java
When flexibility in size, efficient insertion and deletion operations, and dynamic memory allocation are required in the data structure, we use LinkedList. The following advantages make LinkedLists 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 LinkedList, 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: LinkedList 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 LinkedList 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, LinkedLists 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.
If you have any doubts or queries, do drop them on our Community Page!