Singly Linked Lists

CS205 Data Structures

Use arrow keys or buttons to navigate • Interactive slides ahead!

1 / 21

What is a Linked List?

A linked list is a linear data structure where each element (called a node) contains data and a reference (pointer) to the next node.

Analogy: Treasure Hunt

Each clue tells you where to find the next clue. You can only follow the chain forward — you cannot jump directly to clue #5.

Analogy: Train Cars

Each car (node) carries cargo (data) and is coupled to the next car (next pointer). The engine is the head. The last car points to null.

Key Idea

Unlike arrays, linked list nodes do NOT need to be stored contiguously in memory. They can be scattered anywhere — the pointers connect them into a logical sequence.

2 / 21

Array vs. Linked List

Array: Contiguous Memory

Linked List: Scattered Memory

Operation	Array	Linked List	Winner
Access by index	O(1)	O(n)	Array
Insert at front	O(n)	O(1)	Linked List
Insert at end	O(1)*	O(n)	Array
Insert at middle	O(n)	O(n)	Tie
Delete at front	O(n)	O(1)	Linked List
Search	O(n)	O(n)	Tie
Memory overhead	Low	Higher (ptrs)	Array

* Amortized O(1) for dynamic arrays. Worst case O(n) when resizing.

3 / 21

The Node Class

Every linked list is built from Node objects. Each node stores data and a reference to the next node.

Java Implementation

public class Node {
    int data;       // the value stored
    Node next;      // pointer to next node

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

The next field is itself a Node reference — this creates the chain. When next is null, we've reached the end.

Anatomy of a Single Node

Key Idea

A Node is a self-referential structure: it contains a reference to another object of its own type. This is the fundamental building block for all linked structures.

4 / 21

Singly Linked List Structure

A singly linked list has: a head pointer, one-way traversal, and a null terminator.

Java Wrapper Class

public class SinglyLinkedList {
    private Node head;  // entry point
    private int size;   // # of elements

    public SinglyLinkedList() {
        this.head = null;
        this.size = 0;
    }
}

Three Things to Remember

head — the only entry point into the list. Lose it and you lose everything.
Singly linked — each node only knows about the next node.
null terminator — the last node's next is null.

5 / 21

Creating a Linked List (Step by Step)

Build the list 10 → 20 → 30 from scratch. Click through each step.

Step 0 / 3 — Click Next

// Click "Next Step" to begin building the list

Warning: Never Lose the Head!

If you accidentally reassign head without saving the old reference, all nodes become unreachable.

6 / 21

Traversal

Walking through every node using a temporary current pointer.

Java Code

public void printList() {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " → ");
        current = current.next;
    }
    System.out.println("null");
}

Key Idea

Use a temporary pointer so we don't modify head.

Step-by-Step

Click "Start Traversal" to watch current walk through the list.

7 / 21

Insert at Head — O(1)

The fastest insertion: add a new node at the front.

Insert value 5 at head — Click Next

public void insertAtHead(int data) {
    Node newNode = new Node(data);
    newNode.next = head;  // link first!
    head = newNode;       // then move head
    size++;
}

Order Matters!

WRONG: head = newNode first → self-loop, list lost!

RIGHT: Link first, then move head.

8 / 21

Insert at Tail — O(n)

Must traverse the entire list to find the last node before appending.

Insert 40 at tail — Click Next

public void insertAtTail(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
    } else {
        Node current = head;
        while (current.next != null)
            current = current.next;
        current.next = newNode;
    }
    size++;
}

Why O(n)?

No direct reference to the tail, so we walk all n nodes. A tail pointer makes this O(1).

9 / 21

Insert at Position — O(n)

Insert at index k by finding the node at k-1 and rewiring pointers.

Insert 25 at index 2 — Click Next

public void insertAt(int index, int data) {
    if (index == 0) { insertAtHead(data); return; }
    Node newNode = new Node(data);
    Node prev = head;
    for (int i = 0; i < index - 1; i++)
        prev = prev.next;
    newNode.next = prev.next;  // link first!
    prev.next = newNode;       // then rewire
    size++;
}

Order of Assignments

WRONG: prev.next = newNode first — breaks the chain!

RIGHT: Set newNode.next FIRST, THEN prev.next.

10 / 21

Delete from Head — O(1)

Remove the first node by advancing the head pointer.

Delete head node — Click Next

public int deleteFromHead() {
    if (head == null)
        throw new NoSuchElementException();
    int data = head.data;
    head = head.next;
    size--;
    return data;
}

Memory Management

Java / Python: Garbage collector frees the orphaned node.
C / C++: You must manually free() the removed node.

11 / 21

Delete from Tail — O(n)

Find the second-to-last node, set its next to null.

Delete tail node — Click Next

public int deleteFromTail() {
    if (head == null) throw new NoSuchElementException();
    if (head.next == null) {
        int data = head.data; head = null; size--; return data;
    }
    Node current = head;
    while (current.next.next != null)
        current = current.next;
    int data = current.next.data;
    current.next = null;
    size--;
    return data;
}

Why O(n)?

No backwards pointer. Must traverse from head to second-to-last. A doubly linked list solves this.

12 / 21

Delete by Value — O(n)

Find the node containing value 20 and remove it using two pointers.

Delete value 20 — Click Next

public boolean deleteByValue(int target) {
    if (head == null) return false;
    if (head.data == target) {
        head = head.next; size--; return true;
    }
    Node prev = head;
    Node current = head.next;
    while (current != null) {
        if (current.data == target) {
            prev.next = current.next;
            size--; return true;
        }
        prev = current;
        current = current.next;
    }
    return false;
}

Two-Pointer Technique

We track prev and current because removing a node requires updating the previous node's next. We can't go backwards in a singly linked list.

13 / 21

Search / Contains — O(n)

Linear search to find a value. Try it below!

Java Code

public boolean contains(int target) {
    Node current = head;
    while (current != null) {
        if (current.data == target)
            return true;
        current = current.next;
    }
    return false;
}

No Random Access

Unlike arrays (arr[i] in O(1)), linked lists require walking from the head. Searching is always O(n) worst case.

Interactive Search

Search for:

Enter a value and click Search to animate.

14 / 21

Get Size / Length

Two approaches: traverse and count, or maintain a size variable.

Approach 1: Count by Traversal — O(n)

public int getSize() {
    int count = 0;
    Node current = head;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

Approach 2: Maintain Size Field — O(1)

public class SinglyLinkedList {
    private Node head;
    private int size;   // track it!

    public int getSize() {
        return size;    // O(1)!
    }

    public void insertAtHead(int data) {
        // ... insertion logic ...
        size++;   // increment on insert
    }
}

Best Practice

Always maintain a size field. Increment on insert, decrement on delete → O(1) size queries.

15 / 21

Sentinel / Dummy Head Node

A dummy node at the front eliminates special cases for empty list or head insertion/deletion.

Without Dummy

Must check if (head == null) everywhere. Special case for head operations!

With Dummy

Head is never null. Same logic for all positions. Simpler code!

// With dummy: insert at front — no special case!
public void insertAtFront(int data) {
    Node newNode = new Node(data);
    newNode.next = head.next;
    head.next = newNode;
    size++;
}

Why Use a Sentinel?

head is never null
Front insert/delete = same logic as any position
Trade-off: one extra node of memory

16 / 21

Common Pitfalls

Bugs that trip up nearly every student implementing a linked list for the first time.

1. NullPointerException

Calling current.next when current is null. Always check first!

2. Losing References

3. Off-by-One Errors

Traversing to index k? Stop at k-1 for insertion. < vs <= matters!

4. Forgetting to Update Size

Every insert: size++. Every delete: size--. One miss corrupts everything.

5. Not Handling Edge Cases

Empty list (head == null)
Single-element list
Deleting the head node

17 / 21

Time Complexity Summary

Operation	Singly Linked List	Array (fixed)	ArrayList (dynamic)
Insert at head	O(1)	O(n)	O(n)
Insert at tail	O(n)*	O(1)†	O(1) amortized
Insert at index k	O(k)	O(n)	O(n)
Delete at head	O(1)	O(n)	O(n)
Delete at tail	O(n)	O(1)	O(1)
Delete by value	O(n)	O(n)	O(n)
Access by index	O(n)	O(1)	O(1)
Search	O(n)	O(n)	O(n)
Get size	O(1)‡	O(1)	O(1)

* O(1) with tail pointer † Only if space available ‡ If you maintain a size field

When to Choose a Linked List

Use when you need frequent insertions/deletions at the head, don't need random access, and size is unpredictable. Use an array for fast random access with stable size.

18 / 21

Real-World Applications

Implementing Stacks & Queues

Music Playlist

Undo Functionality

Also Used In...

Operating system process scheduling
Hash table chaining (collision resolution)
Graph adjacency lists
Memory allocation (free lists)

19 / 21

Summary & Cheat Sheet

INSERT AT HEAD:        O(1)
  newNode.next = head;
  head = newNode;

INSERT AT TAIL:        O(n)
  traverse to last node
  last.next = newNode;

DELETE FROM HEAD:      O(1)
  head = head.next;

SEARCH:                O(n)
  traverse, compare each

TRAVERSAL PATTERN:
  Node cur = head;
  while (cur != null) {
      // process cur.data
      cur = cur.next;
  }

Golden Rules

Never lose the head — always use a temporary pointer.
Link before you redirect — set newNode.next before head.
Check for null — before accessing .data or .next.
Handle edge cases — empty list, single element, head deletion.
Maintain size — increment/decrement on every insert/delete.

Train Cars Recap

Engine = head Car = node Coupling = next pointer

Last car → null Insert = couple in Delete = uncouple

Coming Next

Doubly Linked Lists — adding a prev pointer for backward traversal and O(1) tail ops.

20 / 21

Challenge: Fix the Bug!

This insertAtHead has a critical bug. Can you spot it?

Buggy Code

public void insertAtHead(int data) {
    Node newNode = new Node(data);
    head = newNode;       // line 3
    newNode.next = head;  // line 4
    size++;
}

Click the line(s) you think are wrong.

Which line has the bug?

What happens with this code?

Challenge: Predict the State

Starting with list [5, 10, 15, 20, 25], what does the list look like after these operations?

deleteFromHead();
insertAtTail(30);
deleteByValue(15);
insertAtHead(1);

What's the final list?

Pick your answer!

Challenge: What's the Output?

Trace this code carefully. What gets printed?

SinglyLinkedList list = new SinglyLinkedList();
list.insertAtHead(3);
list.insertAtHead(7);
list.insertAtTail(9);
list.insertAtHead(1);
list.deleteFromHead();
list.insertAtTail(5);

System.out.println(list.contains(1));
System.out.println(list.contains(7));
System.out.println(list.getSize());
list.printList();

Your answer:

contains(1):

contains(7):

getSize():

Select your answers, then check!

Trace Visualization

Answer the questions first, then reveal the trace!

Final Challenge: Quick-Fire Quiz

5 questions. How many can you get right?

Final Challenge: Find All the Bugs

This deleteByValue method has 3 bugs. Click on every buggy line!

public boolean deleteByValue(int target) {
    Node prev = null;
    Node current = head;
    while (current != null) {
        if (current.data == target) {
            prev.next = current.next;  // line 6
            return true;
        }
        current = current.next;  // line 9
    }
    return false;
}

0 / 3 bugs found

Click on the 3 buggy lines.

Hint 1

What if the target is at the head of the list? What is prev when current == head?

Hint 2

After finding and removing the node, should we update anything else?

Hint 3

When we DON'T find a match, how do prev and current advance?

Final Challenge: Build the Target List

Using only the buttons below, build this exact list in as few operations as possible:

Target: [42, 7, 15, 99, 3]

Your list is empty. Start building!

Operations used: 0 Par: 5

Interactive Linked List Playground

Build and manipulate a linked list in real time. Try all the operations!

List is empty. Insert some values to get started!

Operation Log

List State

Size: 0
Values: (empty)

21 / 21

Singly Linked Lists

What is a Linked List?

Analogy: Treasure Hunt

Analogy: Train Cars

Key Idea

Array vs. Linked List

Array: Contiguous Memory

Linked List: Scattered Memory

The Node Class

Java Implementation

Anatomy of a Single Node

Key Idea

Singly Linked List Structure

Java Wrapper Class

Three Things to Remember

Creating a Linked List (Step by Step)

Warning: Never Lose the Head!

Traversal

Java Code

Key Idea

Step-by-Step

Insert at Head — O(1)

Order Matters!

Insert at Tail — O(n)

Why O(n)?

Insert at Position — O(n)

Order of Assignments

Delete from Head — O(1)

Memory Management

Delete from Tail — O(n)

Why O(n)?

Delete by Value — O(n)

Two-Pointer Technique

Search / Contains — O(n)

Java Code

No Random Access

Interactive Search

Get Size / Length

Approach 1: Count by Traversal — O(n)

Approach 2: Maintain Size Field — O(1)

Best Practice

Sentinel / Dummy Head Node

Without Dummy

With Dummy

Why Use a Sentinel?

Common Pitfalls

1. NullPointerException

2. Losing References

3. Off-by-One Errors

4. Forgetting to Update Size

5. Not Handling Edge Cases

Time Complexity Summary

When to Choose a Linked List

Real-World Applications

Implementing Stacks & Queues

Music Playlist

Undo Functionality

Also Used In...

Summary & Cheat Sheet

Golden Rules

Train Cars Recap

Coming Next

Challenge: Fix the Bug!

Buggy Code

What happens with this code?

The Fix

Challenge: Predict the State

What's the final list?

Step-by-step trace:

Challenge: What's the Output?

Your answer:

Trace Visualization

Final Challenge: Quick-Fire Quiz

Final Challenge: Find All the Bugs

Hint 1

Hint 2

Hint 3

The 3 Bugs:

Final Challenge: Build the Target List

Interactive Linked List Playground