A linked list is a non-contiguous storage structure where logical ordering is maintained through node references. It belongs to the linear data structure category.

• Data Field: Contains element values
• Pointer Field: Stores references to adjacent nodes

Classification Criteria

Linked lists are categorized by three properties:

1. Dummy head presence (unused data field)
2. Circular termination (tail points to head)
3. Directionality (unidirectional vs bidirectional pointers)

Combining these properties yields 8 possible configurations.

Singly Linked List Implementation

Non-circular, unidirectional structure with out dummy head.

Node Structure

class SNode {
    int data;
    SNode link;
    
    SNode(int data) {
        this.data = data;
    }
}

Core Operations

Insert at Front

SNode firstNode;

void insertFront(int value) {
    SNode newNode = new SNode(value);
    newNode.link = firstNode;
    firstNode = newNode;
}

Append at End

void appendEnd(int value) {
    SNode newNode = new SNode(value);
    if (firstNode == null) {
        firstNode = newNode;
        return;
    }
    SNode iterator = firstNode;
    while (iterator.link != null) {
        iterator = iterator.link;
    }
    iterator.link = newNode;
}

Position-based Insert

boolean insertAtPosition(int position, int value) {
    if (position < 0 || position > getSize()) return false;
    if (position == 0) {
        insertFront(value);
        return true;
    }
    SNode current = firstNode;
    for (int i = 0; i < position - 1; i++) {
        current = current.link;
    }
    SNode newNode = new SNode(value);
    newNode.link = current.link;
    current.link = newNode;
    return true;
}

Search Operation

boolean containsValue(int target) {
    SNode tracker = firstNode;
    while (tracker != null) {
        if (tracker.data == target) return true;
        tracker = tracker.link;
    }
    return false;
}

Remove First Match

void removeFirstMatch(int target) {
    if (firstNode == null) return;
    if (firstNode.data == target) {
        firstNode = firstNode.link;
        return;
    }
    SNode prev = firstNode;
    SNode curr = firstNode.link;
    while (curr != null) {
        if (curr.data == target) {
            prev.link = curr.link;
            return;
        }
        prev = curr;
        curr = curr.link;
    }
}

Bulk Removal

void removeAllMatches(int target) {
    while (firstNode != null && firstNode.data == target) {
        firstNode = firstNode.link;
    }
    if (firstNode == null) return;
    SNode prev = firstNode;
    SNode curr = firstNode.link;
    while (curr != null) {
        if (curr.data == target) {
            prev.link = curr.link;
            curr = curr.link;
        } else {
            prev = curr;
            curr = curr.link;
        }
    }
}

Size Calculation

int getSize() {
    int count = 0;
    SNode iterator = firstNode;
    while (iterator != null) {
        count++;
        iterator = iterator.link;
    }
    return count;
}

Clear Structure

void clearList() {
    while (firstNode != null) {
        SNode temp = firstNode;
        firstNode = firstNode.link;
        temp.link = null;
    }
}

Characteristics

• Pros: Efficient insertions/deletions
• Cons: Unidirectional traversal only

Doubly Linked List Implementation

Non-circular bidirectional structure with out dummy head.

Node Structure

class DNode {
    int data;
    DNode prevLink;
    DNode nextLink;
    
    DNode(int data) {
        this.data = data;
    }
}

Core Operations

Front Insertion

DNode leadNode, tailNode;

void insertFront(int value) {
    DNode newNode = new DNode(value);
    if (leadNode == null) {
        leadNode = tailNode = newNode;
        return;
    }
    newNode.nextLink = leadNode;
    leadNode.prevLink = newNode;
    leadNode = newNode;
}

End Append

void appendEnd(int value) {
    DNode newNode = new DNode(value);
    if (tailNode == null) {
        leadNode = tailNode = newNode;
        return;
    }
    tailNode.nextLink = newNode;
    newNode.prevLink = tailNode;
    tailNode = newNode;
}

Position Insertion

boolean insertAtPosition(int position, int value) {
    if (position < 0 || position > calculateSize()) return false;
    if (position == 0) {
        insertFront(value);
        return true;
    }
    if (position == calculateSize()) {
        appendEnd(value);
        return true;
    }
    DNode target = leadNode;
    for (int i = 0; i < position; i++) {
        target = target.nextLink;
    }
    DNode newNode = new DNode(value);
    newNode.prevLink = target.prevLink;
    newNode.nextLink = target;
    target.prevLink.nextLink = newNode;
    target.prevLink = newNode;
    return true;
}

Search Operation

boolean containsValue(int target) {
    DNode iterator = leadNode;
    while (iterator != null) {
        if (iterator.data == target) return true;
        iterator = iterator.nextLink;
    }
    return false;
}

Targeted Removal

void removeFirstMatch(int target) {
    DNode iterator = leadNode;
    while (iterator != null) {
        if (iterator.data == target) {
            if (iterator == leadNode) {
                leadNode = leadNode.nextLink;
                if (leadNode != null) leadNode.prevLink = null;
                else tailNode = null;
            } else if (iterator == tailNode) {
                tailNode = tailNode.prevLink;
                tailNode.nextLink = null;
            } else {
                iterator.prevLink.nextLink = iterator.nextLink;
                iterator.nextLink.prevLink = iterator.prevLink;
            }
            return;
        }
        iterator = iterator.nextLink;
    }
}

Bulk Removal

void removeAllMatches(int target) {
    DNode iterator = leadNode;
    while (iterator != null) {
        if (iterator.data == target) {
            if (iterator == leadNode) {
                leadNode = leadNode.nextLink;
                if (leadNode != null) leadNode.prevLink = null;
                else tailNode = null;
            } else if (iterator == tailNode) {
                tailNode = tailNode.prevLink;
                tailNode.nextLink = null;
            } else {
                iterator.prevLink.nextLink = iterator.nextLink;
                iterator.nextLink.prevLink = iterator.prevLink;
            }
        }
        iterator = iterator.nextLink;
    }
}

Size Calculation

int calculateSize() {
    int count = 0;
    DNode iterator = leadNode;
    while (iterator != null) {
        count++;
        iterator = iterator.nextLink;
    }
    return count;
}

Clear Structure

void clearList() {
    DNode iterator = leadNode;
    while (iterator != null) {
        DNode next = iterator.nextLink;
        iterator.prevLink = null;
        iterator.nextLink = null;
        iterator = next;
    }
    leadNode = tailNode = null;
}

Characteristics

• Pros: Bidirectional traversal capability
• Cons: Higher memory overhead for pointers

Java LinkedList Class

Implements doubly-linked list structure with:

• No random access support
• Cloneable and serializable interfaces

Constructors

• Default constructor
• Collection-based initialization

Performance Comparison

Operation	Array-Based	Pointer-Based
Random Access	O(1)	O(n)
Insertion (End)	O(1)*	O(1)
Insertion (Mid)	O(n)	O(n)
Deletion	O(n)	O(1)**

*Amortized constant time
**With known position

Practice Exercises

• Remove all nodes with specific value
• Reverse list ordering
• Locate central node
• Combine sorted sequences
• Partition around pivot
• Verify palindrome property
• Detect sequence intersection
• Iedntify cyclic references