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: 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: 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.

NEW->next = PTR->next
PTR->next = NEW

Example: 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 the first line, 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 the second line, PTR->next is redirected onto NEW, and NEW sits between them: 10 → 20 → 25 → 30 → 40:

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: 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: 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

To delete a node in the middle, both it and the node before it need to be located first.

prev->next = current->next
free(current)

Example: deleting the node holding 20 from 10 → 20 → 30 → 40. Locating the target means walking prev and current 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 with prev holding 10 and current holding 20:

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: 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.