Skip to main content

​
Overview

This implementation extends singly linked lists with advanced operations like insertion at index, deletion, and stack-like operations. Unlike the basic implementation, this version stores integers instead of strings.

​
Data Structure Definition

The integer-based singly linked list is defined in lists.h:14-18:
lists.h
typedef struct listint_s
{
    int n;
    struct listint_s *next;
} listint_t;
This simpler structure stores only:
  • n: The integer value
  • next: Pointer to the next node
No length tracking needed since we’re storing primitive integers, not strings.

​
Basic Operations

​
Adding Nodes

add_nodeint.c
/**
 * *add_nodeint - adds a new node at the beginning of a listint_t list
 * @head: pointer to the head of the list
 * @n: integer to be added
 * Return: address of the new element, or NULL if it failed
 */
listint_t *add_nodeint(listint_t **head, const int n)
{
    listint_t *new_node;

    new_node = malloc(sizeof(listint_t));
    if (new_node == NULL)
        return (NULL);
    new_node->n = n;
    new_node->next = *head;
    *head = new_node;
    return (new_node);
}
Time Complexity: O(1) - constant time insertion
Space Complexity: O(1) - single node allocation

​
Advanced Operations

​
Stack Operations: Pop

pop_listint.c
/**
 * pop_listint - deletes the head node of a listint_t linked list
 * @head: pointer to the head of the list
 * Return: the head node's data (n)
 */
int pop_listint(listint_t **head)
{
    listint_t *temp;
    int n;

    if (*head == NULL)
        return (0);

    temp = *head;
    n = temp->n;
    *head = (*head)->next;
    free(temp);
    return (n);
}
This implements stack-like LIFO (Last In, First Out) behavior:
  1. Save the value from the head node
  2. Update head to point to next node
  3. Free the old head
  4. Return the saved value
Time Complexity: O(1)

​
Indexed Access

get_nodeint_at_index.c
/**
 * *get_nodeint_at_index - returns the nth node of a listint_t linked list.
 * @head: pointer to the first node of the list
 * @index: index of the node to return
 * Return: the nth node of a listint_t linked list.
 */
listint_t *get_nodeint_at_index(listint_t *head, unsigned int index)
{
    unsigned int i;

    if (head == NULL)
        return (NULL);

    for (i = 0; i < index; i++)
    {
        if (head->next == NULL)
            return (NULL);
        head = head->next;
    }
    return (head);
}
Time Complexity: O(n) - worst case traverses entire list
Space Complexity: O(1) - only index counter

​
Insertion at Index

insert_nodeint_at_index.c
/**
 * insert_nodeint_at_index - inserts a new node at a given position
 * @head: pointer to the first node of the list
 * @idx: index of the list where the new node should be added
 * @n: data to be added
 * Return: the address of the new node, or NULL if it failed
 */
listint_t *insert_nodeint_at_index(listint_t **head, unsigned int idx, int n)
{
    listint_t *new_node, *temp;
    unsigned int i;

    if (head == NULL)
        return (NULL);

    new_node = malloc(sizeof(listint_t));
    if (new_node == NULL)
        return (NULL);

    new_node->n = n;

    if (idx == 0)
    {
        new_node->next = *head;
        *head = new_node;
        return (new_node);
    }

    temp = *head;
    for (i = 0; i < idx - 1; i++)
    {
        if (temp->next == NULL)
            return (NULL);
        temp = temp->next;
    }
    new_node->next = temp->next;
    temp->next = new_node;
    return (new_node);
}

​
Deletion at Index

delete_nodeint_at_index.c
/**
 * delete_nodeint_at_index - deletes node at index
 * @head: head of list
 * @index: index of node to delete
 * Return: 1 if success, -1 if failure
 */
int delete_nodeint_at_index(listint_t **head, unsigned int index)
{
    listint_t *temp;
    unsigned int i;

    if (*head == NULL)
        return (-1);

    if (index == 0)
    {
        *head = (*head)->next;
        free(*head);
        return (1);
    }

    temp = *head;
    for (i = 0; i < index - 1; i++)
    {
        if (temp->next == NULL)
            return (-1);
        temp = temp->next;
    }
    temp->next = temp->next->next;
    free(temp->next);
    return (1);
}
Return Values:
  • 1: Successfully deleted node
  • -1: Failed (invalid index or empty list)
Edge Cases Handled:
  • Empty list (*head == NULL)
  • Delete first node (index == 0)
  • Index out of bounds (traversal reaches NULL)

​
Complete Function Set

From lists.h:20-30, the full API includes:
lists.h
size_t print_listint(const listint_t *h);
size_t listint_len(const listint_t *h);
listint_t *add_nodeint(listint_t **head, const int n);
listint_t *add_nodeint_end(listint_t **head, const int n);
void free_listint(listint_t *head);
void free_listint2(listint_t **head);
int pop_listint(listint_t **head);
listint_t *get_nodeint_at_index(listint_t *head, unsigned int index);
int sum_listint(listint_t *head);
listint_t *insert_nodeint_at_index(listint_t **head, unsigned int idx, int n);
int delete_nodeint_at_index(listint_t **head, unsigned int index);

​
Usage Example

example.c
#include "lists.h"

int main(void)
{
    listint_t *head = NULL;
    
    /* Build list: 3 -> 2 -> 1 -> NULL */
    add_nodeint(&head, 1);
    add_nodeint(&head, 2);
    add_nodeint(&head, 3);
    
    /* Insert at index 1: 3 -> 5 -> 2 -> 1 -> NULL */
    insert_nodeint_at_index(&head, 1, 5);
    
    /* Get node at index 2 */
    listint_t *node = get_nodeint_at_index(head, 2);
    printf("Node at index 2: %d\n", node->n);  // Output: 2
    
    /* Pop (removes and returns head) */
    int val = pop_listint(&head);  // val = 3, list: 5 -> 2 -> 1
    
    /* Delete at index 1: 5 -> 1 -> NULL */
    delete_nodeint_at_index(&head, 1);
    
    /* Cleanup */
    free_listint(head);
    
    return (0);
}

​
Complexity Summary

OperationTimeSpaceNotes
add_nodeintO(1)O(1)Insert at head
add_nodeint_endO(n)O(1)Must traverse to end
pop_listintO(1)O(1)Remove from head
get_nodeint_at_indexO(n)O(1)Linear search
insert_nodeint_at_indexO(n)O(1)Traverse to position
delete_nodeint_at_indexO(n)O(1)Traverse to position
sum_listintO(n)O(1)Must visit all nodes

​
Key Improvements Over Basic Lists

  1. Index-based operations: Direct access to nodes by position
  2. Stack operations: Efficient push/pop for LIFO behavior
  3. In-place modification: Delete and insert without rebuilding list
  4. Simpler memory model: Integers don’t require separate allocation like strings

Build docs developers (and LLMs) love

Get started for freeTalk to us