Header File Inclusion

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

Data Type Defniition

Using a type alias improves maintainability and simplifies type changes across the codebase:

typedef int ElementDataType;

Node Structure Definition

typedef struct ListNode {
    ElementDataType value;
    struct ListNode* next;
} LinkedListNode;

Core Linked List Functions

1. Printing the List

void PrintLinkedList(LinkedListNode* head) {
    LinkedListNode* current = head;
    while (current) {
        printf("%d -> ", current->value);
        current = current->next;
    }
    printf("NULL\n");
}

2. Node Creation

LinkedListNode* CreateNode(ElementDataType value) {
    LinkedListNode* newNode = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (!newNode) {
        perror("Memory allocation failed!");
        exit(EXIT_FAILURE);
    }
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

3. Append Node at End

void AppendNode(LinkedListNode** headRef, ElementDataType value) {
    assert(headRef);
    LinkedListNode* newNode = CreateNode(value);
    
    if (!*headRef) {
        *headRef = newNode;
        return;
    }
    
    LinkedListNode* tail = *headRef;
    while (tail->next) {
        tail = tail->next;
    }
    tail->next = newNode;
}

4. Insert at Begnining

void InsertAtStart(LinkedListNode** headRef, ElementDataType value) {
    assert(headRef);
    LinkedListNode* newNode = CreateNode(value);
    newNode->next = *headRef;
    *headRef = newNode;
}

5. Remove Last Node

void RemoveLastNode(LinkedListNode** headRef) {
    assert(headRef && *headRef);
    
    if (!(*headRef)->next) {
        free(*headRef);
        *headRef = NULL;
        return;
    }
    
    LinkedListNode* current = *headRef;
    LinkedListNode* prev = NULL;
    
    while (current->next) {
        prev = current;
        current = current->next;
    }
    
    prev->next = NULL;
    free(current);
}

6. Remove First Node

void RemoveFirstNode(LinkedListNode** headRef) {
    assert(headRef && *headRef);
    LinkedListNode* secondNode = (*headRef)->next;
    free(*headRef);
    *headRef = secondNode;
}

7. Search for Value

LinkedListNode* FindValue(LinkedListNode** headRef, ElementDataType target) {
    assert(headRef);
    LinkedListNode* current = *headRef;
    while (current) {
        if (current->value == target) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

8. Insert Before Position

void InsertBefore(LinkedListNode** headRef, LinkedListNode* position, ElementDataType value) {
    assert(headRef && position && *headRef);
    
    if (*headRef == position) {
        InsertAtStart(headRef, value);
        return;
    }
    
    LinkedListNode* current = *headRef;
    while (current && current->next != position) {
        current = current->next;
    }
    
    if (!current) return;
    
    LinkedListNode* newNode = CreateNode(value);
    current->next = newNode;
    newNode->next = position;
}

9. Insert After Posiiton

void InsertAfter(LinkedListNode* position, ElementDataType value) {
    assert(position);
    LinkedListNode* newNode = CreateNode(value);
    newNode->next = position->next;
    position->next = newNode;
}

10. Delete Specific Node

void DeleteNode(LinkedListNode** headRef, LinkedListNode* position) {
    assert(headRef && *headRef && position);
    
    if (*headRef == position) {
        RemoveFirstNode(headRef);
        return;
    }
    
    LinkedListNode* current = *headRef;
    while (current && current->next != position) {
        current = current->next;
    }
    
    if (!current) return;
    
    current->next = position->next;
    free(position);
}

11. Delete Next Node

void DeleteNextNode(LinkedListNode* position) {
    assert(position && position->next);
    LinkedListNode* toDelete = position->next;
    position->next = toDelete->next;
    free(toDelete);
}

12. Destroy Entire List

void DestroyList(LinkedListNode** headRef) {
    assert(headRef && *headRef);
    LinkedListNode* current = *headRef;
    while (current) {
        LinkedListNode* next = current->next;
        free(current);
        current = next;
    }
    *headRef = NULL;
}

Array-Based Linked List Implementations

1. Single-Linked List with Array

#include <stdio.h>
const int MAX_NODES = 100010;

int head;
int valueStore[MAX_NODES];
int nextPointer[MAX_NODES];
int currentIndex;

void InitializeList() {
    head = -1;
    currentIndex = 0;
}

void InsertAtHead(int value) {
    valueStore[currentIndex] = value;
    nextPointer[currentIndex] = head;
    head = currentIndex++;
}

void InsertAfterIndex(int index, int value) {
    valueStore[currentIndex] = value;
    nextPointer[currentIndex] = nextPointer[index];
    nextPointer[index] = currentIndex++;
}

void RemoveAfterIndex(int index) {
    nextPointer[index] = nextPointer[nextPointer[index]];
}

2. Double-Linked List with Array

const int MAX_DOUBLE_NODES = 100010;
int element[MAX_DOUBLE_NODES];
int leftPointer[MAX_DOUBLE_NODES];
int rightPointer[MAX_DOUBLE_NODES];
int doubleIndex;

void InitializeDoubleList() {
    rightPointer[0] = 1;
    leftPointer[1] = 0;
    doubleIndex = 2;
}

void InsertRight(int index, int value) {
    element[doubleIndex] = value;
    rightPointer[doubleIndex] = rightPointer[index];
    leftPointer[doubleIndex] = index;
    leftPointer[rightPointer[index]] = doubleIndex;
    rightPointer[index] = doubleIndex++;
}

void InsertLeft(int index, int value) {
    element[doubleIndex] = value;
    rightPointer[doubleIndex] = index;
    leftPointer[doubleIndex] = leftPointer[index];
    rightPointer[leftPointer[index]] = doubleIndex;
    leftPointer[index] = doubleIndex++;
}

void RemoveNode(int index) {
    rightPointer[leftPointer[index]] = rightPointer[index];
    leftPointer[rightPointer[index]] = leftPointer[index];
}