Linked List Variants

Singly linked lists contain nodes with a single pointer to the next node. Doubly linked lists include two pointers per node: one to the next node and one to the previous node, enabling bidirectional traversal. Circular linked lists form a closed loop where the last node points back to the first node, useful for solving problems like the Josephus puzzle.

Memory Allocation Patterns

Unlike arrays which occupy contiguous memory blocks, linked list nodes are scattered across non-adjacent memory locations. Pointers connect these dispersed nodes into a coherent sequence, with allocation managed by the operating system's memory handler.

Node Structure Definition

Proper node implementation is essential for linked list operations. Here's a Java node definition:

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

Element Removal Techniques

Deleting a node involves redirecting the previous node's pointer to bypass the target node. Memory deallocation is required in manual memory management languages like C++. Head node removal requires special handling or a dummy head approach for consistent behavior.

LeetCode 203: Element Removal Implementation

This solution removes all nodes containing specified values using a dummy head for uniform handling:

public ListNode removeNodes(ListNode head, int target) {
    ListNode dummy = new ListNode(-1, head);
    ListNode previous = dummy;
    ListNode current = head;
    
    while (current != null) {
        if (current.data == target) {
            previous.next = current.next;
        } else {
            previous = current;
        }
        current = current.next;
    }
    return dummy.next;
}

LeetCode 707: Custom Linked List Implementation

A comprehensive linked list implementation with five core operations using a dummy head node:

class CustomLinkedList {
    private int nodeCount;
    private ListNode dummyHead;

    public CustomLinkedList() {
        nodeCount = 0;
        dummyHead = new ListNode(0);
    }

    public int fetch(int position) {
        if (position < 0 || position >= nodeCount) return -1;
        ListNode current = dummyHead;
        for (int i = 0; i <= position; i++) {
            current = current.next;
        }
        return current.data;
    }

    public void insertHead(int value) {
        insertAtPosition(0, value);
    }

    public void insertTail(int value) {
        insertAtPosition(nodeCount, value);
    }

    public void insertAtPosition(int position, int value) {
        if (position > nodeCount) return;
        position = Math.max(0, position);
        ListNode predecessor = dummyHead;
        for (int i = 0; i < position; i++) {
            predecessor = predecessor.next;
        }
        ListNode newNode = new ListNode(value);
        newNode.next = predecessor.next;
        predecessor.next = newNode;
        nodeCount++;
    }

    public void removeAtPosition(int position) {
        if (position < 0 || position >= nodeCount) return;
        ListNode predecessor = dummyHead;
        for (int i = 0; i < position; i++) {
            predecessor = predecessor.next;
        }
        predecessor.next = predecessor.next.next;
        nodeCount--;
    }
}

LeetCode 206: List Reversal Techniques

An iterative approach to reverse node pointers without additional memory allocation:

public ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextNode = current.next;
        current.next = previous;
        previous = current;
        current = nextNode;
    }
    return previous;
}

A recursive implementation for list reversal:

public ListNode reverseRecursive(ListNode head) {
    return reverseNodes(null, head);
}

private ListNode reverseNodes(ListNode prev, ListNode curr) {
    if (curr == null) return prev;
    ListNode nextNode = curr.next;
    curr.next = prev;
    return reverseNodes(curr, nextNode);
}