LinkedList

About

The LinkedList class in Java is a part of the java.util package and implements both the List and Deque interfaces. It is a doubly-linked list, meaning each node in the list contains three elements:

• Data: The value stored in the node.

• Reference to the next node: Pointer to the next element in the list.

• Reference to the previous node: Pointer to the previous element in the list.

Since it implements the Deque interface, LinkedList can function as a FIFO (First-In-First-Out) queue or LIFO (Last-In-First-Out) stack.

Features

1. Dynamic Size: Unlike arrays, LinkedList can dynamically grow and shrink as elements are added or removed.

2. Efficient Insertions/Deletions: Adding or removing elements from the beginning or middle is efficient compared to ArrayList.

3. Implements Multiple Interfaces:

   • List: Allows indexed access and supports duplicate elements.

   • Deque: Enables usage as a stack, queue, or deque.

4. Non-Synchronized: Not thread-safe by default but can be synchronized using Collections.synchronizedList.

5. Allows Nulls: Null elements are allowed as valid entries.

6. Iterators: Provides fail-fast iterators that throw ConcurrentModificationException if the list is structurally modified while iterating.

Internal Working

1. Structure: Each element (node) of a LinkedList contains three parts:

   • Data: The actual value stored in the node.

   • Next: A reference to the next node in the list.

   • Previous: A reference to the previous node in the list.

2. Node Class: The LinkedList internally uses a static nested class Node<E> to represent each element in the list. A static nested class is a class declared inside another class with the static modifier. Unlike inner classes, a static nested class does not require an instance of the enclosing class to be instantiated.

   public class LinkedList<E> {
       private static class Node<E> {
           E item;
           Node<E> next;
           Node<E> prev;
   
           Node(Node<E> prev, E element, Node<E> next) {
               this.item = element;
               this.next = next;
               this.prev = prev;
           }
       }
   }

3. Head and Tail Pointers:

   • Head: Points to the first node.

   • Tail: Points to the last node.

4. Traversal:

   • Forward Traversal: Starts from the head and moves through the next reference.

   • Backward Traversal: Starts from the tail and moves through the prev reference.

Key Methods

Here are some of the commonly used methods in LinkedList and their descriptions:

Method	Description
add(E e)	Appends the specified element to the end of the list.
add(int index, E element)	Inserts the element at the specified position in the list.
addFirst(E e) / offerFirst(E e)	Adds the element at the beginning of the list.
addLast(E e) / offerLast(E e)	Adds the element at the end of the list.
remove()	Removes the first element (head) of the list.
removeFirst() / pollFirst()	Removes and returns the first element.
removeLast() / pollLast()	Removes and returns the last element.
get(int index)	Returns the element at the specified position.
getFirst() / peekFirst()	Retrieves the first element without removing it.
getLast() / peekLast()	Retrieves the last element without removing it.
size()	Returns the number of elements in the list.
contains(Object o)	Returns true if the list contains the specified element.
indexOf(Object o) / lastIndexOf(Object o)	Returns the index of the first/last occurrence of the specified element.
clear()	Removes all elements from the list.
descendingIterator()	Returns an iterator that iterates in reverse order.

Big O Complexity for Operations

Operation	Complexity	Explanation
Access (by index)	O(n)	Traverses the list from the beginning or end, whichever is closer to the index.
Insertion (at head/tail)	O(1)	Adding elements at the start or end is constant time due to direct pointer manipulation.
Insertion (at index)	O(n)	Requires traversal to the index, then updates pointers.
Deletion (head/tail)	O(1)	Removing the first or last element is constant time.
Deletion (at index)	O(n)	Requires traversal to the index, then updates pointers.
Search	O(n)	Needs to traverse the list to find the element.

Examples

1. Basic Usage

import java.util.LinkedList;

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

        // Adding elements
        list.add("Alice");
        list.add("Bob");
        list.add("Charlie");
        System.out.println(list); // Output: [Alice, Bob, Charlie]

        // Adding at specific positions
        list.addFirst("Zara");
        list.addLast("Daniel");
        System.out.println(list); // Output: [Zara, Alice, Bob, Charlie, Daniel]

        // Accessing elements
        System.out.println("First: " + list.getFirst()); // Output: First: Zara
        System.out.println("Last: " + list.getLast());   // Output: Last: Daniel
        System.out.println("Index 2: " + list.get(2));   // Output: Index 2: Bob

        // Removing elements
        list.remove(); // Removes the first element
        System.out.println(list); // Output: [Alice, Bob, Charlie, Daniel]

        list.removeLast(); // Removes the last element
        System.out.println(list); // Output: [Alice, Bob, Charlie]
    }
}

2. Queue Operations

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        System.out.println(queue); // Output: [10, 20, 30]

        System.out.println("Peek: " + queue.peek()); // Output: Peek: 10
        System.out.println("Poll: " + queue.poll()); // Output: Poll: 10
        System.out.println(queue); // Output: [20, 30]
    }
}

3. Stack Operations

import java.util.LinkedList;

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

        stack.push(5); // Push onto stack
        stack.push(10);
        stack.push(15);
        System.out.println(stack); // Output: [15, 10, 5]

        System.out.println("Pop: " + stack.pop()); // Output: Pop: 15
        System.out.println(stack); // Output: [10, 5]
    }
}

4. Converting to Array

import java.util.LinkedList;

public class ArrayConversion {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("Red");
        list.add("Green");
        list.add("Blue");

        String[] array = list.toArray(new String[0]);
        for (String color : array) {
            System.out.println(color); 
            // Output:
            // Red
            // Green
            // Blue
        }
    }
}