Deleting from the Head
You'll learn how to remove the first node from a linked list in constant time.
When you need to remove the first element from a linked list, you're essentially making the second node become the new "first" node. Think of it like removing the front car from a train — you simply detach it and let the next car become the new engine.
The Core Concept
Deleting from the head involves moving your head pointer to point at the second node instead of the first. Here's the process:
- Check if the list is empty (
headisNULL). If so, there's nothing to delete. - Store a pointer to the current head node (so you can free its memory later).
- Move
headtohead->next(the second node becomes the new head). - Deallocate the old head node's memory to prevent memory leaks.
This operation is remarkably efficient because you don't need to traverse the list at all — you're always working with the first node, which you can access immediately through the head pointer.
Why O(1)?
No matter how long your linked list is (10 nodes, 1000 nodes, or a million nodes), deleting the head always takes the same number of steps. You're just:
- Checking one pointer
- Updating one pointer
- Freeing one block of memory
This makes it a constant-time operation: O(1).
Memory Considerations
Don't forget to deallocate! The old head node still occupies memory even after you've moved head to point elsewhere. Failing to free this memory creates a memory leak — lost memory that your program can never use again.
Key Takeaway: Deleting from the head is an O(1) operation that moves head to head->next and requires careful memory deallocation to avoid leaks.