Linked Lists Overview

Linked lists implement linear sequences using nodes connected via pointers, enabling non-contiguous memory storage. Each node contains:

• Data field: Stores element values
• Pointer field: References adjacent nodes

Classification Criteria

• Dummy head: Fixed header node with invalid data
• Directionality: Single (unidirectional traversal) vs. double (bidirectional traversal)
• Cyclicity: Tail pointer references head node

This implementation covers non-dummy-head non-cyclic singly and doubly linked lists.

Singly Linked List Implementation

public class SinglyLinkedList {
    private Node start;
    
    public void prepend(int value);
    public void append(int value);
    public void insertAt(int position, int value);
    public boolean exists(int target);
    public void deleteFirstOccurrence(int target);
    public void deleteAllOccurrences(int target);
    public int length();
    public void erase();
    public void print();
    
    private static class Node {
        int value;
        Node successor;
        
        Node(int value) {
            this.value = value;
        }
    }
}

Prepend Operation

public void prepend(int value) {
    Node newNode = new Node(value);
    newNode.successor = start;
    start = newNode;
}

Append Operation

public void append(int value) {
    Node newNode = new Node(value);
    if (start == null) {
        start = newNode;
    } else {
        Node current = start;
        while (current.successor != null) {
            current = current.successor;
        }
        current.successor = newNode;
    }
}

Position-Based Insertion

public void insertAt(int position, int value) {
    if (position < 0 || position > length()) {
        throw new IndexOutOfBoundsException();
    }
    if (position == 0) {
        prepend(value);
        return;
    }
    if (position == length()) {
        append(value);
        return;
    }
    Node current = start;
    for (int i = 1; i < position; i++) {
        current = current.successor;
    }
    Node newNode = new Node(value);
    newNode.successor = current.successor;
    current.successor = newNode;
}

Existence Check

public boolean exists(int target) {
    Node current = start;
    while (current != null) {
        if (current.value == target) {
            return true;
        }
        current = current.successor;
    }
    return false;
}

Target Deletion

public void deleteFirstOccurrence(int target) {
    if (start == null) return;
    if (start.value == target) {
        start = start.successor;
        return;
    }
    Node previous = start;
    Node current = start.successor;
    while (current != null) {
        if (current.value == target) {
            previous.successor = current.successor;
            return;
        }
        previous = previous.successor;
        current = current.successor;
    }
}

Complete List Erasure

public void erase() {
    while (start != null) {
        Node next = start.successor;
        start.successor = null;
        start = next;
    }
}

Singly Linked List Characteristics

Advantages: Efficient node insertion/deletion
Limitations: No predecessor access; unidirectional traversal

Doubly Linked List Implementation

public class DoublyLinkedList {
    private Node first;
    private Node last;
    
    public void prepend(int value);
    public void append(int value);
    public void insertAt(int position, int value);
    public boolean exists(int target);
    public void deleteFirstOccurrence(int target);
    public void deleteAllOccurrences(int target);
    public int length();
    public void erase();
    
    private static class Node {
        int value;
        Node predecessor;
        Node successor;
        
        Node(int value) {
            this.value = value;
        }
    }
}

Bidirectional Insertion

public void insertAt(int position, int value) {
    if (position < 0 || position > length()) {
        throw new IndexOutOfBoundsException();
    }
    if (position == 0) {
        prepend(value);
        return;
    }
    if (position == length()) {
        append(value);
        return;
    }
    Node current = first;
    for (int i = 0; i < position; i++) {
        current = current.successor;
    }
    Node newNode = new Node(value);
    newNode.predecessor = current.predecessor;
    newNode.successor = current;
    current.predecessor.successor = newNode;
    current.predecessor = newNode;
}

Target Removal

public void deleteFirstOccurrence(int target) {
    Node current = first;
    while (current != null) {
        if (current.value == target) {
            if (current == first) {
                first = first.successor;
                if (first != null) first.predecessor = null;
            } else if (current == last) {
                last = last.predecessor;
                last.successor = null;
            } else {
                current.predecessor.successor = current.successor;
                current.successor.predecessor = current.predecessor;
            }
            return;
        }
        current = current.successor;
    }
}

Doubly Linked List Characteristics

Advantages: Bidirectional traversal; predecessor access
Limitations: Increased memory overhead; complex pointer management

Java Collections Framework Integration

The java.util.LinkedList implements a non-dummy-head bidirectional non-cyclic list.

Core Functionlaity

• Implements List, Deque, and Cloneable interfaces
• Excludes RandomAccess due to sequential access nature

Traversal Techniques

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);

// Standard printing
System.out.println(list);

// Index-based iteration
for (int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i));
}

// Enhanced for-loop
for (int num : list) {
    System.out.print(num);
}

// Iterator
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    System.out.print(it.next());
}

// Bidirectional traversal
ListIterator<Integer> lit = list.listIterator(list.size());
while (lit.hasPrevious()) {
    System.out.print(lit.previous());
}