Exploring Linked Lists (Java)

Meet the Author: Marco Ni

Hello readers! In this article, we will be exploring linked lists in Java.

What is a Linked List?

A linked list is a data structure composed of nodes, where each node contains:

1. Data: The actual value or information stored in the node.
2. Pointer (Reference): A reference to the next node in the list.

In Java, linked lists can be implemented using the LinkedList class, which provides a doubly linked list. This means each node has references to both the next and previous nodes, allowing traversal in both directions.

Types of Linked Lists

Java’s LinkedList class supports the following types:

1. Singly Linked List: Each node has a reference to the next node.
2. Doubly Linked List: Each node has references to both the next and previous nodes (Java’s LinkedList is doubly linked).
3. Circular Linked List: The last node points back to the first node (not directly supported by Java’s LinkedList but can be implemented manually).

How Do Linked Lists Work?

Here’s a breakdown of common operations with linked lists in Java:

1. Insertion

Inserting an element involves creating a new node and updating pointers. For example, to add an element at the beginning of the list, you can use the addFirst method of the LinkedList class.

2. Traversal

To access elements, you can traverse the list from the head to the end using methods like forEach or iterators. In a doubly linked list, you can traverse in both directions.

3. Deletion

Deleting a node involves updating the pointers of adjacent nodes. In Java’s LinkedList, you can use methods like remove to delete elements.

Why Use Linked Lists?

Linked lists offer several advantages:

• Dynamic Size: They can grow and shrink dynamically, making them ideal for situations where the number of elements is unknown or changes frequently.
• Efficient Insertions/Deletions: Inserting or removing elements is more efficient than with arrays, especially in large lists, as no elements need to be shifted.
• Memory Utilization: They don’t require contiguous memory allocation, which can be advantageous in fragmented memory scenarios.

However, linked lists have some drawbacks:

• Slower Access: Accessing elements is slower than arrays because you must traverse the list sequentially.
• Extra Memory: Each node requires extra memory for the pointer/reference.

Working with Linked Lists in Java

Here’s a simple example of using the LinkedList class in Java:

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();

        // Inserting elements
        list.add(10);      // Adds to the end of the list
        list.addFirst(20); // Adds to the beginning of the list
        list.addLast(30);  // Adds to the end of the list

        // Displaying elements
        System.out.println("Linked List: " + list);

        // Removing elements
        list.removeFirst(); // Removes the first element
        list.removeLast();  // Removes the last element

        // Displaying elements after removal
        System.out.println("Linked List after removal: " + list);

        // Traversing the list
        for (Integer num : list) {
            System.out.println(num);
        }
    }
}

Output:

Linked List: [20, 10, 30]
Linked List after removal: [10]
10