How to Concatenate Two Linked Lists in Java

Concatenating two linked lists involves linking the end of the first list to the beginning of the second. This operation is common in various applications such as merging data from multiple sources or organizing data sequences.

In this post, we will explore how to concatenate two singly linked lists in Java.

---

Understanding Linked Lists

A linked list is a linear data structure where each element is a separate object called a node. Each node contains two parts:

1. Data: Stores the value.
2. Next: A reference (link) to the next node in the sequence.

The last node’s next pointer is null, indicating the end of the list.

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

Concatenating Two Linked Lists

To concatenate two singly linked lists, follow these steps:

1. Traverse the first list to find the last node.
2. Set the next pointer of the last node of the first list to the head of the second list.

Here’s the step-by-step process in Java:

1. Create the Node class.
2. Create the LinkedList class with methods to add nodes and concatenate lists.
3. Implement the concatenate method to link the lists.

Example Code

Below is the complete Java code for concatenating two linked lists:

// Node class representing each element in the linked list
class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// LinkedList class with methods to add and concatenate lists
class LinkedList {
    Node head;
    
    // Add a node to the end of the list
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
    
    // Concatenate two linked lists
    public void concatenate(LinkedList list2) {
        if (head == null) {
            head = list2.head;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = list2.head;
        }
    }
    
    // Print the elements of the list
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

// Test the concatenation of two linked lists
public class Main {
    public static void main(String[] args) {
        LinkedList list1 = new LinkedList();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        
        LinkedList list2 = new LinkedList();
        list2.add(4);
        list2.add(5);
        list2.add(6);
        
        System.out.println("List 1:");
        list1.printList();
        
        System.out.println("List 2:");
        list2.printList();
        
        list1.concatenate(list2);
        
        System.out.println("Concatenated List:");
        list1.printList();
    }
}

Conclusion

Concatenating linked lists is a straightforward process in Java. This method allows efficient merging of two lists by adjusting pointers without creating a new list or copying data. The approach can be adapted to various types of linked lists and is crucial for managing dynamic data structures.