Skip to content

Header Nodes

A header node is a special extra node placed at the beginning of a linked list.

It may:

  • store no actual user data
  • store metadata like count of nodes
  • help simplify insertion and deletion

Simple Picture

1
Header -> [10|*] -> [20|*] -> [30|NULL]

The header is not treated like a normal data node.

Why Use A Header Node?

  • avoids special cases at the beginning of the list
  • can store length information
  • makes algorithms cleaner

Example: Insert At Beginning With Header

Without header:

  • changing the head needs special handling

With header:

1
2
3
4
5
insertFront(header, x):
    newNode = create node
    newNode.data = x
    newNode.next = header.next
    header.next = newNode

Time: O(1)

Example: Delete First Data Node

1
2
3
4
5
6
deleteFront(header):
    if header.next == NULL:
        return
    temp = header.next
    header.next = temp.next
    delete temp

Time: O(1)

Complexity

Header nodes do not change the big-O complexity much.

They mainly make edge cases easier to handle.

Good Use Cases

  • lists with many insert/delete operations
  • implementations where cleaner code matters
  • circular lists with sentinel-style design