I extended my linked list knowledge with more complex operations. This was not about building lists anymore. It was about manipulating them, finding nodes, inserting at arbitrary positions, and handling edge cases that crash programs.
This project was part of my ALX Software Engineering program. It took the foundation I built and stress-tested it.
What I Built
Ten functions that go beyond basic linked list operations:
- print_listint - Print all elements
- listint_len - Count nodes
- add_nodeint - Insert at the beginning
- add_nodeint_end - Insert at the end
- free_listint - Free all memory
- free_listint2 - Free and set head to NULL
- pop_listint - Delete head and return its value
- get_nodeint_at_index - Access node by index
- sum_listint - Sum all values in the list
- insert_nodeint_at_index - Insert at any position
- delete_nodeint_at_index - Delete at any position
Plus three advanced functions for handling lists with cycles.
Each function required careful pointer arithmetic and bulletproof edge case handling.
The Core Challenge
This project was not about creating lists. It was about navigating them safely.
Arrays give you direct access. arr[5] gets the sixth element instantly. Linked lists force you to walk. You must traverse five nodes to reach the sixth.
This makes some operations expensive. But it also makes insertion and deletion cheap at certain positions.
The challenge: implement operations that feel like array access but work with a chain of pointers.
What I Learned
1. Index-Based Access is Expensive
Getting node at index n requires walking n steps.
listint_t *get_nodeint_at_index(listint_t *head, unsigned int index)
{
unsigned int i = 0;
while (head && i < index)
{
head = head->next;
i++;
}
return head;
}
This is O(n) time. Arrays do it in O(1).
But if you need to insert or delete at that position, the walk is unavoidable anyway.
2. Insertion Requires the Previous Node
To insert at position 5, you need the node at position 4.
Why? Because you must update its next pointer to point to your new node.
The pattern:
- Walk to index - 1
- Create new node
- Point new node to current->next
- Point current to new node
Special case: inserting at index 0 means updating the head pointer. No previous node exists.
3. Deletion is Similar But Tricky
Deleting at index 5 also requires the node at index 4.
You need to link node 4 to node 6, skipping node 5 entirely. Then free node 5.
The bug I hit: I walked to the node I wanted to delete. Then I tried to free it. But I had no way to update the previous node's pointer.
The fix: stop at index - 1. Save the target node. Update pointers. Then free.
temp = current->next; // Node to delete
current->next = temp->next; // Skip it
free(temp); // Free it
Order matters. If you free first, you lose access to temp->next.
4. NULL Checks Everywhere
Every operation can fail.
- Accessing index 10 in a 5-node list? Return NULL.
- Inserting at index 100 in a 5-node list? Return NULL.
- Deleting from an empty list? Return -1.
I learned to check before dereferencing. Not after.
if (head == NULL || *head == NULL)
return (-1);
This prevents segmentation faults.
5. Off-by-One Errors
My first version of get_nodeint_at_index had this:
while (head)
{
head = head->next;
i++;
if (i == index)
return head;
}
Looks fine. But it is wrong.
I advance the pointer before checking. So when i reaches index, I am already one node ahead.
The fix: check first, then advance.
while (head && i < index)
{
head = head->next;
i++;
}
return head;
Subtle. But critical.
6. Freeing Safely
I wrote a new free function: free_listint2.
It frees the list and sets the head to NULL. This prevents dangling pointers.
void free_listint2(listint_t **head)
{
listint_t *temp;
if (head == NULL)
return;
while (*head)
{
temp = (*head)->next;
free(*head);
*head = temp;
}
*head = NULL;
}
The double pointer lets me modify the caller's head. After this runs, the list is gone and the pointer knows it.
Challenges I Faced
The Insert Bug
My first insert_nodeint_at_index stopped at the wrong node.
I wrote:
while (i < idx)
{
if (i == idx)
break;
tmp = tmp->next;
i++;
}
This checks i == idx inside a loop that runs while i < idx. The condition never triggers.
I realized: the loop condition already handles when to stop. The inner check was redundant and broken.
The fix: remove the inner check. Let the loop condition do its job.
The Delete Crash
My delete function crashed on edge cases.
If the list had 3 nodes and I tried to delete index 5, it walked to the end, then tried to access current->next->next. That is NULL dereferencing.
The fix: check if current->next exists before trying to delete it.
if (p == NULL || p->next == NULL)
return (-1);
Always validate before dereferencing.
The Sum Overflow
I wrote sum_listint to add all values. Simple enough. But what if the sum exceeds INT_MAX?
The project did not specify. I assumed the input would not overflow. But in production code, this is a bug.
I learned: always consider edge cases, even when they are not tested.
Key Takeaways
- Linked lists trade direct access for flexible insertion/deletion.
- Index-based operations are O(n) because you must traverse.
- Insertion and deletion require the previous node, not the target node.
- Check for NULL before every dereference.
- Off-by-one errors are common. Test with small lists.
- Order of operations matters when freeing memory.
Skills Gained
- Pointer arithmetic and traversal logic
- Edge case handling (NULL, empty lists, out-of-bounds)
- Memory safety (avoiding dangling pointers and leaks)
- Algorithm correctness (fixing off-by-one errors)
- Debugging without a debugger (using print statements and reasoning)
Why This Matters
Linked lists are everywhere. File systems use them for free block lists. Operating systems use them for process scheduling. Compilers use them for symbol tables.
But more than that, this project taught me how to think about data structure invariants.
Every operation must maintain the structure. If you break the chain, the list is lost. If you forget to free, memory leaks. If you dereference NULL, the program crashes.
I learned to reason about correctness before writing code.
The Advanced Tasks
I also implemented three advanced functions:
- reverse_listint - Reverse the list in place
- print_listint_safe - Print a list that may contain a cycle
- free_listint_safe - Free a list that may contain a cycle
These required detecting cycles using Floyd's algorithm (the tortoise and hare method).
The core idea: use two pointers. One moves one step at a time. The other moves two steps. If they meet, a cycle exists.
This was mind-bending. But it made sense once I drew it out.
Technical Details
Language: C
Compiler: gcc with -Wall -Werror -Wextra -pedantic -std=gnu89
Testing: Manual test files provided by ALX
Time Spent: ~15 hours (including debugging and documentation)
Reflections
This project was harder than the previous one. Not because the code was longer. Because the logic was subtler.
I spent hours debugging off-by-one errors. I drew diagrams of lists on paper. I traced pointer movements step by step.
Eventually, I realized: every bug was a misunderstanding of what the pointers represented.
When I thought current pointed to the target node but it actually pointed to the previous node, my delete function failed.
When I thought i == index meant "I am at the right node" but I had already advanced past it, my insert function broke.
Precision matters. Not just in code. In reasoning.
Repository
https://github.com/zolldic/alx-low_level_programming/tree/main/0x13-more_singly_linked_lists