Singly Linked List Operations

Every operation on a singly linked list comes down to the same two moves: following next pointers to reach a node, and rewriting next pointers to change what's connected to what. The operations below build on each other, starting with the ones that only read the list, then the ones that change it.

Traversal

Visiting every node means starting at HEAD and following next until a NULL link is reached.

TRAVERSE(HEAD)
 
1. PTR = HEAD
2. While PTR != NULL
       Print PTR->data
       PTR = PTR->next
3. Stop

Example: for the list 10 → 20 → 30, PTR starts at HEAD (the node holding 10).

Each pass through the loop prints the current node's data, then moves PTR one node forward:

Once PTR steps past the last node it becomes NULL, the loop ends, and 10 20 30 has been printed. There's no way to skip ahead, since the only way to reach a node is through the link of the one before it. Traversal is always O(n), since every node must be visited once.

Search

Searching follows the same one-step-at-a-time pattern as traversal, stopping early if the target is found.

SEARCH(HEAD, KEY)
 
1. PTR = HEAD
2. While PTR != NULL
       If PTR->data == KEY
           return FOUND
       PTR = PTR->next
3. return NOT FOUND

Example: searching the list 10 → 20 → 30 for KEY = 20. PTR starts at HEAD, the node holding 10:

PTR->data is 10, which doesn't match KEY, so PTR moves on to the second node:

PTR->data is now 20, which matches KEY, so the search returns FOUND without visiting the third node.

How long this takes depends entirely on where the key happens to be:

• Best case, O(1): the key is sitting right at HEAD. One comparison, done.
• Worst case, O(n): the key is the last node, or isn't in the list at all. Either way, every single node has to be checked before an answer is possible, since a singly linked list has no shortcut to skip ahead.

For a list of n nodes, that means anywhere from 1 comparison up to n comparisons, depending on luck.

Insertion at the beginning

Inserting a new node before the current head only requires the new node to point at the old head, then HEAD to move onto the new node.

INSERT_BEGIN(HEAD, ITEM)
 
1. Create NEW
2. NEW->data = ITEM
3. NEW->next = HEAD
4. HEAD = NEW
5. Return HEAD

Example 1: inserting into an empty list. Inserting 5 when HEAD == NULL. Step 3 sets NEW->next = HEAD, which is NULL, so NEW correctly ends up with no successor. Step 4 moves HEAD onto NEW, and the list goes from empty to a single node:

Nothing about the algorithm needs to change for this case: an empty list is just the special case where HEAD was already NULL before NEW->next copied it.

Example 2: inserting into a non-empty list. Inserting 5 at the beginning of 10 → 20 → 30. Before anything changes, HEAD points at the node holding 10:

Step 1 creates NEW, a node with nothing set yet, both fields holding garbage values. It isn't part of the list, so there's no HEAD pointing at it, only NEW itself:

Step 2 fills in its data field, giving NEW->data = 5. It's still a lone node, disconnected from the rest of the list, since NEW->next hasn't been touched yet and still holds a garbage address, not NULL:

After step 3, NEW->next points at the old head. NEW is still not part of the list yet, since HEAD hasn't moved, but it can now reach every other node through that link:

After step 4, HEAD moves onto NEW, and the list is 5 → 10 → 20 → 30:

Order matters here: NEW->next must be set to the old HEAD before HEAD itself is reassigned, otherwise the old head's address is lost and the rest of the list becomes unreachable. Insertion at the beginning runs in O(1), since no traversal is needed, the new node always attaches right at the front.

Insertion at the end

Without a maintained tail pointer, reaching the end means walking the whole list first.

INSERT_END(HEAD, ITEM)
 
1. Create NEW
2. NEW->data = ITEM
3. NEW->next = NULL
4. If HEAD == NULL
       HEAD = NEW
       return HEAD
5. PTR = HEAD
6. While PTR->next != NULL
       PTR = PTR->next
7. PTR->next = NEW
8. Return HEAD

Example 1: inserting into an empty list. Inserting 40 when HEAD == NULL. Step 4 catches this immediately: HEAD = NEW and the function returns right away, skipping the walk entirely, since there's no existing tail to find:

Example 2: inserting into a non-empty list. Inserting 40 at the end of 10 → 20 → 30. Steps 1-3 build NEW on its own first, not yet part of the list: NEW->data = 40, then NEW->next = NULL explicitly, since this node will end up last:

Step 5 sets PTR = HEAD, so PTR starts at the first node:

Step 6 checks PTR->next != NULL, true here, so PTR steps forward:

The check is true again, so PTR steps forward once more, reaching the current last node, where PTR->next is finally NULL and the loop stops:

Step 7 attaches NEW after PTR, giving 10 → 20 → 30 → 40:

Step 6 stops at the last node, not past it, checking PTR->next != NULL rather than PTR != NULL, so PTR ends up pointing at the current tail, exactly where the new node needs to attach. Insertion at the end costs O(n) without a tail pointer (the whole list must be walked to find the end), or O(1) if a tail pointer is kept up to date, since the last node is already known.

Insertion after a given node

Inserting between two existing nodes only touches the pointers immediately around the insertion point, once the node to insert after, PTR, is known.

INSERT_AFTER(HEAD, PTR, ITEM)
 
1. If PTR == NULL
       Return HEAD
2. Create NEW
3. NEW->data = ITEM
4. NEW->next = PTR->next
5. PTR->next = NEW
6. Return HEAD

Example 1: PTR is NULL. Inserting after a node that wasn't found (PTR == NULL), for instance if a search for the target value came up empty beforehand. Step 1 catches this immediately and returns the list unchanged, since there's no node to attach after.

Example 2: inserting in the middle. Inserting 25 after the node holding 20, in the list 10 → 20 → 30 → 40. NEW has already been created and filled with 25, but is still a lone node, not yet linked to the list:

PTR is the node holding 20, found beforehand:

After step 4, NEW->next points at PTR->next (the node holding 30), so NEW is already wired into the chain even though PTR doesn't point at it yet:

After step 5, PTR->next is redirected onto NEW, and NEW sits between them: 10 → 20 → 25 → 30 → 40:

Example 3: inserting after the tail node. Inserting 50 after the node holding 40, the last node in 10 → 20 → 40. PTR->next is NULL here, since PTR is the tail:

Step 4 sets NEW->next = PTR->next, which is NULL, so NEW correctly becomes the new tail. Step 5 attaches it after PTR, giving 10 → 20 → 40 → 50, the same result as insertion at the end, reached without walking the list first since PTR was already known:

The order matters for the same reason as insertion at the beginning: NEW->next must be set to PTR->next before PTR->next is overwritten, otherwise the link to the rest of the list is lost. Once PTR (the node to insert after) is known, inserting after it is O(1); finding PTR in the first place can take O(n).

Deletion at the beginning

Removing the first node just means moving HEAD forward by one link.

DELETE_BEGIN(HEAD)
 
1. If HEAD == NULL
       Return HEAD
2. TEMP = HEAD
3. HEAD = HEAD->next
4. free(TEMP)
5. Return HEAD

Example 1: empty list. Deleting from an empty list, HEAD == NULL. Step 1 catches this immediately and returns without touching anything, since there's no node to remove.

Example 2: non-empty list. Deleting the first node from 10 → 20 → 30. Before anything changes, HEAD points at the node holding 10:

After step 2, TEMP marks the node about to be removed, before HEAD moves:

After step 3, HEAD has moved to the second node, but the nodes themselves haven't changed: node 10 still physically links to node 20, and TEMP still points at it, not yet freed:

Step 4 frees TEMP, releasing that node's memory. The old head is gone, and the list is 20 → 30:

TEMP had to be saved before HEAD moved, since once HEAD pointed elsewhere there would be no way left to reach the old head node and free it. Deletion at the beginning is O(1), since no traversal is needed, the node to remove is always the current head.

Deletion at the end

Deleting the last node needs the node before it, since that's the one whose next pointer must become NULL. Since a singly linked list has no way to move backward, reaching that node means walking the whole list from HEAD.

DELETE_END(HEAD)
 
1. If HEAD == NULL
       Return HEAD
2. If HEAD->next == NULL
       TEMP = HEAD
       HEAD = NULL
       free(TEMP)
       Return HEAD
3. PREV = HEAD
4. While PREV->next->next != NULL
       PREV = PREV->next
5. LAST = PREV->next
6. PREV->next = NULL
7. free(LAST)
8. Return HEAD

Example 1: empty list. Deleting from an empty list, HEAD == NULL. Step 1 catches this immediately and returns without touching anything.

Example 2: single-node list. Deleting the only node from a list holding just 10. Step 2 catches HEAD->next == NULL: TEMP marks the node, HEAD is set to NULL directly (no need to walk to find the node before it, since there isn't one), then TEMP is freed, leaving the list empty.

Example 3: multi-node list. Deleting the last node from 10 → 20 → 30. Step 3 sets PREV = HEAD, so PREV starts at the first node:

Step 4 checks PREV->next->next != NULL. Here PREV->next is the node holding 20, and its next is the node holding 30, not NULL, so PREV steps forward:

Now PREV->next->next is NULL (the node holding 30 is the last one), so the loop stops. Step 5 sets LAST = PREV->next, the node about to be removed:

Step 6 sets PREV->next = NULL. The list is now 10 → 20, but LAST still holds the detached node 30, not yet freed:

Step 7 frees LAST, releasing that node's memory, leaving the list 10 → 20:

PREV->next must be cut before LAST is freed, otherwise the list would still point at freed memory. Deletion at the end is O(n) for a basic singly linked list, since finding the node before the last one means walking from HEAD, even though the pointer update itself is a single step.

Deleting a specific node

Deleting by value means finding the node holding KEY first, since a singly linked list has no way to jump straight to it. The node before the match also has to be tracked, since that's the one whose next pointer needs to change.

DELETE_NODE(HEAD, KEY)
 
1. If HEAD == NULL
       Return HEAD
2. If HEAD->data == KEY
       TEMP = HEAD
       HEAD = HEAD->next
       free(TEMP)
       Return HEAD
3. PREV = HEAD
4. CURRENT = HEAD->next
5. While CURRENT != NULL and CURRENT->data != KEY
       PREV = CURRENT
       CURRENT = CURRENT->next
6. If CURRENT == NULL
       Return HEAD
7. PREV->next = CURRENT->next
8. free(CURRENT)
9. Return HEAD

Example 1: empty list. Deleting anything from an empty list. Step 1 catches HEAD == NULL immediately and returns without touching anything, since there's no node to remove.

Example 2: deleting the head node. Deleting 10 from 10 → 20 → 30. HEAD->data matches KEY right away, so step 2 handles it the same way as deletion at the beginning, no walk needed:

HEAD moves to the second node and TEMP is freed, leaving 20 → 30:

Example 3: deleting a middle node. Deleting 20 from 10 → 20 → 30 → 40. Step 2 doesn't match (HEAD->data is 10), so PREV and CURRENT walk together from HEAD, one link at a time, until CURRENT->data matches. They start at the first two nodes:

CURRENT->data is 20, the match, so the walk stops:

PREV->next is redirected to skip over CURRENT straight to the node holding 30, then CURRENT is freed, leaving 10 → 30 → 40:

Finding the largest element

Scanning every node once and keeping track of the maximum value seen so far finds the largest element in a single pass.

LARGEST(HEAD)
 
1. If HEAD == NULL
       Print "List is empty"
       Stop
2. MAX = HEAD->data
3. PTR = HEAD->next
4. While PTR != NULL
       If PTR->data > MAX
           MAX = PTR->data
       PTR = PTR->next
5. Return MAX

Example 1: empty list. Finding the largest value in an empty list, HEAD == NULL. Step 1 catches this immediately, prints "List is empty", and stops, since there's no value to return.

Example 2: non-empty list. Finding the largest value in 10 → 30 → 20. Before the loop starts, MAX is set to 10 (the first node's value):

PTR starts at the second node:

PTR->data is 30, greater than MAX, so MAX becomes 30. PTR then moves to the last node:

PTR->data is 20, not greater than MAX, so MAX stays 30. PTR becomes NULL, the loop ends, and LARGEST returns 30.

MAX starts at the first node's value rather than some arbitrary sentinel, so the algorithm works correctly even if every value in the list happens to be negative. Finding the largest element is O(n) time (every node is visited once) and O(1) space (only MAX and PTR are kept, regardless of list length).

Operation summary

Quick recall

• Traversal and search both move one link at a time from HEAD; search stops early on a match, traversal doesn't.
• Insertion always sets the new node's own next pointer before touching the pointer that will connect it to the list, otherwise a link gets overwritten before it's saved.
• Insert/delete at the beginning are O(1); insert/delete at the end or at an arbitrary node are O(n), since a singly linked list has no way to reach them except by walking from HEAD.
• Deleting a node needs a reference to the node before it, since that's the pointer that must be redirected.
• Finding the largest element is a single O(n) pass that tracks a running maximum, starting from the first node's own value.