LincedList

lincedlist.c

// printf -> print to console
#include <stdio.h>
// malloc -> heap memory allocations
#include <stdlib.h>


// Data of the Linked List
typedef struct NodeData {
    int num;
} NodeData;

// Linked List Node (single direction -> only a next pointer)
typedef struct Node {
    NodeData data;
    struct Node* next;
} Node;


// Create a Linked List Node
Node* createNode(NodeData p) {
    // 1) Allocate memory on the heap of the size of a Node
    Node* newNode = (Node*)malloc(sizeof(Node));
    // 2) Optional: Check if memory was successfully allocated
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    // 3) Copy the data into the heap
    newNode->data = p;
    // 4) Set the pointer to the next node to 0 (end of list)
    newNode->next = NULL;
    return newNode;
}

/**
 * @param head Pointer to the first element of the list (could also be any other values)
 */
void printList(Node* head) {
    // We can change 'head' since the data it holds was copied by value
    // -> thus updating 'head' won't change anything outside this function
    int index = 0;
    while (head != NULL) {
        printf("(%d, {num=%d}) -> ", index++, head->data.num);
        head = head->next;
    }
    printf("NULL\n");
}

/**
 * @param head Pointer to the first element of the list (could also be any other values)
 */
void insert(Node** head, NodeData data) {
    Node* newNode = createNode(data);
    newNode->next = NULL;
    // Case 1: Empty list
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    // Case 2: Traverse to the end
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    //         Insert at the end
    temp->next = newNode;
}

void insertAtIndex(Node** head, NodeData data, int index) {
    Node* newNode = createNode(data);

    // Case 1: Insert at the beginning
    if (index == 0) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    // Case 2: Traverse list to index
    Node* temp = *head;
    int i = 0;

    // Traverse to the node before the desired position
    while (temp != NULL && i < index - 1) {
        temp = temp->next;
        i++;
    }

    // Possible error: Index out of range
    if (temp == NULL) {
        printf("Index out of bounds!\n");
        free(newNode);
        return;
    }

    // Insert the new node
    newNode->next = temp->next;
    temp->next = newNode;
}

void deleteAtIndex(Node** head, int index) {
    Node* temp = *head;
    Node* prev = NULL;
    int tempIndex = 0;

    if (temp != NULL && tempIndex == index) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && tempIndex != index) {
        prev = temp;
        temp = temp->next;
        tempIndex++;
    }

    if (temp == NULL)  {
        printf("Index out of bounds!\n");
        return;
    }

    prev->next = temp->next;
    free(temp);
}

void deleteHeadBad(Node* head) {
    head = head->next; // changes only the local copy
    // 'head' in e.g. main() still points to the old head!
}

void deleteHeadGood(Node** head) {
    Node* temp = *head;          // temp = current head
    *head = (*head)->next;       // change the caller's head
    free(temp);
}


int main() {
    // Create a pointer to a node
    //  ┌────────────────────┐
    //  │  Pointer to Node   │
    //  │  [Memory Address]  │    
    //  │  head              ┼──────┐
    //  └────────────────────┘      │
    //                              ▼
    //                            NULL (Node but currently 0)
    Node* head = NULL;

    for (int i = 0; i < 10; i++) {
        NodeData data = {i};
        // Put the memory address of the pointer into the function
        //  ┌──────────────────────────────┐
        //  |  Pointer to Pointer to Node  │        
        //  │  &head                       ┼──────┐   
        //  └──────────────────────────────┘      │   
        //                                        ▼   
        //                              ┌────────────────────┐
        //                              │  Pointer to Node   │
        //                              │  [Memory Address]  │    
        //                              │  head              ┼──────┐
        //                              └────────────────────┘      │
        //                                                          ▼
        //                                                        NULL (Node but currently 0)
        insert(&head, data);
        // Meaning now it's possible to update the "Pointer to Node" in the function insert
    }

    printf("Linked list: ");
    printList(head);

    deleteAtIndex(&head, 2);
    printf("After deleting 2: ");
    printList(head);

    deleteAtIndex(&head, 10);
    printf("After deleting 10: ");
    printList(head);

    deleteAtIndex(&head, 0);
    printf("After deleting 0: ");
    printList(head);

    {
        NodeData data = {42};
        insertAtIndex(&head, data , 1);
    }
    {
        NodeData data = {91};
        insertAtIndex(&head, data , 0);
    }
    printf("After inserting 42,1 and 91,0: ");
    printList(head);

    deleteAtIndex(&head, 100);
    {
        NodeData data = {-1};
        insertAtIndex(&head, data , 100);
    }

    // Free linked list
    Node* nextNode;
    while (head != NULL) {
        nextNode = head->next;
        free(head);
        head = nextNode;
    }

    return 0;
}

run.sh

#!/usr/bin/env bash

gcc lincedlist.c -o lincedlist
./lincedlist

# Check for memory leaks
valgrind --leak-check=full ./lincedlist