Singly Linked List

A linear collection of nodes where each node contains data and a reference to the next node. Provides O(1) insertion/deletion at the beginning.

How Singly Linked List Works Internally

Node Structure

Each node contains two fields: data (the actual value) and next (a reference/pointer to the next node). The last node's next is null.

class Node {
    E data;
    Node next;
}

Head and Tail References

The list maintains a head reference pointing to the first node. Optionally, a tail reference points to the last node, enabling O(1) insertion at the end.

Sequential Access

To access element at index i, you must start at head and follow i "next" pointers. This is why get(index) is O(n) - you can't jump directly to a position.

Pointer Manipulation

Insert and delete operations involve changing "next" pointers. No shifting of elements is needed - just redirect the pointers. This is the key advantage over ArrayList for certain operations.

Time Complexity

Operation	Time	Why
get(index)	O(n)	Must traverse from head to index
set(index, value)	O(n)	Must traverse from head to index
addFirst(value)	O(1)	Just update head pointer
addLast(value)	O(1)*	O(1) with tail pointer, O(n) without
add(index, value)	O(n)	Must traverse to index-1, then O(1) insert
removeFirst()	O(1)	Just update head pointer
removeLast()	O(n)	Must traverse to find second-to-last
remove(index)	O(n)	Must traverse to index-1, then O(1) remove

* With tail pointer maintained

Interactive Visualizer

Try different operations and watch how pointers are updated. Notice the traversal needed to access middle elements.

Size: 4

head↓

[0]10

→

[1]20

→

[2]30

→

[3]40

→ null

← tail

Node data Pointer

Operation

Index

Value

Speed:

Java Implementation

public void add(int index, E element) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException();
    Node newNode = new Node(element);
    if (index == 0) {
        newNode.next = head;
        head = newNode;
        if (tail == null) tail = newNode;
    } else if (index == size) {
        tail.next = newNode;
        tail = newNode;
    } else {
        Node prev = getNode(index - 1);
        newNode.next = prev.next;
        prev.next = newNode;
    }
    size++;
}

Pseudocode

1. Check if index is valid (0 to size)

2. Create a new node with the element

3. If adding at index 0:

- Point new node to current head

- Update head to new node

4. If adding at end:

- Point current tail to new node

- Update tail to new node

5. If adding in middle:

- Traverse to node at index-1

- Point new node to node at index

- Point previous node to new node

6. Increment size

Node Class Structure

private class Node {
    E data;
    Node next;

    Node(E data) {
        this.data = data;
        this.next = null;
    }
}

Pointer Operations Explained

addFirst(value) - O(1)

1. Create new node 2. Set new.next = head 3. Set head = new

Before: head → [A] → [B] → [C] → null

After: head → [NEW] → [A] → [B] → [C] → null

removeFirst() - O(1)

1. Save head.data 2. Set head = head.next 3. Return saved data

Before: head → [A] → [B] → [C] → null

After: head → [B] → [C] → null (A removed)

add(1, value) - Insert at index 1

1. Traverse to node at index 0 2. Create new node 3. Set new.next = prev.next 4. Set prev.next = new

Before: head → [A] → [B] → [C] → null

After: head → [A] → [NEW] → [B] → [C] → null

Edge Cases to Consider

Empty List Operations

• head == null indicates empty list
• addFirst on empty: new node becomes both head and tail
• removeFirst on empty → NoSuchElementException

Single Element

• head == tail when only one element
• Removing single element: both head and tail become null
• Need to update tail when removing last element

Tail Management

• Must update tail when adding to empty list
• Must update tail when removing last element
• removeLast needs to find new tail (O(n))

Traversal

• Always check for null before accessing next
• Can only traverse forward (no prev pointer)
• Keep track of previous node for deletions

When to Use Singly Linked List

Good For

✓ Frequent insertions at beginning
✓ Frequent deletions at beginning
✓ When you don't need random access
✓ Implementing stacks (push/pop at head)
✓ When memory for pointers is acceptable

Not Good For

✗ Random access by index
✗ Searching for elements
✗ Removing from the end (use doubly-linked)
✗ When memory is very constrained
✗ When cache locality matters