Linked List Overview

A linked list represents a linear data structure where elements are stored in non-contiguous memory locations. Each element maintains a reference to the next element, creating a sequence through pointer connections rather than physical adjacency. Each node consists of two components: a data field storing the actual value and a link field containing the address of the subsequent node.

Two primary types exist: singly linked lists, where each node points only to its successor, and doubly linked lists, where nodes maintain references to both predecessor and successor nodes.

Core Operations

• Insertion: Adding new nodes at specific positions
• Deletion: Removing existing nodes from the structure
• Search: Locating nodes containing specific values
• Update: Modifying data within existing nodes
• Traversal: Accessing all nodes sequentially

Memory Management

Node Creation

struct ListNode* buildNewNode(DataType value)
{
    struct ListNode* freshNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(freshNode != NULL)
    {
        freshNode->value = value;
        freshNode->pointer = NULL;
    }
    return freshNode;
}

List Initialization

struct LinkedList* initializeList()
{
    struct LinkedList* newList = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    if(newList != NULL)
    {
        newList->start = NULL;
        newList->count = 0;
    }
    return newList;
}

Memory Deallocation

void destroyList(struct LinkedList* targetList)
{
    if(targetList == NULL)
        return;
        
    struct ListNode* walker = targetList->start;
    while(walker != NULL)
    {
        struct ListNode* holder = walker;
        walker = walker->pointer;
        free(holder);
    }
    free(targetList);
}

Operation Implementations

Insertion Logic

void addElementAtPosition(struct LinkedList* container, int position, DataType value)
{
    if(container == NULL || position < 0 || position > container->count)
        return;
        
    struct ListNode* newNode = buildNewNode(value);
    if(newNode == NULL)
        return;
        
    if(position == 0)
    {
        newNode->pointer = container->start;
        container->start = newNode;
    }
    else
    {
        struct ListNode* walker = container->start;
        for(int index = 0; index < position - 1; index++)
        {
            walker = walker->pointer;
        }
        newNode->pointer = walker->pointer;
        walker->pointer = newNode;
    }
    container->count++;
}

Deletion Logic

void removeElementAtPosition(struct LinkedList* container, int position)
{
    if(container == NULL || position < 0 || position >= container->count)
        return;
    
    struct ListNode* victim;
    if(position == 0)
    {
        victim = container->start;
        container->start = container->start->pointer;
    }
    else
    {
        struct ListNode* walker = container->start;
        for(int index = 0; index < position - 1; index++)
        {
            walker = walker->pointer;
        }
        victim = walker->pointer;
        walker->pointer = victim->pointer;
    }
    free(victim);
    container->count--;
}

Update Logic

void modifyElementAtPosition(struct LinkedList* container, int position, DataType newValue)
{
    if(container == NULL || position < 0 || position >= container->count)
        return;
        
    struct ListNode* walker = container->start;
    for(int index = 0; index < position; index++)
    {
        walker = walker->pointer;
    }
    walker->value = newValue;
}

Search Logic

int locateElement(struct LinkedList* container, DataType targetValue)
{
    if(container == NULL)
        return -1;
    
    struct ListNode* walker = container->start;
    int position = 0;
    
    while(walker != NULL)
    {
        if(walker->value == targetValue)
            return position;
        walker = walker->pointer;
        position++;
    }
    return -1;
}

Traversal Logic

void displayList(struct LinkedList* container)
{
    if(container == NULL)
        return;
    
    struct ListNode* walker = container->start;
    while(walker != NULL)
    {
        printf("%d ", walker->value);
        walker = walker->pointer;
    }
    printf("\n");
}

Complete Implementation

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

struct ListNode{
    DataType value;
    struct ListNode* pointer;
};

struct LinkedList{
    struct ListNode* start;
    int count;
};

struct ListNode* buildNewNode(DataType value)
{
    struct ListNode* freshNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(freshNode != NULL)
    {
        freshNode->value = value;
        freshNode->pointer = NULL;
    }
    return freshNode;
}

struct LinkedList* initializeList()
{
    struct LinkedList* newList = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    if(newList != NULL)
    {
        newList->start = NULL;
        newList->count = 0;
    }
    return newList;
}

void addElementAtPosition(struct LinkedList* container, int position, DataType value)
{
    if(container == NULL || position < 0 || position > container->count)
        return;
        
    struct ListNode* newNode = buildNewNode(value);
    if(newNode == NULL)
        return;
        
    if(position == 0)
    {
        newNode->pointer = container->start;
        container->start = newNode;
    }
    else
    {
        struct ListNode* walker = container->start;
        for(int index = 0; index < position - 1; index++)
        {
            walker = walker->pointer;
        }
        newNode->pointer = walker->pointer;
        walker->pointer = newNode;
    }
    container->count++;
}

void removeElementAtPosition(struct LinkedList* container, int position)
{
    if(container == NULL || position < 0 || position >= container->count)
        return;
    
    struct ListNode* victim;
    if(position == 0)
    {
        victim = container->start;
        container->start = container->start->pointer;
    }
    else
    {
        struct ListNode* walker = container->start;
        for(int index = 0; index < position - 1; index++)
        {
            walker = walker->pointer;
        }
        victim = walker->pointer;
        walker->pointer = victim->pointer;
    }
    free(victim);
    container->count--;
}

void modifyElementAtPosition(struct LinkedList* container, int position, DataType newValue)
{
    if(container == NULL || position < 0 || position >= container->count)
        return;
        
    struct ListNode* walker = container->start;
    for(int index = 0; index < position; index++)
    {
        walker = walker->pointer;
    }
    walker->value = newValue;
}

int locateElement(struct LinkedList* container, DataType targetValue)
{
    if(container == NULL)
        return -1;
    
    struct ListNode* walker = container->start;
    int position = 0;
    
    while(walker != NULL)
    {
        if(walker->value == targetValue)
            return position;
        walker = walker->pointer;
        position++;
    }
    return -1;
}

void displayList(struct LinkedList* container)
{
    if(container == NULL)
        return;
    
    struct ListNode* walker = container->start;
    while(walker != NULL)
    {
        printf("%d ", walker->value);
        walker = walker->pointer;
    }
    printf("\n");
}

void destroyList(struct LinkedList* targetList)
{
    if(targetList == NULL)
        return;
        
    struct ListNode* walker = targetList->start;
    while(walker != NULL)
    {
        struct ListNode* holder = walker;
        walker = walker->pointer;
        free(holder);
    }
    free(targetList);
}

int main()
{
    struct LinkedList* myList = initializeList();
    addElementAtPosition(myList, 0, 15);
    addElementAtPosition(myList, 1, 25);
    addElementAtPosition(myList, 2, 35);
    
    displayList(myList);
    
    modifyElementAtPosition(myList, 1, 30);
    
    displayList(myList);
    
    removeElementAtPosition(myList, 2);
    displayList(myList);
    
    int foundPos = locateElement(myList, 35);
    printf("Position: %d\n", foundPos);
    
    destroyList(myList);
    
    return 0;
}