LinkedList in Java

In Java programming and software development, choosing the correct data structure can majorly impact the performance and efficiency of any program or application. The LinkedList in Java is a very useful data structure that generally allows efficient insertions and deletions, which makes it ideal for memory management, real-time Java applications, and undo operations in different text editors.

With this Java LinkedList tutorial, you are going to learn types of LinkedList, operations, working, methods, and many more. Whether you are just getting started with Java Data Structures or you are a proficient Java programmer, this tutorial on Java LinkedLists will help you gain the required knowledge to implement and use these linked lists effectively in your Java Coding Problems.

Table of Contents:

What is a LinkedList in Java?

A LinkedList in Java is generally a linear data structure that is used to store a collection of elements where each element which is called a node is linked to the next element using a pointer. This dynamic data structure is very useful in various operations like insertion, deletion, and traversal of elements making it very important in programming and software development.

Core Concept of LinkedLists

Imagine a train where each compartment (node) is connected to the next one through a coupling (pointer/reference). This is similar to how a linked list works:

Each node stores data (like passengers in a train compartment).
Each node also has a pointer that connects it to the next node (like the coupling between compartments).
The last node points to null, indicating the end of the list.

Unlike arrays, which use indexes for direct access, a linked list requires traversal from the first node to reach a specific element.

Key Differences Between LinkedLists and Array

Feature	Array	LinkedList
Storage Type	Contiguous memory allocation	Non-contiguous (scattered in memory)
Size Flexibility	Fixed-size (declared initially)	Dynamic size (grows/shrinks as needed)
Insertion/Deletion	Slow (requires shifting elements)	Fast (only pointers are updated)
Memory Usage	Efficient (no extra space needed)	Uses extra memory for pointers
Access Time	Fast (random access via index)	Slow (sequential access)

Advantages of LinkedList Over Array

Dynamic Size: In the LinkedList, you don’t need to define the size at the time of creation as it can grow or shrink based on the requirement.
Efficient Insertions and Deletions: The addition or removal of elements in Java LinkedList does not require to shift of the other elements.
Better Memory Utilization: It only uses the memory required for the current elements.

Working of LinkedList in Java

Now that you’ve seen the various kinds of LinkedLists there are in Java, let us understand how it actually works internally. A LinkedList operates differently from an array, as it generally offers dynamic allocation of memory, efficient insertion and deletion, and adaptive data handling.

1. How LinkedList Stores Data

A LinkedList in Java is normally defined by the number of nodes, whereby each node has two elements:

Data that contains the actual value.
Pointer (Reference) that simply Stores the memory address of the next node.

2. Memory Allocation in LinkedList

Unlike arrays, which generally have contiguous memory allocation, a LinkedList typically uses non-contiguous memory allocation which means that nodes are simply scattered across memory but are linked together through references.

3. How Memory is Allocated in a LinkedList?

When a new node is created, Java dynamically allocates memory for it.
Each node of the LinkedList generally stores the memory address(reference) of the next node, unlike the arrays where it is stored in a continuous memory block.
Garbage Collector in Java automatically deallocates memory for the unused nodes and prevents memory leaks.

4. Comparison of Memory Representation between LinkedList vs Array

Feature	LinkedList	Array
Memory Allocation	Dynamic, non-contiguous	Static, contiguous
Insertion/Deletion	Fast (O(1) at the beginning)	Slow (O(n) shifting required)
Access Time	Sequential (O(n))	Random Access (O(1))
Memory Usage	Requires extra memory for pointers	Uses only data storage

5. Example: Dynamic Memory Allocation in a LinkedList

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null; // Initially, the node points to NULL
    }
}
public class LinkedListMemoryDemo {
    public static void main(String[] args) {
        Node head = new Node(10); // Allocates memory dynamically
        head.next = new Node(20); // Creates another node and links it
        head.next.next = new Node(30); // Continues the linking process
        Node temp = head;
        while (temp != null) {
            System.out.println("Data: " + temp.data + ", Address: " + temp);
            temp = temp.next;
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output Example (Addresses will vary after every execution):

This output shows that nodes in the LinkedList are stored at different memory locations but are connected through references.

How to Create a Custom LinkedList in Java

While Java generally provides the built-in LinkedList class in its Java Collections Framework (JCF), creating a custom implementation of LinkedList simply helps in understanding how LinkedLists manage data, memory, and pointers.

1. Creating the Node Class

Let’s define a Node class for creating a custom linked list to represent each node in our Singly LinkedList.

Java

1
2
3
4
5
6
7
8
9
10
11
12
// Node class representing a single element in the LinkedList
class Node {
    int data;  // Stores the value of the node
    Node next; // Stores the reference to the next node
    // Constructor to initialize the node with a value
    public Node(int data) {
        this.data = data;
        this.next = null; // Initially, the next reference is set to null
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

2. Creating a Custom LinkedList Class

Now, we need a class that can manage the list. The class must have:

A reference back to the head node (list starting node).
Methods to add elements to the list.
A method to iterate over and display the list.

Let’s define the CustomLinkedList class:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// Node class representing a single element in the LinkedList
class Node {
    int data;  // Stores the value of the node
    Node next; // Stores the reference to the next node
    // Constructor to initialize the node with a value
    public Node(int data) {
        this.data = data;
        this.next = null; // Initially, the next reference is set to null
    }
}
// Custom implementation of a Singly LinkedList
class CustomLinkedList {
    Node head; // Head node of the list
    // Method to add a new node at the end of the list
    public void add(int data) {
        Node newNode = new Node(data); // Create a new node
        // If the list is empty, set the new node as the head
        if (head == null) {
            head = newNode;
            return;
        }
        // Traverse to the last node
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        // Link the last node to the new node
        temp.next = newNode;
    }
    // Method to display the LinkedList elements
    public void display() {
        Node temp = head;
        
        // If the list is empty
        if (temp == null) {
            System.out.println("LinkedList is empty.");
            return;
        }
        // Traverse and print each node
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }
}
// Main class to test the LinkedList implementation
public class LinkedListDemo {
    public static void main(String[] args) {
        CustomLinkedList list = new CustomLinkedList();
        // Adding elements to the linked list
        list.add(10);
        list.add(20);
        list.add(30);
        list.add(40);
        // Displaying the linked list
        list.display();
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

3. Explanation of Code

The Node class in it generally defines the individual elements of the LinkedList.
The class names as CustomLinkedList typically manage the list with its internal head pointer.
To insert the new node at the end, the add() method is being used.
To print the whole custom linked list and display it on the screen, the display() method is used.
The main method (LinkedListDemo) creates a list, adds elements, and prints the list.

Types of LinkedLists in Java

Now that you have learned the basic concepts about the LinkedList and its advantages, let’s learn its different types in Java. There are three types of LinkedLists in Java:

1. Singly LinkedList in Java

A Singly LinkedList is the simplest form of a linked list where:

Each node contains data, as well as a pointer to the next node.
The last node of the singly linked list points to NULL, which simply indicates the end of the Java Singly LinkedList.
The starting Node is generally called as head and the last node is called as Tail.

1.1 Structure of a Singly LinkedList

Here, each node simply stores a value and a reference to the next node in the sequence.

1.2 When to Use a Singly LinkedList?

You can use the Singly LinkedList whenever you want to create a simple and lightweight linked list.
You can use it whenever operations like insertions and deletion at the starting are frequent.
You can also use Singly LinkedList when memory optimization is a top priority (since it stores only one pointer per node).

1.3 Implementing a Singly LinkedList in Java

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
public class SinglyLinkedList {
    Node head;
    // Insert a new node at the end
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
    // Display the linked list
    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + "-> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.add(10);
        list.add(20);
        list.add(30);
        list.display();
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

2. Doubly LinkedList in Java

Each node in DLL typically contains data, a pointer to the next node, and a pointer to the previous node. Also, note that the previous pointer of the first node and the next pointer of the last node are NULL in DLL.

2.1 Structure of a Doubly LinkedList

Here, every node has basically two pointers, one is pointing to the next node, and another pointing to its previous one.

2.2 When to Use a Doubly LinkedList?

Doubly LinkedList in Java is majorly used in the case of bidirectional traversals.
You can use DLL when you frequently insert or delete elements from both ends.
You can also use DLL when the ability to move backward through the list is useful.

2.3 Implementing a Doubly LinkedList in Java

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class DoublyNode {
    int data;
    DoublyNode next;
    DoublyNode prev;
    public DoublyNode(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}
public class DoublyLinkedList {
    DoublyNode head;
    // Insert at the end
    public void add(int data) {
        DoublyNode newNode = new DoublyNode(data);
        if (head == null) {
            head = newNode;
            return;
        }
        DoublyNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.prev = temp;
    }
    // Display the linked list forward
    public void display() {
        DoublyNode temp = head;
        while (temp != null) {
            System.out.print(temp.data + "<-> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.add(10);
        list.add(20);
        list.add(30);
        list.display();
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

3. Circular LinkedList in Java

A Circular LinkedList (CLL) in Java is a variation of a normal linked list in which the last node simply points back to the first node, which generally forms a circular structure.

In the case of a Singly Circular LinkedList, the next pointer of the last node generally points to the first node.
In a Doubly Circular LinkedList, both the first and last nodes are connected in both directions.

3.1 Structure of a Singly Circular LinkedList

3.2 Structure of a Doubly Circular LinkedList

3.3 When to Use a Circular LinkedList?

When you are dealing with circular buffer implementations such as CPU scheduling, and network buffering.
‘When you need to continuously rotate through the elements such as multiplayer games, and streaming applications.

3.4 Implementing a Circular LinkedList in Java

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class CircularNode {
    int data;
    CircularNode next;
    public CircularNode(int data) {
        this.data = data;
        this.next = null;
    }
}
public class CircularLinkedList {
    CircularNode head, tail;
    // Insert a new node
    public void add(int data) {
        CircularNode newNode = new CircularNode(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            tail.next = head; // Circular reference
            return;
        }
        tail.next = newNode;
        tail = newNode;
        tail.next = head; // Maintain circular link
    }
    // Display the circular linked list
    public void display() {
        if (head == null) return;
        CircularNode temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("(Back to Head)");
    }
    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        list.add(10);
        list.add(20);
        list.add(30);
        list.display();
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

LinkedList Operations in Java

LinkedList operations are very important for managing dynamic data structures efficiently and in this section, you are going to learn some operations you can perform on LinkedLists.

1. Inserting Elements in Java LinkedList

A linked list in Java stores every element as nodes and is connected with each other by pointer references. Here, we have explained every step to insert the elements in the Java LinkedList. You just have to go through all the comments for a deeper understanding.

For every operation, we have written the core methods to perform the specific operations. If you want to test these operations by running them yourself, we have written the runnable code performing all the operations at the end of this section

1.1 How to Insert an Element at the beginning of a LinkedList in Java?

For inserting the elements or nodes in a linked list in Java, you just need to follow these steps:

Create a new node with your data
Point the new node you want to insert in LinkedList to the current head
And Update the head to point it to the new node which will simply make it the first element.

Example:

Java

1
2
3
4
5
6
7
8
// Insert at the beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

1.2 How to Insert an Element at the End of a LinkedList in Java?

Now, let’s insert the node(element) at the tail or end of the linked list:

First, create the new node using the given data.
Then traverse the linked list all to the last node whose next is null
And then make that next null to that new node you want to insert.

Example:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Insert at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

1.3 How to Insert an Element at a Specific Position of LinkedList in Java?

To insert the node(element) at any specific position of the linked list:

First, create the new node using the given data.
Traverse the linked list to find the node before you want to insert the new node.
Update the reference of the index-1 node to the new node

Example:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Insert at a specific position
    public void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 0) {
            newNode.next = head;
            head = newNode;
            return;
        }
        Node current = head;
        for (int i = 0; current != null && i < position - 1; i++) {
            current = current.next;
        }
        if (current == null) return;
        newNode.next = current.next;
        current.next = newNode;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

2. How to Update the Value of an Element in a LinkedList?

To update the value of the node, you need to traverse the list until we find the node at a specific position and replace it with the new reference.

Example:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Update a node's value at a specific position
    public void updateNode(int position, int newData) {
        Node current = head;
        int currentPosition = 0;
        while (current != null) {
            if (currentPosition == position) {
                current.data = newData;
                return;
            }
            current = current.next;
            currentPosition++;
        }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

3. Deleting Elements of LinkedList

Deleting any element from the LinkedList means changing or updating the references of the adjacent nodes simply removes the reference from the particular node that you to delete.

1. Deleting the First Node

Removing the first node or head node from the LinkedList simply means shifting the head to the next node in the list.

Example:

Java

1
2
3
4
5
6
// Delete the first node in the LinkedList
public void deleteFirst() {
    if (head == null) return; // If list is empty, do nothing
    head = head.next; // Move head to the next node
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

4. Deleting the Last Node

In order to delete the last node of the LinkedList you just need to traverse to the second last of the list and just update its next pointer to null.

Example:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Delete the last node in the LinkedList
public void deleteLast() {
    if (head == null) return; // If list is empty, do nothing
    if (head.next == null) { // If only one node exists
        head = null;
        return;
    }
    Node temp = head;
    while (temp.next.next != null) { // Traverse to second last node
        temp = temp.next;
    }
    temp.next = null; // Remove reference to last node
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

5. Deleting a Node at a Specific Position

For deleting the node of random or any specific position of a given index, you need to traverse the node just one index position before the given index and update its pointer

Example:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Delete a node at a given position
public void deleteAtPosition(int position) {
    if (head == null) return; // If list is empty, do nothing
    if (position == 0) { // If deleting the first node
        head = head.next;
        return;
    }
    Node temp = head;
    for (int i = 0; temp != null && i < position - 1; i++) {
        temp = temp.next;
    }
    if (temp == null || temp.next == null) {
        System.out.println("Invalid position");
        return;
    }
    temp.next = temp.next.next; // Remove the node
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Here we have included all the operations to perform on the LinkedList. Try running the code, and modify it according to your needs in order to learn these operations better.

Example:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// Node class representing each node in the linked list
class Node {
    int data;
    Node next;
    // Constructor to create a new node
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}
// LinkedList class containing all operations
class LinkedList {
    private Node head; // Head of the list
    // Insert at the beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
    // Insert at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }
    // Insert at a specific position
    public void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 0) {
            newNode.next = head;
            head = newNode;
            return;
        }
        Node current = head;
        for (int i = 0; current != null && i < position - 1; i++) {
            current = current.next;
        }
        if (current == null) return;
        newNode.next = current.next;
        current.next = newNode;
    }
    // Update a node's value at a specific position
    public void updateNode(int position, int newData) {
        Node current = head;
        int currentPosition = 0;
        while (current != null) {
            if (currentPosition == position) {
                current.data = newData;
                return;
            }
            current = current.next;
            currentPosition++;
        }
    }
    // Delete the first node
    public void deleteFirst() {
        if (head == null) return;
        head = head.next;
    }
    // Delete the last node
    public void deleteLast() {
        if (head == null || head.next == null) {
            head = null;
            return;
        }
        Node current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        current.next = null;
    }
    // Delete a node at a specific position
    public void deleteAtPosition(int position) {
        if (head == null) return;
        if (position == 0) {
            head = head.next;
            return;
        }
        Node current = head;
        for (int i = 0; current != null && i < position - 1; i++) {
            current = current.next;
        }
        if (current == null || current.next == null) return;
        current.next = current.next.next;
    }
    // Print the linked list
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}
// Main class to test all LinkedList operations
public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // Insert operations
        list.insertAtBeginning(3);
        list.insertAtBeginning(2);
        list.insertAtBeginning(1);
        list.insertAtEnd(4);
        list.insertAtPosition(5, 2);
        System.out.println("LinkedList after insertions:");
        list.printList(); // Output: 1 -> 2 -> 5 -> 3 -> 4 -> null
        // Update operation
        list.updateNode(2, 10);
        System.out.println("After updating position 2:");
        list.printList(); // Output: 1 -> 2 -> 10 -> 3 -> 4 -> null
        // Delete operations
        list.deleteFirst();
        System.out.println("After deleting first node:");
        list.printList(); // Output: 2 -> 10 -> 3 -> 4 -> null
        list.deleteLast();
        System.out.println("After deleting last node:");
        list.printList(); // Output: 2 -> 10 -> 3 -> null
        list.deleteAtPosition(1);
        System.out.println("After deleting node at position 1:");
        list.printList(); // Output: 2 -> 3 -> null
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

Advanced Operations on LinkedList

Now you have seen some of the basic operations like insertion and deletion in the LinkedList, we also need to perform complex operations and solve difficult problems like reversing, merging, and sorting LinkedLists.

1. How to Reverse a LinkedList in Java

Reversing a Singly LinkedList generally means changing the directions of the pointers due to which the last node will become a new head. Below we have written the program to do so.

Example:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Class representing a Node in the LinkedList
class Node {
    int data;
    Node next;
    // Constructor to initialize a new node
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
// LinkedList class
class LinkedList {
    Node head;
    // Add a new node at the end of the LinkedList
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
    // Reverse the LinkedList
    public void reverse() {
        Node prev = null, current = head, next;
        while (current != null) {
            next = current.next; // Store next node
            current.next = prev; // Reverse the link
            prev = current;
            current = next;
        }
        head = prev; // Update head to the last node
    }
    // Display the LinkedList
    public void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}
// Main class to test the reverse method
public class ReverseLinkedList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println("Original List:");
        list.display();
        list.reverse();
        System.out.println("Reversed List:");
        list.display();
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

2. How to Merge the Two LinkedLists in Java

When you want to merge the two linked lists into one single linked list you need to compare the heads of both linked lists and then recursively call it on the remaining nodes.

Example:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// Class representing a Node in the LinkedList
class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
// LinkedList class
class LinkedList {
    Node head;
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
    // Merge two sorted LinkedLists
    public static Node mergeLists(Node l1, Node l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.data < l2.data) {
            l1.next = mergeLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeLists(l1, l2.next);
            return l2;
        }
    }
    // Display the LinkedList
    public void display(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}
// Main class to test the merge method
public class MergeSortedLinkedLists {
    public static void main(String[] args) {
        LinkedList list1 = new LinkedList();
        list1.add(1);
        list1.add(3);
        list1.add(5);
        LinkedList list2 = new LinkedList();
        list2.add(2);
        list2.add(4);
        list2.add(6);
        System.out.println("First Sorted List:");
        list1.display(list1.head);
        System.out.println("Second Sorted List:");
        list2.display(list2.head);
        Node mergedHead = LinkedList.mergeLists(list1.head, list2.head);
        System.out.println("Merged Sorted List:");
        list1.display(mergedHead);
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

3. How to Sort a LinkedList using Merge Sort in Java

Sorting the LinkedList using the Merge sort algorithm is one of the most efficient approaches to follow. You just need to find the middle of the Linked list using fast and slow pointer and write the sorting approach.

Example:

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Class representing a Node in the LinkedList
class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
// LinkedList class
class LinkedList {
    Node head;
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }
    // Get the middle node of the LinkedList (Used for Merge Sort)
    private Node getMiddle(Node head) {
        if (head == null) return head;
        Node slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    // Merge two sorted LinkedLists
    private Node mergeLists(Node l1, Node l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.data < l2.data) {
            l1.next = mergeLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeLists(l1, l2.next);
            return l2;
        }
    }
    // Merge Sort for LinkedList
    public Node mergeSort(Node head) {
        if (head == null || head.next == null) return head;
        Node middle = getMiddle(head);
        Node nextToMiddle = middle.next;
        middle.next = null; // Split the list into two halves
        Node left = mergeSort(head);
        Node right = mergeSort(nextToMiddle);
        return mergeLists(left, right);
    }
    // Display the LinkedList
    public void display(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}
// Main class to test the merge sort method
public class SortLinkedList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(4);
        list.add(2);
        list.add(1);
        list.add(3);
        System.out.println("Unsorted List:");
        list.display(list.head);
        list.head = list.mergeSort(list.head);
        System.out.println("Sorted List:");
        list.display(list.head);
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

How to Iterate Over a LinkedList in Java

Iteration is perhaps the most common operation that is performed on a LinkedList. Because LinkedLists have no array-based direct indices to access, traversing through the list requires iteration from the front of the list to the end of the list or terminal node.

1. Using a While Loop

The simplest and most widely used way to traverse through a Singly LinkedList is by using a loop called a ‘while loop’.

Example: Iterating with a while loop

Java

1
2
3
4
5
6
7
8
9
10
11
// Method to iterate and print the LinkedList using a while loop
public void iterateUsingWhileLoop() {
    Node temp = head;
    while (temp != null) { // Traverse until the end
        System.out.print(temp.data + " -> ");
        temp = temp.next;
    }
    System.out.println("NULL");
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

How Does It Work?

Start from the head node.
Print the data of the current node.
Move to the next node and repeat until reaching NULL.

2. Using a For Loop

A for loop might even be used for iteration while initializing the loop with the head of the linked list.

Example: Iterating with a for loop

Java

1
2
3
4
5
6
7
8
// Method to iterate using a for loop
public void iterateUsingForLoop() {
    for (Node temp = head; temp != null; temp = temp.next) {
        System.out.print(temp.data + " -> ");
    }
    System.out.println("NULL");
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Key Difference from While Loop

The initialization, testing for condition, and update all occur in a single statement.
Works similarly to a while loop but results in more readable code.

3. Using an Iterator

Java’s Iterator interface allows for iteration of Java’s LinkedList in a fail-safe manner so that ConcurrentModificationException is not incurred.

Example: Iterating using an Iterator (Only for Java's Built-in LinkedList)

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Iterator;
import java.util.LinkedList;
public class IteratorExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(10);
        list.add(20);
        list.add(30);
        list.add(40);
        // Using Iterator to traverse the LinkedList
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " -> ");
        }
        System.out.println("NULL");
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Why Use an Iterator?

Prevents ConcurrentModificationException while iteratively changing.
Works on Java's own LinkedList implementation, not on some other implementation.

4. Using a ListIterator (For Doubly LinkedLists)

A ListIterator provides bi-directional iteration for Doubly LinkedLists.

Example: Using ListIterator to Traverse Forward & Backward

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.ListIterator;
import java.util.LinkedList;
public class ListIteratorExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(10);
        list.add(20);
        list.add(30);
        list.add(40);
        // Creating ListIterator for forward iteration
        ListIterator<Integer> listIterator = list.listIterator();
        System.out.print("Forward Traversal: ");
        while (listIterator.hasNext()) {
            System.out.print(listIterator.next() + "-> ");
        }
        System.out.println("NULL");
        // Backward Traversal
        System.out.print("Backward Traversal: ");
        while (listIterator.hasPrevious()) {
            System.out.print(listIterator.previous() + "-> ");
        }
        System.out.println("NULL");
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

Key Features of ListIterator:

Can traverse in both directions
Allows element modification in iteration.
Works only on Java LinkedList implementation (no custom lists).

5. Using Java Streams (Java 8 and Later)

Java Streams API provides a modern approach to iterating over a LinkedList with functional programming.

Example: Iterating using Java Streams

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.LinkedList;
public class StreamExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(10);
        list.add(20);
        list.add(30);
        list.add(40);
        // Using Java Streams to iterate and print the LinkedList
        list.stream().forEach(data -> System.out.print(data + "-> "));
        System.out.println("NULL");
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

Methods of LinkedList in Java

Java provides us with an in-built LinkedList in java.util package that has several useful methods to insert, delete, modify, and retrieve elements. All these methods make operations on LinkedList more efficient and easy to implement in real-life situations like caching, graph algorithms, and memory allocation.

Method	Description
add(E e)	Adds an element to the end of the LinkedList.
add(int index, E element)	Inserts an element at a specific position.
addFirst(E e)	Adds an element at the beginning.
addLast(E e)	Adds an element at the end.
get(int index)	Returns the element at the given index.
getFirst()	Retrieves the first element.
getLast()	Retrieves the last element.
remove(int index)	Removes the element at the specified index.
remove(Object o)	Removes the first occurrence of the specified element.
removeFirst()	Removes the first element.
removeLast()	Removes the last element.
contains(Object o)	Checks if the LinkedList contains the specified element.
size()	Returns the total number of elements in the LinkedList.
clear()	Removes all elements from the LinkedList.
isEmpty()	Checks if the LinkedList is empty.
set(int index, E element)	Replaces an element at the given index.
indexOf(Object o)	Returns the index of the first occurrence of the element.
lastIndexOf(Object o)	Returns the index of the last occurrence of the element.
toArray()	Converts the LinkedList into an array.
iterator()	Returns an iterator for the LinkedList.
listIterator()	Returns a ListIterator for bidirectional traversal.
descendingIterator()	Returns an iterator to traverse in reverse order.
clone()	Creates a shallow copy of the LinkedList.

These LinkedList methods of Java generally simplify the LinkedList operations and are very important for efficient data structure manipulation in Java.

Constructors of LinkedLists in Java

In Java, the linked lists class typically contains many constructors that help the Java Developers create different variations of the LinkedLists.

1. LinkedList() – Default Constructor

The default constructor in Java helps to construct the empty LinkedList with zero elements. Elements can be added to it by methods like add(), addFirst(), and addLast().

Example: Using LinkedList() Constructor

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.LinkedList;
public class LinkedListConstructorExample {
    public static void main(String[] args) {
        // Creating an empty LinkedList
        LinkedList<String> list = new LinkedList<>();
        // Adding elements to the list
        list.add("Java");
        list.add("Python");
        list.add("C++");
        // Displaying the LinkedList
        System.out.println("LinkedList: " + list);
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

2. LinkedList(Collection c) – Copy Constructor

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.ArrayList;
import java.util.LinkedList;
public class LinkedListFromCollection {
    public static void main(String[] args) {
        // Creating an ArrayList with initial elements
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("Java");
        arrayList.add("Linked");
        arrayList.add("List");
        // Creating a LinkedList using the ArrayList
        LinkedList<String> linkedList = new LinkedList<>(arrayList);
        // Displaying the LinkedList
        System.out.println("LinkedList initialized from ArrayList: " + linkedList);
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

Learning these constructors will help you to effectively create the linked lists depending upon the requirements of the program.

Serialization of LinkedList in Java

Serialization is the concept in Java that generally converts an object to a byte stream in order to save it to a file, transfer it across a network, or simply store it in a database. Let's learn how you can serialize a LinkedList in Java

1. How to Serialize a LinkedList in Java

Ensure the class is serializable (Java LinkedList is implemented by default).
Use ObjectOutputStream to write the object to a file.
Use ObjectInputStream to read the object from the file.

Example: Serializing and Deserializing a LinkedList

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.io.*;
import java.util.LinkedList;
public class LinkedListSerialization {
    public static void main(String[] args) {
        // Step 1: Create a LinkedList and add elements
        LinkedList<String> list = new LinkedList<>();
        list.add("Java");
        list.add("Python");
        list.add("C++");
        // File where the object will be saved
        String filename = "linkedlist.ser";
        // Step 2: Serialize the LinkedList
        try (ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream(filename))) {
            out.writeObject(list);
            System.out.println("LinkedList serialized successfully.");
        } catch (IOException e) {
            e.printStackTrace();
        }
        // Step 3: Deserialize the LinkedList
        LinkedList<String> deserializedList = null;
        try (ObjectInputStream in = new ObjectInputStream(new FileInputStream(filename))) {
            deserializedList = (LinkedList<String>) in.readObject();
            System.out.println("Deserialized LinkedList: " + deserializedList);
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

LinkedList Queue and Dequeue in Java

A queue is a data structure in Java that generally follows the FIFO (First In First Out) logic in which the elements are typically added at the rear and removed from the front.

A dequeue (double-ended queue) extends this functionality by allowing insertion and deletion at both ends.

1. Implementing Queue Using LinkedList

Since LinkedList has implemented a Queue interface, it has in-built methods for Queue operations:

Enqueue (add to the queue)
Dequeue (remove elements from the queue)
Peek (view through front element without removal from mount

Example: Implementing Queue Using LinkedList

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.LinkedList;
import java.util.Queue;
public class LinkedListQueueExample {
    public static void main(String[] args) {
        // Creating a queue using LinkedList
        Queue<Integer> queue = new LinkedList<>();
        // Enqueue: Adding elements to the queue
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        System.out.println("Queue after enqueue operations: " + queue);
        // Peek: Checking the front element
        System.out.println("Front element: " + queue.peek());
        // Dequeue: Removing elements from the queue
        queue.poll();
        System.out.println("Queue after one dequeue operation: " + queue);
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

2. Implementing Deque (Double-Ended Queue) Using LinkedList

A Deque or double-ended queue allows insertion as well as removal from both ends. LinkedList has implemented the Deque interface to provide additional methods:

Insertion at front and rear
Deletion from front and rear
Peeking at the front and rear

Example: Implementing Deque Using LinkedList

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Deque;
import java.util.LinkedList;
public class LinkedListDequeExample {
    public static void main(String[] args) {
        // Creating a Deque using LinkedList
        Deque<String> deque = new LinkedList<>();
        // Adding elements at both ends
        deque.addFirst("Front");
        deque.addLast("Rear");
        System.out.println("Deque after additions: " + deque);
        // Peeking at both ends
        System.out.println("First Element: " + deque.peekFirst());
        System.out.println("Last Element: " + deque.peekLast());
        // Removing elements from both ends
        deque.removeFirst();
        System.out.println("Deque after removing first element: " + deque);
        deque.removeLast();
        System.out.println("Deque after removing last element: " + deque);
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

Best Practices for Using LinkedLists in Java

Use LinkedList for Frequent Insertions/Deletions: Ideal when modifying elements at the beginning or middle, but avoid it for random access.
Prefer Iterators Over get(index) for Traversal: Iterator and ListIterator are more efficient than repeatedly calling get(index).
Optimize with addFirst() and removeFirst(): These methods perform in O(1), whereas inserting at arbitrary positions takes O(n).
Convert to ArrayList for Faster Random Access: If frequent indexing is required, transform the linked list into an array-backed list.
Use ArrayDeque Instead of LinkedList for Queues: ArrayDeque is generally faster for stack and queue operations.

Comparison: ArrayList vs LinkedList in Java

Feature	ArrayList	LinkedList
Data Structure	Dynamic array	Doubly linked list
Access Time (get(index))	O(1) – Fast random access	O(n) – Requires traversal
Insertion/Deletion at End	O(1) (Amortized) – Fast unless resized	O(1) – Always fast
Insertion/Deletion in Middle	O(n) – Requires shifting elements	O(n) – Requires traversal but no shifting
Insertion/Deletion at Beginning	O(n) – Shifting required	O(1) – Directly updates head pointer
Memory Usage	Lower (stores only elements)	Higher (stores extra pointers)
Iteration Performance	Faster (better cache locality)	Slower (scattered memory)
Best For	Read-heavy operations, random access	Frequent insertions/deletions

With this, you've learned this Java LinkedList Tutorial. The Java LinkedList is one of the basic data structures for dynamic memory management, best suited for repeated insertion, and repeated deletion. Compared to ArrayList, featuring quick random access, LinkedList best fits deques, graph-based apps, and queues. However, it has increased memory overhead and slower sequential access. By applying best practices like iterator use, and insertion optimization, you achieve maximum efficiency. If you need scalable apps, you must understand the operation of LinkedList in Java.

FAQs on Java LinkedList

1. What is the main advantage of using LinkedList over ArrayList in Java?

LinkedList performs well if there are several insertions and deletions, both near the middle or head, as it does not require shifting elements like ArrayList.

2. When should I use LinkedList instead of ArrayList?

Use LinkedList while performing repeated insertion/deletion, and ArrayList if there is a need for quick random access (get(index)).

3. Why is LinkedList slower than ArrayList for random access?

Unlike ArrayList, which has O(1) index-based access, LinkedList has an O(n) traversal time as elements are stored as nodes that are interconnected by pointers.

4. What are the key operations supported by LinkedList in Java?

The Java LinkedList data structure allows addition, removal, modification, traversal, reverse, merging, sorting, and queueing, as well as deques.

5. Does LinkedList use more memory than ArrayList?

Yes, LinkedList nodes also have other pointers (next, previous), so it takes more memory compared to ArrayList.

LinkedList in Java

What is a LinkedList in Java?

Core Concept of LinkedLists

Key Differences Between LinkedLists and Array

Advantages of LinkedList Over Array

Working of LinkedList in Java

1. How LinkedList Stores Data

2. Memory Allocation in LinkedList

3. How Memory is Allocated in a LinkedList?

4. Comparison of Memory Representation between LinkedList vs Array

5. Example: Dynamic Memory Allocation in a LinkedList

How to Create a Custom LinkedList in Java

1. Creating the Node Class

2. Creating a Custom LinkedList Class

3. Explanation of Code

Types of LinkedLists in Java

1. Singly LinkedList in Java

1.1 Structure of a Singly LinkedList

1.2 When to Use a Singly LinkedList?

1.3 Implementing a Singly LinkedList in Java

2. Doubly LinkedList in Java

2.1 Structure of a Doubly LinkedList

2.2 When to Use a Doubly LinkedList?

2.3 Implementing a Doubly LinkedList in Java

3. Circular LinkedList in Java

3.1 Structure of a Singly Circular LinkedList

3.2 Structure of a Doubly Circular LinkedList

3.3 When to Use a Circular LinkedList?

3.4 Implementing a Circular LinkedList in Java

LinkedList Operations in Java

1. Inserting Elements in Java LinkedList

1.1 How to Insert an Element at the beginning of a LinkedList in Java?

1.2 How to Insert an Element at the End of a LinkedList in Java?

1.3 How to Insert an Element at a Specific Position of LinkedList in Java?

2. How to Update the Value of an Element in a LinkedList?

3. Deleting Elements of LinkedList

4. Deleting the Last Node

5. Deleting a Node at a Specific Position

Advanced Operations on LinkedList

1. How to Reverse a LinkedList in Java

2. How to Merge the Two LinkedLists in Java

3. How to Sort a LinkedList using Merge Sort in Java

How to Iterate Over a LinkedList in Java

1. Using a While Loop

Example: Iterating with a while loop

How Does It Work?

2. Using a For Loop

Example: Iterating with a for loop

Key Difference from While Loop

3. Using an Iterator

Example: Iterating using an Iterator (Only for Java's Built-in LinkedList)

Why Use an Iterator?

4. Using a ListIterator (For Doubly LinkedLists)

Example: Using ListIterator to Traverse Forward & Backward

Key Features of ListIterator:

5. Using Java Streams (Java 8 and Later)

Example: Iterating using Java Streams

Methods of LinkedList in Java

Constructors of LinkedLists in Java

1. LinkedList() – Default Constructor

Example: Using LinkedList() Constructor

2. LinkedList(Collection c) – Copy Constructor

Serialization of LinkedList in Java

1. How to Serialize a LinkedList in Java

Example: Serializing and Deserializing a LinkedList

LinkedList Queue and Dequeue in Java

1. Implementing Queue Using LinkedList

Example: Implementing Queue Using LinkedList

2. Implementing Deque (Double-Ended Queue) Using LinkedList

Example: Implementing Deque Using LinkedList

<img decoding="async" src="https://lh7-rt.googleusercontent.com/docsz/AD_4nXdIMa-IezYbocD2Ti2DMxkZhm-AsCm6PYq2Sb9FzBHmS4Q1mORjPVpn_dT0ODThzszB3t5vUzeGIzvqLcFHmdosLncL24aPlbdwr1j5uZxFBn222ndlX5seMG2oqOtCjtEVnQoUiQ?key=2BdhPEBwyPRYzKTupo2CMz5X" width="624" height="139">

Best Practices for Using LinkedLists in Java

Comparison: ArrayList vs LinkedList in Java

FAQs on Java LinkedList

About the Author