Singly Linked Lists in C

I built a linked list in C from scratch. No helper code. Just pointers and memory work. The project came from my ALX Software Engineering program, and it pushed me into parts of memory I had not explored before.

What I Built

I wrote five functions that manage the full life cycle of a singly linked list.

1. print_list prints every node
2. list_len counts nodes
3. add_node adds a node at the start
4. add_node_end adds a node at the end
5. free_list releases all memory

These functions rely on pointer movement and dynamic allocation. Each one taught me how data travels through the structure.

The Core Concept

A singly linked list is a chain of nodes. Every node stores data and one pointer to the next node. The last node points to nothing.

[Data|Next] -> [Data|Next] -> [Data|Next] -> NULL

Nodes do not sit next to each other in memory. The pointer connects them. This gives freedom when inserting or deleting nodes, but it slows direct access. To reach node 100, you walk through the earlier nodes.

What I Learned

1. Pointers and Double Pointers

A pointer stores an address. A double pointer stores the address of a pointer. Passing a pointer gives a copy of the address. Changing that copy does not affect the caller’s version. To update the caller’s pointer, you pass a double pointer.

void add_node(list_t **head, const char *str)
{
    list_t *new = malloc(sizeof(list_t));
    new->next = *head;
    *head = new;
}

My early code used a single pointer. I added nodes, but the caller never saw them. The list stayed empty. Once I replaced the parameter with a double pointer, everything worked.

2. Traversal Without Losing the Head

To walk through a list, use a temporary pointer. Do not move the head unless you intend to change the list.

Incorrect:

while (head->next)
    head = head->next;

Correct:

list_t *temp = head;
while (temp->next)
    temp = temp->next;

This pattern kept the head safe.

3. Memory Management

Every allocation needs a matching free. In my add function, I used malloc for the node and strdup for the string. Both must be released later.

The free function became a key part of the project.

void free_list(list_t *head)
{
    list_t *temp;
    
    while (head)
    {
        temp = head->next;
        free(head->str);
        free(head);
        head = temp;
    }
}

Saving the next pointer before freeing the node prevents lost memory. If you free first, you lose access to the rest of the chain.

4. Handling Empty Lists

Empty lists caused many early crashes. I learned to check for NULL before dereferencing anything. Adding to an empty list means the new node becomes the head. Freeing an empty list should finish without errors.

5. Insert at End vs Insert at Start

Adding at the start is simple. Create the node. Point it at the old head. Update the head.

Adding at the end takes longer. You must walk to the final node. For an empty list, both operations produce the same result: the new node becomes the head.

Challenges I Faced

The Disappearing List

My first version of add_node_end used a double pointer for traversal. Each step moved the head forward. After a few insertions, the head pointed at the last node. Earlier nodes were gone.

I fixed this by using a single pointer for traversal and keeping the double pointer only where updates were needed.

The Memory Leak

I wrote an early free function that released strings but not nodes. I lost access to earlier nodes as soon as I moved forward. Valgrind showed the leak. Saving the next pointer before freeing fixed it.

The NULL Crash

Calling free on an empty list crashed the program. I had written head->next without checking if head was valid. A small check solved the problem.

Key Takeaways

1. A pointer is a reference. Changing a copy does not update the original.
2. Use a temporary pointer to walk the list.
3. Save what you need before freeing memory.
4. Always test pointers for NULL.
5. Manual memory work needs attention. Mistakes stay hidden until runtime.

Skills Gained

• Dynamic memory allocation
• Pointer and double pointer operations
• Building data structures without libraries
• Debugging memory leaks with Valgrind
• Handling edge cases
• Time cost analysis of each operation

Why This Matters

Linked lists appear in many low-level systems. They help manage dynamic data, handle collisions in hash tables, and store graph neighbors. Working on this project gave me a clear sense of how memory behaves and how small pointer changes affect the entire structure.

Technical Details

Language: C Compiler: gcc with strict flags Testing: Manual tests and Valgrind

Reflections

The hardest part was noticing why my code failed. I could not see the list. I could not print it when the pointers pointed to the wrong place. Once I understood that a pointer holds a memory address and that changing it changes the path to the data, the project made sense.

Repository

https://github.com/zolldic/alx-low_level_programming/tree/main/0x12-singly_linked_lists