Skip to main content

​
Overview

A singly linked list is a linear data structure where each element (node) contains data and a pointer to the next node in the sequence. This implementation stores strings with their lengths.

​
Data Structure Definition

The singly linked list node is defined in lists.h:16-21:
lists.h
typedef struct list_s
{
    char *str;
    unsigned int len;
    struct list_s *next;
} list_t;
Each node contains:
  • str: A dynamically allocated string (must be freed)
  • len: The length of the string
  • next: Pointer to the next node (NULL if last node)

​
Core Operations

​
Traversal and Counting

/**
 * print_list - print all elements of a list_t
 * @h: nodes
 * Return: number of nodes
 */
size_t print_list(const list_t *h)
{
    size_t nodes;
    nodes = 0;

    while (h != NULL)
    {
        if (h->str == NULL)
            printf("[%d] %s\n", 0, "(nil)");
        else
            printf("[%d] %s\n", h->len, h->str);
        h = h->next;
        nodes++;
    }
    return (nodes);
}
Time Complexity: O(n) - must traverse entire list
Space Complexity: O(1) - only counter variable needed

​
Insertion Operations

/**
 * add_node - adds a new node at the beginning
 * @head: head of linked list
 * @str: str to store
 * Return: address of the new element, or NULL if fail
 */
list_t *add_node(list_t **head, const char *str)
{
    list_t *newlist;
    size_t c;

    newlist = malloc(sizeof(list_t));
    if (newlist == NULL)
        return (NULL);

    newlist->str = strdup(str);

    for (c = 0; str[c]; c++)
        ;

    newlist->len = c;
    newlist->next = *head;
    *head = newlist;

    return (*head);
}
Performance Comparison:
  • add_node(): O(1) - inserts at beginning
  • add_node_end(): O(n) - must traverse to end
For frequent insertions, prepending is more efficient.

​
Memory Management

free_list.c
/**
 * free_list - frees a list_t list
 * @head: head of linked list
 */
void free_list(list_t *head)
{
    list_t *current;
    list_t *next;

    current = head;

    while (current != NULL)
    {
        next = current->next;
        free(current->str);
        free(current);
        current = next;
    }
}
Important: Always free the string (str) before freeing the node itself to avoid memory leaks. Each node requires two free() calls.

​
Usage Example

example.c
#include "lists.h"

int main(void)
{
    list_t *head = NULL;
    
    /* Add nodes */
    add_node(&head, "Hello");
    add_node(&head, "World");
    add_node_end(&head, "!");
    
    /* Print list */
    printf("List has %lu elements:\n", print_list(head));
    
    /* Output:
     * [5] World
     * [5] Hello
     * [1] !
     * List has 3 elements:
     */
    
    /* Cleanup */
    free_list(head);
    
    return (0);
}

​
Complexity Summary

OperationTime ComplexitySpace Complexity
Insert at beginningO(1)O(1)
Insert at endO(n)O(1)
Traverse/PrintO(n)O(1)
SearchO(n)O(1)
DeleteO(n)O(1)

​
Key Characteristics

  • Unidirectional: Can only traverse forward
  • Dynamic size: Grows and shrinks as needed
  • No random access: Must traverse from head to reach any element
  • Memory efficient: Only stores pointer to next node
  • String management: Uses strdup() for string duplication and requires explicit freeing

Build docs developers (and LLMs) love

Get started for freeTalk to us