Difficulty: Beginner–Intermediate | Prerequisites: Part 1 (Linked Lists – Concepts, Types, and Definitions), comfort with C pointers, malloc/free.
Knowing what a linked list is matters less than knowing how to work with one. This set of notes covers the core operations: traversal, search, insertion, deletion, and counting. These operations recur in every pointer-based data structure you will encounter later (trees, graphs, hash table chaining), so learning the patterns here pays off well beyond this unit. Every operation boils down to walking pointers and redirecting them.
Linked list operations follow a common rhythm: start at the head, walk node-by-node using ptr = ptr->next, and do something at each step. Insertion and deletion are about rewiring pointers in the right order so you do not lose part of the list. Always remember to free removed nodes and to handle the empty-list edge case.
Traversal
Walking through every node in the list from head to NULL, doing something with each node's data along the way. Think of it as reading every bead on a string, one by one.
Search (linear search)
A traversal where you compare each node's data to a target value and stop when you find a match or reach NULL. In simple terms, you are checking every box in the chain until you find what you want.
Insertion at the head (prepend)
Adding a new node at the front of the list. The new node's next points to the old head, then the head pointer is updated. This is O(1).
Insertion at the tail (append)
Adding a new node at the end of the list. Without a tail pointer, you must traverse to the last node first, making it O(n). With a tail pointer, it is O(1).
Deletion
Removing a node by redirecting the previous node's next pointer to skip over it, then calling free on the removed node. In simple terms, you unlink one bead from the string and throw it away.
Traversal is the most fundamental operation. Every other operation (search, size, print) is built on top of it.
void traverseList(LLNode *head) {
LLNode *ptr = head;
while (ptr != NULL) {
// Process ptr->data here
ptr = ptr->next;
}
}
Start a temporary pointer ptr at the head.
Loop while ptr is not NULL.
Advance ptr to the next node each iteration.
Never modify head directly during traversal; use the temporary pointer.
Search is a traversal with a conditional return:
LLNode* searchList(LLNode *head, int query) {
LLNode *ptr = head;
while (ptr != NULL) {
if (ptr->data == query) {
return ptr; // Found it
}
ptr = ptr->next;
}
return NULL; // Not in the list
}
Returns a pointer to the matching node, or NULL if the value is not present.
Time complexity is O(n) in the worst case (the value is at the end or absent).
This is linear search; linked lists do not support binary search because there is no random access.
The fastest insertion. Three steps, all O(1):
void insertAtBeginning(LList *list, int newData) {
LLNode *newNode = (LLNode*) malloc(sizeof(LLNode));
newNode->data = newData;
newNode->next = list->head;
list->head = newNode;
}
Allocate a new node with malloc.
Set the new node's next to the current head (so it points to the existing chain).
Update list->head to point to the new node.
Order matters: if you update head before setting newNode->next, you lose the rest of the list.
Requires traversal to the last node unless you maintain a tail pointer:
void insertAtEnd(LList *list, int newData) {
LLNode *newNode = (LLNode*) malloc(sizeof(LLNode));
newNode->data = newData;
newNode->next = NULL;
if (list->head == NULL) {
list->head = newNode;
return;
}
LLNode *ptr = list->head;
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = newNode;
}
Handle the empty list case first: if head is NULL, the new node becomes the head.
Otherwise, walk to the last node (the one whose next is NULL) and attach the new node there.
Time complexity is O(n) because of the traversal; a tail pointer would make it O(1).
Deletion requires tracking both the current node and the previous node so you can redirect the previous node's pointer:
void removeElement(LList *list, int value) {
LLNode *ptr = list->head;
LLNode *prev = NULL;
while (ptr != NULL && ptr->data != value) {
prev = ptr;
ptr = ptr->next;
}
if (ptr == NULL) {
return; // Value not found
}
if (prev == NULL) {
list->head = ptr->next; // Removing the head node
} else {
prev->next = ptr->next; // Bypass the node
}
free(ptr); // Release the memory
}
Two pointers walk in tandem: prev trails one step behind ptr.
If ptr reaches NULL, the value is not in the list; do nothing.
If prev is NULL when the match is found, the match is the head node, so update list->head.
Otherwise, link prev->next around the matched node.
Always call free on the removed node. Forgetting this causes a memory leak.
A straightforward traversal with a counter:
int listSize(LLNode *head) {
int count = 0;
LLNode *ptr = head;
while (ptr != NULL) {
count++;
ptr = ptr->next;
}
return count;
}
O(n) every time, because you must visit each node.
Some implementations store the size as a field in the list struct and update it on every insert/delete to make this O(1).
Time complexity summary:
Operation | Singly linked list (no tail pointer) | With tail pointer |
|---|---|---|
Access by index | O(n) | O(n) |
Search | O(n) | O(n) |
Insert at head | O(1) | O(1) |
Insert at tail | O(n) | O(1) |
Delete (known node) | O(n)* | O(n)* |
Size (no stored count) | O(n) | O(n) |
*O(n) for deletion because you must find the predecessor, unless you already have it.
Operating system kernels use linked lists extensively for managing process queues and memory blocks. Hash tables that handle collisions with chaining use a linked list at each bucket. Undo histories in editors are often doubly linked lists so you can step forward and backward through changes.
Students often forget to handle the empty-list edge case in insertion and deletion. If head is NULL and you try to dereference it, you get a segfault.
Students sometimes update the head pointer before linking the new node's next, which severs the existing list. Always set newNode->next first, then move head.
Students frequently forget to call free after removing a node. The node is unlinked from the list but the memory is still allocated; this is a memory leak.
Students often confuse deletion of the head node with deletion of a middle node. Head deletion requires updating list->head; middle deletion requires updating prev->next. The code must branch on whether prev is NULL.
⚠️ Be ready to write insertion and deletion functions from scratch, including the empty-list and head-node edge cases.
⚠️ Expect tracing questions: given a sequence of insertions and deletions, draw or describe the resulting list state.
⚠️ Know the time complexities for each operation and be able to explain why (e.g. "insert at tail is O(n) because we traverse to find the last node").
⚠️ Memory management questions are common: what happens if you forget free? What happens if you free a node but another pointer still references it (dangling pointer)?
True or false: Inserting at the head of a singly linked list is O(n).
A: False. It is O(1) because no traversal is needed.
Fill in the blank: When deleting a node, you must call ______ to release the memory.
A: free.
True or false: In the removeElement function, if prev is NULL when a match is found, the matched node is the head.
A: True.
Fill in the blank: To insert at the end without a tail pointer, you traverse until ptr->______ == NULL.
A: next.
Q: Why does insertAtBeginning set newNode->next = list->head before list->head = newNode, rather than the other way round?
A: If you update list->head first, you lose the pointer to the rest of the list. The new node's next must grab the old head before the head pointer moves.
Q: What is the time complexity of insertAtEnd without a tail pointer, and how does a tail pointer change it?
A: Without a tail pointer, it is O(n) because you traverse the entire list to find the last node. A tail pointer gives you direct access to the last node, making the operation O(1).
Q: In removeElement, what happens if the value you are trying to remove is not in the list?
A: The while loop runs until ptr is NULL without finding a match. The function then hits the if (ptr == NULL) return; guard and exits without modifying the list.
Q: What is a dangling pointer, and how can deletion in a linked list create one?
A: A dangling pointer is a pointer that still references memory that has been freed. If another part of your code holds a pointer to a node that has been removed and freed, that pointer is now dangling. Dereferencing it is undefined behaviour.
Q: Why is linear search the only search option for a standard linked list?
A: Binary search requires random access (jumping to the middle element), which linked lists cannot do. You must walk from the head, making only sequential (linear) search possible.
These operations are the building blocks for stack and queue implementations: a stack uses insertAtBeginning and removes from the head; a queue uses insertAtEnd and removes from the head (or uses head and tail pointers for O(1) on both ends). Tree traversal algorithms extend the same pointer-following logic to nodes with two or more children instead of one next pointer.
linked list traversal, linked list search, insert at head, insert at tail, prepend, append, delete node, remove element, free memory, memory leak, dangling pointer, malloc, linked list size, time complexity linked list, O(1) insertion, O(n) traversal, COP 3223, Computer Science I, UCF, data structures in C, pointer manipulation