Navigating the world of Java collections, you’ll undoubtedly encounter the LinkedList. As a part of Java’s collections framework, LinkedList offers flexibility and features that make it an attractive choice for many scenarios. This article sheds light on the “LinkedList in Java” to enhance your Java programming journey.

LinkedList in Java: An Overview

The LinkedList class, part of the Java Collections Framework, provides an ordered collection based on a doubly-linked list. Unlike arrays, linked lists excel in scenarios where constant-time insertions or deletions are more crucial than constant-time random access.

For example:

LinkedList<String> names = new LinkedList<>();
names.add("Alice");
names.add("Bob");
names.addFirst("Eve");

In this example, names like “Alice” and “Bob” are added to the end, while “Eve” is added at the beginning.

Benefits of Using LinkedList

1. Dynamic Size: LinkedLists can grow or shrink in size dynamically, eliminating the need to determine its size beforehand.
2. Efficient Insertions/Deletions: LinkedLists provide O(1) time for insertions or deletions (provided the node is known), making them optimal for such operations.

Traversing a LinkedList in Java

Java offers the Iterator and ListIterator to traverse a LinkedList seamlessly.

ListIterator<String> iterator = names.listIterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

The ListIterator also provides the ability to traverse in both directions, something unique to LinkedLists.

Common Operations with LinkedList

Adding Elements:

names.addLast("Zara");

Removing Elements:

names.removeFirst();

Fetching Elements:

String firstPerson = names.getFirst();

LinkedList vs. ArrayList

Java offers a variety of data structures through its Collections framework. Among them, ArrayList and LinkedList are two of the most popular implementations of the List interface, each with its own strengths and weaknesses.

Underlying Data Structure:

• ArrayList: At its core, an ArrayList is backed by an array. When the array fills up, a new, larger array is created, and the old data is copied over.Example:

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");

• LinkedList: A LinkedList, on the other hand, consists of elements called nodes. Each node holds a data item and has a reference (or link) to the next node in the sequence. In the case of a doubly-linked list (which Java’s LinkedList is), each node also has a reference to the previous node.

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("X");
linkedList.add("Y");

Performance Considerations:

• Random Access: Due to its array backing, ArrayList performs constant-time random access, i.e., O(1), while LinkedList requires O(n) time as it might traverse from the start to get to the required node.
• Insertions/Deletions: In LinkedList, insertions or deletions (if you’ve direct reference to a node) are O(1), while in ArrayList it’s O(n) in the worst case (when you have to shift elements).

Memory Overhead:

• ArrayList: Uses a single array, so has minimal overhead per element.
• LinkedList: Each element carries two extra pointers for neighbor nodes, resulting in a higher memory overhead.

Resizing:

• ArrayList: Needs resizing. When elements are added and the underlying array becomes full, it’s resized (typically doubled). This can be an expensive operation, but happens rarely (amortized cost is low).
• LinkedList: Doesn’t need resizing since each element is a separate object.

Use Cases:

• ArrayList:
  • When you need to frequently access elements using an index.
  • When your primary operations are fetch and store.
  • When you have a known or fixed-size list.
• LinkedList:
  • When you need frequent insertions and deletions in the middle of the list.
  • Implementing stack/queue.
  • When you don’t know the size of the list in advance and it may grow frequently.

Code Example Demonstrating a Performance Difference:

Consider the task of adding an element to the middle of the list:

int n = 100000;  // A large number for demonstration

ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < n; i++) {
    arrayList.add(i);
}
long startTime = System.currentTimeMillis();
arrayList.add(n/2, -1);  // Insert in the middle
long endTime = System.currentTimeMillis();
System.out.println("ArrayList Insertion Time: " + (endTime - startTime) + "ms");

LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < n; i++) {
    linkedList.add(i);
}
startTime = System.currentTimeMillis();
linkedList.add(n/2, -1);  // Insert in the middle
endTime = System.currentTimeMillis();
System.out.println("LinkedList Insertion Time: " + (endTime - startTime) + "ms");

In this example, LinkedList may show a better performance due to more efficient middle insertions, especially as n grows.

Conclusion

The LinkedList in Java remains a vital tool in the developer’s toolkit. By understanding its intricacies and proper use cases, you can harness its power to create efficient and scalable applications.

Related Contents

• Java Linkedlist To Array: Java Explained
• Linkedlist Javascript: Javascript Explained
• Arraylist Linkedlist Java: Java Explained
• Arraylist Linkedlist Java: Arraylist-Java Explained
• Linkedlist Vs Arraylist Java: Arraylist-Java Explained