The Singly Linked List

[!NOTE] This module explores the core principles of the Singly Linked List, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

In the previous chapter, we learned that a Linked List is a collection of nodes scattered in memory. Now, let’s build one.

A Singly Linked List is the simplest form. Each node points only to the next node. You can go forward, but never back.

1. The Blueprint

We need two things:

1. Node: Holds data and a pointer.
2. LinkedList Class: Holds the head (start) of the list.

2. Interactive: List Builder

Use this tool to visualize how pointers change during operations.

List is empty. Head → null

Ready.

2. Core Operations

A. Insert at Head (Prepend) - O(1)

This is the fastest operation.

1. Create a new node.
2. Set newNode.next = head.
3. Update head = newNode.

Java

Go

public void addFirst(int val) {
  ListNode newNode = new ListNode(val);
  newNode.next = head;
  head = newNode;
}

func (ll *LinkedList) AddFirst(val int) {
  newNode := &ListNode{Val: val}
  newNode.Next = ll.Head
  ll.Head = newNode
}

B. Insert at Tail (Append) - O(N)

To add to the end, we must find the end first.

1. Start at head.
2. Walk until current.next is null.
3. Set current.next = newNode.

[!TIP] If you maintain a tail pointer, this becomes O(1).

Java

Go

public void addLast(int val) {
  if (head == null) {
    head = new ListNode(val);
    return;
  }
  ListNode current = head;
  while (current.next != null) { // Walk to end
    current = current.next;
  }
  current.next = new ListNode(val);
}

func (ll *LinkedList) AddLast(val int) {
  newNode := &ListNode{Val: val}
  if ll.Head == nil {
    ll.Head = newNode
    return
  }
  current := ll.Head
  for current.Next != nil {
    current = current.Next
  }
  current.Next = newNode
}

C. Delete by Value - O(N)

To delete a node, we must bypass it.

1. Handle edge case: if head is the target, head = head.next.
2. Traverse with current. Check current.next.val.
3. If found, current.next = current.next.next.

Java

Go

public void delete(int val) {
  if (head == null) return;

  // Case 1: Head is target
  if (head.val == val) {
    head = head.next;
    return;
  }

  ListNode current = head;
  while (current.next != null) {
    if (current.next.val == val) {
      current.next = current.next.next; // Bypass
      return;
    }
    current = current.next;
  }
}

func (ll *LinkedList) Delete(val int) {
  if ll.Head == nil {
    return
  }

  // Case 1: Head is target
  if ll.Head.Val == val {
    ll.Head = ll.Head.Next
    return
  }

  current := ll.Head
  for current.Next != nil {
    if current.Next.Val == val {
      current.Next = current.Next.Next // Bypass
      return
    }
    current = current.Next
  }
}

3. Complexity Summary

Operation	Complexity	Why?
Access	O(N)	No index lookup.
Search	O(N)	Must scan nodes.
Insert (Head)	O(1)	Pointer swap.
Insert (Tail)	O(N)	Traversal needed (unless tail ptr exists).
Delete	O(N)	Search time dominates.

In the next chapter, we’ll look at Doubly Linked Lists, which allow us to go backwards.