Introducsion to Singly Linked Lists

A singly linked list can be visualized as a train where each car carries cargo and a link to the next car. Similar, each node in a singly linked list contains data and a pointer to the next node.

The structure of a singly linked list node is defined as:

typedef int SLTDataType;

typedef struct SListNode
{
    int data;
    struct SListNode* next;
}SListNode;

Key characteristics of singly linked lists:

• Physically non-linear storage
• Logically linear arrangement

Core Implementation

Display Function

This function traverses and displays all elements in the list:

void SListPrint(SListNode* head)
{
    SListNode* current = head;
    while (current)
    {
        printf("%d->", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

Node Creation

Helper function to allocate and initialize new nodes:

SListNode* CreateNode(SLTDataType value)
{
    SListNode* node = (SListNode*)malloc(sizeof(SListNode));
    if (node == NULL)
    {
        perror("Memory allocation failed");
        exit(1);
    }
    node->data = value;
    node->next = NULL;
    return node;
}

Insertion Operations

Tail Insertion

void SListAppend(SListNode** headRef, SLTDataType value)
{
    assert(headRef);

    SListNode* newNode = CreateNode(value);

    if (*headRef == NULL)
    {
        *headRef = newNode;
    }
    else
    {
        SListNode* current = *headRef;
        while (current->next)
        {
            current = current->next;
        }
        current->next = newNode;
    }
}

Head Insertion

void SListPrepend(SListNode** headRef, SLTDataType value)
{
    assert(headRef);

    SListNode* newNode = CreateNode(value);
    newNode->next = *headRef;
    *headRef = newNode;
}

Deletion Operations

Tail Deletion

void SListRemoveTail(SListNode** headRef)
{
    assert(headRef && *headRef);

    if ((*headRef)->next == NULL)
    {
        free(*headRef);
        *headRef = NULL;
    }
    else
    {
        SListNode* current = *headRef;
        SListNode* previous = *headRef;

        while (current->next)
        {
            previous = current;
            current = current->next;
        }
        free(current);
        previous->next = NULL;
    }
}

Head Deletion

void SListRemoveHead(SListNode** headRef)
{
    assert(headRef && *headRef);

    SListNode* nextNode = (*headRef)->next;
    free(*headRef);
    *headRef = nextNode;
}

Search Functionality

SListNode* SListSearch(SListNode* head, SLTDataType target)
{
    SListNode* current = head;
    while (current)
    {
        if (current->data == target)
        {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

Position-Based Operations

Delete Specific Node

void SListRemoveNode(SListNode** headRef, SListNode* target)
{
    assert(headRef && *headRef);
    assert(target);

    if (target == *headRef)
    {
        SListRemoveHead(headRef);
    }
    else
    {
        SListNode* current = *headRef;
        while (current->next != target)
        {
            current = current->next;
        }
        current->next = target->next;
        free(target);
    }
}

Delete Node After Position

void SListRemoveAfter(SListNode* position)
{
    assert(position && position->next);
    SListNode* nodeToRemove = position->next;
    position->next = nodeToRemove->next;
    free(nodeToRemove);
}

Insert Before Position

void SListInsertBefore(SListNode** headRef, SListNode* position, SLTDataType value)
{
    assert(headRef && *headRef);
    assert(position);

    if (*headRef == position)
    {
        SListPrepend(headRef, value);
    }
    else
    {
        SListNode* newNode = CreateNode(value);
        SListNode* current = *headRef;
        while (current->next != position)
        {
            current = current->next;
        }
        newNode->next = position;
        current->next = newNode;
    }
}

Insert After Position

void SListInsertAfter(SListNode* position, SLTDataType value)
{
    assert(position);

    SListNode* newNode = CreateNode(value);
    SListNode* nextNode = position->next;
    position->next = newNode;
    newNode->next = nextNode;
}

List Destruction

void SListDestroy(SListNode** headRef)
{
    SListNode* current = *headRef;
    while (current)
    {
        SListNode* next = current->next;
        free(current);
        current = next;
    }
    *headRef = NULL;
}

Interface Header

#pragma once

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

typedef int SLTDataType;

typedef struct SListNode
{
    int data;
    struct SListNode* next;
}SListNode;

void SListPrint(SListNode* head);
void SListAppend(SListNode** headRef, SLTDataType value);
void SListPrepend(SListNode** headRef, SLTDataType value);
void SListRemoveTail(SListNode** headRef);
void SListRemoveHead(SListNode** headRef);
SListNode* SListSearch(SListNode* head, SLTDataType target);
void SListRemoveNode(SListNode** headRef, SListNode* target);
void SListRemoveAfter(SListNode* position);
void SListInsertBefore(SListNode** headRef, SListNode* position, SLTDataType value);
void SListInsertAfter(SListNode* position, SLTDataType value);
void SListDestroy(SListNode** headRef);