Linked List in Java: Complete Guide with Implementation

LinkedList (Part 1) - Continuing the DSA Series

Welcome back to the DSA series! In this chapter, we dive deep into Linked Lists, one of the fundamental data structures in computer science. Linked Lists are an essential topic in Data Structures and Algorithms (DSA) because they provide dynamic memory allocation, unlike arrays that have fixed sizes. Mastering Linked Lists will help you handle real-world problems efficiently, especially in memory-constrained environments.

In this chapter, we'll cover several concepts related to Linked Lists in detail, breaking down each aspect and demonstrating how to implement them step by step. Here’s the roadmap of what we’ll cover:

1. Introduction to Linked List

A Linked List is a dynamic data structure that is linear in nature, just like arrays or array-based structures such as ArrayList. In our earlier exploration of data structures, we visualized arrays as contiguous memory blocks that store elements one after another. Similarly, we can visualize a Linked List as a linear sequence of nodes that are connected to each other.

For example, in an array, the elements might look like this:

[1, 2, 3, 4, 5]

Each element is stored in a consecutive memory location. However, in a Linked List, we do not rely on contiguous memory; instead, each element, called a node, contains the data and a reference (or pointer in languages like C++) to the next node. This structure gives us more flexibility in terms of memory usage, allowing the list to grow or shrink dynamically without worrying about resizing like we would with arrays.

What is a Linked List?

A Linked List is a collection of nodes where each node consists of two parts:

Data: The value stored in the node. This can be any data type such as an integer (int), character (char), boolean (boolean), or float (float).
Next: A reference to the next node in the sequence. The last node in the list points to null, indicating the end of the list.

Visualizing a Linked List:

[Data | Next] -> [Data | Next] -> [Data | Next] -> null

In this visualization:

The Data field holds the value for each node.
The Next field holds a reference to the next node in the list.
The last node in the list has its Next pointing to null, signifying that it’s the end of the Linked List.

Structure of a Node in a Linked List

If we visualize the nodes in a Linked List, each node has the same structure:

Data: It holds the actual information of the node, such as an integer, character, or any other type.
Next: It is a reference to the next node in the sequence.

In C++ or lower-level languages, we use pointers to link nodes together, but in Java, we use reference variables. These reference variables store the memory address of the next node, allowing us to traverse through the Linked List.

In object-oriented programming (OOP), which we discussed earlier, references point to objects in memory. Since each node in a Linked List has the same structure (data and a reference to the next node), we need a class to represent each node.

Creating the Node Class

To represent a node in Java, we define a Node class. This class will have two fields:

Data: This stores the actual value of the node.
Next: This is a reference to the next node in the list.

Here’s how we define the Node class in Java:

class Node {
    int data;   // This stores the data part of the node
    Node next;  // This stores the reference to the next node in the Linked List

    // Constructor to create a new node with a given data value
    public Node(int data) {
        this.data = data;   // Assign the given data to the data field
        this.next = null;   // Initially, the next node is null because it doesn't point to anything yet
    }
}

Explanation:

The class Node represents a single node in the Linked List.
The data field stores the value of the node.
The next field holds the reference to the next node. Initially, this is set to null because when a node is created, it doesn’t link to any other node yet.
The constructor Node(int data) initializes a new node with a given data value, and the next reference is set to null as there is no next node when a node is first created.

2. Head and Tail in a Linked List

In a Linked List (LL), we always keep track of two important pointers or references:
- Head: This points to the first node of the Linked List.
- Tail: This points to the last node of the Linked List.

These two references are essential because:

The head helps us start traversing the Linked List. It gives us a starting point to access any node.
The tail helps in efficiently adding new nodes to the end of the list. This saves time when appending nodes to the end since we don't have to traverse the entire list to find the last node.

Understanding Head and Tail

Head:

The head node is the first node in the Linked List.
If the Linked List is empty, the head is null.
Every time we add a node at the front of the list, we update the head to point to this new node.

Tail:

The tail node is the last node in the Linked List.
Unlike the head, the tail helps to quickly add nodes at the end of the list without traversing the entire Linked List.
If we have only one node in the list, both the head and tail point to the same node.
The tail's next reference always points to null since it’s the last node.

Single Node Case:

In the case where the Linked List has only one node, both the head and tail point to the same node. This is because the list starts and ends with this single node.
For example:
```
  [Head/Tail] -> [Data | null]
```
This node is both the first and the last node, so the head and tail refer to the same node.

Head and Tail as Properties

In a Linked List, we typically define head and tail as properties of the Linked List class, so they can be tracked and managed throughout the list's lifecycle. These properties allow us to:

Head: Always keep track of the starting point of the list.
Tail: Efficiently add nodes to the end of the list.
Why Not Use null for the Tail?
- The tail should always point to the last node in the list, and that node's next reference should be null, not the tail itself.
- This allows us to easily add new nodes to the end of the list by updating the tail reference without needing to traverse the entire list.

Method Separation and Code Organization

In a well-structured Linked List class, we typically define separate methods for different operations like:

addFirst(): Add a node at the beginning of the list.
addLast(): Add a node at the end of the list.
search(): Search for an element in the list.
printList(): Print the entire list.

These methods help organize the code, making it reusable and easy to manage. By separating these operations, the main function remains clean and focused on high-level tasks rather than dealing with the specifics of list manipulation.

3. Add First in a Linked List

Explanation of `addFirst()` Method in a Linked List

Adding a new node at the beginning of a Linked List (LL) is referred to as the addFirst() operation. This method ensures that a new node is placed at the start, and the existing nodes are adjusted accordingly. Let’s walk through the steps involved in detail.

What Does "Add First" Mean?

In Linked Lists, the addFirst() method inserts a new node at the front of the list. When we add a node at the beginning:

We create a new node.
The new node’s next pointer will point to the current head node.
The head pointer is updated to point to the new node.

This way, the new node becomes the first element in the Linked List. If the Linked List is empty, both the head and tail will point to this new node.

Visualization of the `addFirst()` Method

Let’s say we have an initially empty Linked List. We will perform the following operations:

Add the first node (2).
Add another node (1) at the beginning.

Step-by-Step Visualization

Initial State (Empty List)

The Linked List is empty:

head = null
tail = null

head -> null
tail -> null

Operation 1: Add First Node (2)

We create a new node 2.
Since the list is empty, both head and tail will point to this new node.

Memory Allocation:

New Node:
+-------+------+
|  data | next |
|   2   | null |
+-------+------+

Resulting Linked List:

head -> +-------+------+
        |  data | next |
        |   2   | null | <- tail
        +-------+------+

Now, both head and tail point to this single node. Since this is the only node, its next pointer is null.

Operation 2: Add First Node (1)

We create a new node 1.
This new node’s next will point to the current head (2).
The head will be updated to point to the new node (1).

Memory Allocation:

New Node:
+-------+------+
|  data | next |
|   1   | null |  <- newly created node
+-------+------+

Existing Node:
+-------+------+
|  data | next |
|   2   | null | <- current head and tail
+-------+------+

Steps:

Set the new node’s next to the current head:

 newNode.next = head;  // newNode(1).next points to node(2)

Update the head to point to the new node:

 head = newNode;  // head now points to node(1)

Resulting Linked List:

head -> +-------+------+
        |  data | next |
        |   1   |  o---+----> +-------+------+
        +-------+------+      |  data | next |
                              |   2   | null | <- tail
                              +-------+------+

Now, the new node 1 becomes the head, and it points to the previous node 2. The tail remains unchanged and points to 2, as it is still the last node.

Visualization of the Process

Here’s a more formal breakdown of each state and transition:

1. Initial State (Empty List)

head -> null
tail -> null

2. After Adding First Node (2)

head -> +-------+------+
        |  data | next |
        |   2   | null | <- tail
        +-------+------+

3. After Adding Second Node (1)

head -> +-------+------+
        |  data | next |
        |   1   |  o---+----> +-------+------+
        +-------+------+      |  data | next |
                              |   2   | null | <- tail
                              +-------+------+

Explanation of the Steps:

Creating a new node involves allocating memory for the new node and setting its data and next fields.
Adjusting pointers means updating the next of the new node to point to the old head, and then updating the head itself to point to this new node.
Updating head and tail ensures the new node becomes the first element, while the tail remains pointing to the last element (in this case, node 2).

Step-by-Step Process(Code)

Step 1: Create a New Node
- Before adding a new node, we first need to create it. In this step, a new node is created with the given data.
- The new node's next pointer will initially be null.

    Node newNode = new Node(data);  // Create the new node with the given data

If the Linked List is empty, the new node will become both the head and the tail of the list, as it is the only node.

    if (head == null) {
        head = tail = newNode;  // If empty, both head and tail point to the new node
        return;  // Exit the method since there are no other nodes to adjust
    }

Step 2: Make New Node's next Point to the Current Head
- The newly created node should point to the current head of the Linked List. This is because the new node will now be placed at the start, and its next should refer to the old first node.
- The new node’s next is set to the current head node.

    newNode.next = head;  // New node points to the current head

Detailed Explanation:

The current head node is the first node of the list.
By setting newNode.next = head;, we link the new node to the old head. This operation means that the new node now becomes the first node, and the old head becomes the second node.

Step 3: Update the Head to the New Node
- The head now needs to be updated to point to the newly added node, as this new node is now the first node of the Linked List.
- The head is reassigned to refer to the new node.

    head = newNode;  // Update the head to point to the new node

Explanation:

This step simply updates the reference to the new node. Now, the head points to the newly created node, and the rest of the list follows from there.

Special Case: Empty Linked List

If the Linked List is empty (head == null), both head and tail should point to the newly created node, because it is the only node in the list. This is a special case since normally the tail remains unaffected by the addition of nodes at the front.
If we only have one node, both head and tail will point to this single node.

Code Implementation: `addFirst()`

public void addFirst(int data) {
    // Step 1: Create a new Node
    Node newNode = new Node(data);
    size++;  // Increase the size of the linked list

    // Special case: If the LinkedList is empty, both head and tail point to the new node
    if (head == null) {
        head = tail = newNode;
        return;
    }

    // Step 2: NewNode's next points to the current head
    newNode.next = head;

    // Step 3: Update the head to point to the new node
    head = newNode;
}

Why Changing Head Doesn’t Affect Its Address?

The head in a Linked List is simply a reference (or pointer) to the first node. When you change the head, you are just changing where this reference points, but you are not changing the actual nodes.

The head itself is not the node; it’s a pointer to a node.
When we assign head = newNode;, we are not modifying the memory address of the old head node. We are merely updating the reference, making it point to the new node.

Time Complexity of `addFirst()`

The time complexity of adding a node at the beginning of the Linked List (i.e., the addFirst() operation) is O(1). This is because:

We do not need to traverse the Linked List to find the position where the new node should be added.
The operation consists of creating a node, adjusting its next pointer, and updating the head, all of which take constant time.

Thus, addFirst() is an efficient operation with a time complexity of O(1).

The addFirst() method adds a new node at the beginning of the Linked List, making it the new head. The steps involve creating a new node, linking it to the old head, and updating the head to point to this new node. The method is efficient with O(1) time complexity, and when the list is empty, both the head and tail point to the new node.

4. Add Last in a Linked List

Adding a node at the end of the list requires:

Traversing to the last node (the current tail).
Updating the tail's next pointer to point to the new node.
Setting the new node as the new tail.

This operation has a time complexity of O(n) due to the traversal required to reach the end.

5. Print a Linked List

To print all the elements in the Linked List, we traverse from the head to the tail and print each node’s data. This process gives us a clear representation of the list.

6. Add in the Middle of a Linked List

Adding a node at a specific position in the middle involves:

Traversing to the node just before the desired position.
Updating the next pointers to insert the new node in between.

This is more complex than adding at the beginning or end, but it's a powerful operation for modifying Linked Lists dynamically.

7. Size of a Linked List

The size of a Linked List refers to the total number of nodes in the list. We can determine the size by traversing the list and counting the nodes as we go. The size is helpful for various operations, such as middle element retrieval and boundary checks.

8. Remove First in a Linked List

Removing the first node is simple:

Update the head to the second node (i.e., head = head.next).
If the list becomes empty, make sure to handle that by setting both the head and tail to null.

This operation runs in O(1) time.

9. Remove Last in a Linked List

Removing the last node requires:

Traversing the list to the second-last node.
Updating the second-last node’s next pointer to null and updating the tail.

This operation takes O(n) time due to the traversal.

10. Iterative Search in a Linked List

Searching for a specific element in a Linked List iteratively involves traversing from the head to the tail and comparing each node’s data with the target element. If found, the node’s position is returned.

11. Recursive Search in a Linked List

Recursive search is another way to look for a specific element. We recursively traverse the list, checking each node until the target is found or the end of the list is reached.

12. Reverse a Linked List

Reversing a Linked List involves flipping the direction of the next pointers such that the head becomes the tail and vice versa. We can implement this both iteratively and recursively.

13. Find and Remove Nth Node from the End

To find and remove the Nth node from the end of the Linked List:

We use two pointers: one that starts moving N steps ahead, and another that begins from the head. When the first pointer reaches the end, the second pointer will be at the Nth node from the end.
This method helps avoid traversing the list twice.

14. Check if a Linked List is a Palindrome

A Linked List is said to be a palindrome if its elements read the same forward and backward. To check this:

We can use a slow and fast pointer to find the middle of the list.
Then, reverse the second half of the list and compare it with the first half.

15. Code: Check if a Linked List is a Palindrome

Here’s how we can implement the logic to check if a Linked List is a palindrome in Java:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListPalindrome {
    public boolean isPalindrome(Node head) {
        if (head == null || head.next == null) {
            return true;
        }

        // Find the middle of the LinkedList
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse the second half
        Node reversedHead = reverseList(slow);

        // Compare both halves
        Node current = head;
        while (reversedHead != null) {
            if (current.data != reversedHead.data) {
                return false;
            }
            current = current.next;
            reversedHead = reversedHead.next;
        }
        return true;
    }

    // Helper method to reverse the LinkedList
    public Node reverseList(Node head) {
        Node prev = null;
        Node current = head;

        while (current != null) {
            Node next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
}

By the end of this chapter, you'll have a thorough understanding of the operations that can be performed on Linked Lists, and you’ll be able to implement various operations with ease. Stay tuned for the next part, where we’ll explore advanced Linked List concepts!

Related Posts in My Series:

DSA in Java Series:

Chapter 2: Operators in Java – Learn about the different types of operators in Java, including arithmetic, relational, logical, and assignment operators, along with examples to understand their usage.
Chapter 33: Trie in Java – Explore the implementation and use of Trie data structure in Java, a powerful tool for handling strings, with practical coding examples.

Other Series:

Full Stack Java Development – Master the essentials of Java programming and web development with this series. Topics include object-oriented programming, design patterns, database interaction, and more.
Full Stack JavaScript Development – Become proficient in JavaScript with this series covering everything from front-end to back-end development, including frameworks like React and Node.js.

Connect with Me
Stay updated with my latest posts and projects by following me on social media:

LinkedIn: Connect with me for professional updates and insights.
GitHub: Explore my repositories and contributions to various projects.
LeetCode: Check out my coding practice and challenges.

Your feedback and engagement are invaluable. Feel free to reach out with questions, comments, or suggestions. Happy coding!

Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast

Chapter 21 : LinkedList(Part 1)

Table of contents