Working with LinkedList Class in Java

In this lesson, you will learn.

• LinkedList and Its Features in Java
• ArrayList vs. LinkedList
• Methods of LinkedList
• Examples
• Applications of LinkedList

LinkedList in Java

1. The LinkedList class extends AbstractSequentialList and implements the List, Deque, and Queue interfaces.
2. A LinkedList  class is a linear data structure where elements are not stored in contiguous memory locations.
3. Each element (often called a node) contains its own data and a pointer (or reference) to the next and previous nodes in the sequence.
4. It is a doubly linked list that allows for efficient insertion and deletion of elements.

Key Features of LinkedList:

• Dynamic Size: LinkedLists can grow or shrink during runtime as elements are added or removed. You don’t need to pre-allocate a fixed size.
• Efficient Insertion and Deletion: Inserting or deleting elements at any position is generally efficient because it only involves updating the links of the neighboring nodes, not shifting a whole block of elements like in an ArrayList.
• Non-Contiguous Memory Allocation: Elements in a LinkedList are not stored in adjacent memory locations. Each element (node) contains the actual data and a reference (or link) to the next and/or previous element.
• Doubly Linked: Java’s LinkedList is a doubly linked list. This means each node has references to both the next and the previous node, allowing for efficient traversal in both directions.
• Implements List and Deque Interfaces: This means it inherits the functionalities of both a List (ordered collection that allows duplicate elements) and a Deque (double-ended queue, supporting element insertion and removal at both ends).

Differences between ArrayList and LinkedList

Methods of LinkedList

Here is a summary of the common methods of the LinkedList class in Java, presented in a table format:

Example: Exploring Methods of LinkedList

package collections;

import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Iterator;

public class LinkedListExample {
    public static void main(String[] args) {
        // Creating a LinkedList of Strings
        LinkedList names = new LinkedList<>();

        // 1. add(E e): Appends element to the end of this list.
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        System.out.println("Initial list: " + names); 

        // 2. add(int index, E element): Inserts at the specified position..
        names.add(1, "David");
        System.out.println("List after adding at index 1: " + names); 

        // 3. addFirst(E e): Inserts at the beginning of this list.
        names.addFirst("Eve");
        System.out.println("List after addFirst: " + names);

        // 4. addLast(E e): Appends to the end of this list (same as add(E e)).
        names.addLast("Frank");
        System.out.println("List after addLast: " + names);

        // 5. get(int index): Returns the element at the specified position
        String nameAtIndex2 = names.get(2);
        System.out.println("Element at index 2: " + nameAtIndex2); 

        // 6. getFirst(): Returns the first element
        String firstElement = names.getFirst();
        System.out.println("First element: " + firstElement); 

        // 7. getLast(): Returns the last element 
        String lastElement = names.getLast();
        System.out.println("Last element: " + lastElement); 

        // 8. remove(int index): Removes at the specified position.
        String removedAtIndex1 = names.remove(1);
        System.out.println("List after removing at index 1: " + names); 
        System.out.println("Removed element: " + removedAtIndex1); 

        // 9. remove(Object o): Removes the first occurrence, if presents
        boolean removedBob = names.remove("Bob");
        System.out.println("List after removing 'Bob': " + names);
        System.out.println("Was 'Bob' removed? " + removedBob); 

        // 10. removeFirst(): Removes and returns the first element.
        String removedFirst = names.removeFirst();
        System.out.println("List after removeFirst: " + names); 
        System.out.println("Removed first element: " + removedFirst);

        // 11. removeLast(): Removes and returns the last element 
        String removedLast = names.removeLast();
        System.out.println("List after removeLast: " + names); 
        System.out.println("Removed last element: " + removedLast);

        // 12. set(int index, E element): Replaces the element at the specified position 
        names.set(1, "George");
        System.out.println("List after setting element at index 1: " + names); 

        // 13. size(): Returns the number of elements in this list.
        int size = names.size();
        System.out.println("Size of the list: " + size); 

        // 14. contains(Object o): Returns true if this list contains element.
        boolean containsDavid = names.contains("David");
        System.out.println("Does the list contain 'David'? " + containsDavid);

        // 15. clear(): Removes all elements.
        names.clear();
        System.out.println("List after clear(): " + names); 

        // Let's re-populate for iterator examples
        names.add("Harry");
        names.add("Ivy");
        names.add("Jack");

        // 16. iterator(): Returns an iterator over the elements in this list (in proper sequence).
        System.out.println("\nIterating using Iterator:");
        Iterator iterator = names.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        // Output:
        // Iterating using Iterator:
        // Harry
        // Ivy
        // Jack

        // 17. listIterator(): Returns a list-iterator over the elements in this list (in proper sequence).
        // ListIterator provides more functionality than a regular Iterator, 
        // like bidirectional traversal and element modification.
        System.out.println("\nIterating using ListIterator:");
        ListIterator listIterator = names.listIterator();
        while (listIterator.hasNext()) {
            System.out.println("Next: " + listIterator.next() + ", Next Index: " + listIterator.nextIndex());
            if (listIterator.nextIndex() == 2) {
                listIterator.add("Kelly"); // Adds "Kelly" before the element at index 2
            }
        }
        System.out.println("List after ListIterator add: " + names); 
        // Output: List after ListIterator add: [Harry, Ivy, Kelly, Jack]

        System.out.println("\nIterating backwards using ListIterator:");
        while (listIterator.hasPrevious()) {
            System.out.println("Previous: " + listIterator.previous() + 
            		", Previous Index: " + listIterator.previousIndex());
        }
        // Output (will depend on the final position of the iterator):
        // Iterating backwards using ListIterator:
        // Previous: Kelly, Previous Index: 1
        // Previous: Ivy, Previous Index: 0
        // Previous: Harry, Previous Index: -1

        // 18. toArray(): Returns an array 
        Object[] namesArray = names.toArray();
        System.out.println("\nList as Array:");
        for (Object name : namesArray) {
            System.out.print(name + " "); // Output: Harry Ivy Kelly Jack
        }
        System.out.println();

        // 19. toArray(T[] a): Returns a specified array.
        String[] stringArray = names.toArray(new String[0]); 
        // Providing an empty array of the desired type
        System.out.println("List as String Array:");
        for (String name : stringArray) {
            System.out.print(name + " "); // Output: Harry Ivy Kelly Jack
        }
        System.out.println();
    }
}

Initial list: [Alice, Bob, Charlie]
List after adding at index 1: [Alice, David, Bob, Charlie]
List after addFirst: [Eve, Alice, David, Bob, Charlie]
List after addLast: [Eve, Alice, David, Bob, Charlie, Frank]
Element at index 2: David
First element: Eve
Last element: Frank
List after removing at index 1: [Eve, David, Bob, Charlie, Frank]
Removed element: Alice
List after removing 'Bob': [Eve, David, Charlie, Frank]
Was 'Bob' removed? true
List after removeFirst: [David, Charlie, Frank]
Removed first element: Eve
List after removeLast: [David, Charlie]
Removed last element: Frank
List after setting element at index 1: [David, George]
Size of the list: 2
Does the list contain 'David'? true
List after clear(): []

Iterating using Iterator:
Harry
Ivy
Jack

Iterating using ListIterator:
Next: Harry, Next Index: 1
Next: Ivy, Next Index: 2
Next: Jack, Next Index: 4
List after ListIterator add: [Harry, Ivy, Kelly, Jack]

Iterating backwards using ListIterator:
Previous: Jack, Previous Index: 2
Previous: Kelly, Previous Index: 1
Previous: Ivy, Previous Index: 0
Previous: Harry, Previous Index: -1

List as Array:
Harry Ivy Kelly Jack 
List as String Array:
Harry Ivy Kelly Jack 

Example 2: Working with Objects Using LinkedList

Applications of LinkedList

LinkedList is particularly useful in scenarios where frequent insertions and deletions are needed, especially at arbitrary positions within the list.

Here are some common applications:

• Implementing Stacks and Queues: LinkedList can easily implement the Stack (LIFO – Last-In, First-Out) and Queue (FIFO – First-In, First-Out) interfaces due to its efficient addition and removal at the ends.
• Undo/Redo Functionality: In text editors or graphic design software, a LinkedList can store the history of actions, allowing for easy undoing and redoing by adding or removing actions from the list.
• Navigation Between Pages: Think of the “back” and “forward” buttons in a web browser. A LinkedList can represent the history of visited pages.
• Implementing Circular Lists: The last node’s next pointer can be made to point to the first node, creating a circular linked list.
• Music Playlists: Adding, removing, or rearranging songs in a playlist can be efficiently handled using a LinkedList.
• Graph Implementations: Adjacency lists, a common way to represent graphs, often use linked lists to store the neighbors of each vertex.

End of the lesson….enjoy learning

Student Ratings and Reviews

Submit a Review