A linked list is a linear data structure where each element—called a node—contains data and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation and can dynamically grow or shrink at runtime.

Each node typically consists of two parts: a value field and a next pointer. Insertion can be performed efficiently at the beginning (head insertion) or end (tail insertion) of the list.

Custom Linked List Implementation

public class ListNode {
    public int data;
    public ListNode next;

    public ListNode(int data) {
        this.data = data;
    }
}

public class CustomLinkedList {
    private ListNode head;

    // Insert at the beginning
    public void insertAtHead(int value) {
        ListNode newNode = new ListNode(value);
        newNode.next = head;
        head = newNode;
    }

    // Insert at the end
    public void insertAtTail(int value) {
        ListNode newNode = new ListNode(value);
        if (head == null) {
            head = newNode;
            return;
        }
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Print all elements
    public void display() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

Example usage:

public class Main {
    public static void main(String[] args) {
        CustomLinkedList list = new CustomLinkedList();
        list.insertAtTail(1);
        list.insertAtTail(2);
        list.insertAtHead(0);
        list.insertAtHead(-1);
        list.display(); // Output: -1 -> 0 -> 1 -> 2 -> null
    }
}

Java’s Built-in LinkedList

Java provides java.util.LinkedList, which implements both the List and Deque interfaces. Internally, it uses a doubly linked list, meaning each node has references to both the next and previous nodes.

Common Constructors

• new LinkedList<>(): Creates an empty list.
• new LinkedList<>(Collection<? extends E> c): Initializes the list with elements from another collection.

Key Operations

Adding Elements

• add(E e): Appends to the end.
• addFirst(E e): Adds to the front.
• addLast(E e): Adds to the end (equivalent to add).

Accessing Elements

• get(int index): Retrieves element at a specific index (O(n)).
• getFirst(), getLast(): Return first/last elements (O(1)).

Removing Elements

• remove(int index): Removes by index.
• removeFirst(), removeLast(): Remove from ends (O(1)).

Other Utilities

• contains(Object o): Checks for element presence.
• size(), isEmpty(), clear(): Manage list state.

LinkedList vs ArrayList

Feature	LinkedList	ArrayList
Underlying Structure	Doubly linked list	Dynamic array
Insert/Delete (middle)	O(1) with iterator, O(n) by index	O(n) due to shifting
Random Access	O(n)	O(1)
Memory Overhead	Higher (stores prev/next pointers)	Lower (only stores elements)
Initial Capacity	N/A (grows per node)	Default 10
Resizing	Not applicable	Grows by 50% (old + old >> 1)

ArrayList excels when frequent random access is needed, while LinkedList is preferable for frequent insertions/deletions at the ends or when using iterators for modifications. However, due to poor cache locality and higher memory overhead, LinkedList is often less effiicent in practice than common assumed.