Prerequisites

Before diving into the implementation, let's include the necessary header files:

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

typedef int ELEMENT;  // Custom data type alias

Structure Definitions

For a linked list implementation, we need to define a node structure and a list structure:

// Node structure definition
typedef struct ListNode
{
    ELEMENT value;
    struct ListNode *link;
} Node;

// Linked list container structure
typedef struct
{
    Node *front;      // Head pointer
    Node *rear;       // Tail pointer
    unsigned count;   // Number of elements
} LinkedList;

Initialization

// Initialize an empty linked list
LinkedList *initialize(LinkedList *lst)
{
    lst->front = NULL;
    lst->rear = NULL;
    lst->count = 0;
    return lst;
}

Node Creation

// Create a new node with the given data
Node *allocate_node(ELEMENT item)
{
    Node *node_ptr = (Node *)malloc(sizeof(Node));
    if (!node_ptr)
        return NULL;
    node_ptr->value = item;
    node_ptr->link = NULL;
    return node_ptr;
}

Core Linked List Operations

• 1. Destroy all nodes
• 2. Insert at beginning
• 3. Insert at end
• 4. Delete first node
• 5. Delete last node
• 6. Locate element position
• 7. Insert after a given node
• 8. Insert before a given node (approach 1)
• 9. Insert before a given node (approach 2)
• 10. Remove node following a given node
• 11. Remove specific node (approach 1)
• 12. Remove specific node (approach 2)
• 13. Traverse and display elements

Operation 1: Destroy All Nodes

// Remove all nodes from the linked list
void destroy_list(LinkedList *lst)
{
    while (lst->front)
    {
        Node *temp = lst->front;
        lst->front = lst->front->link;
        free(temp);
    }
    lst->rear = NULL;
    lst->count = 0;
}

Function signature:

void destroy_list(LinkedList *lst)

The return type is void since the operation modifies the list in place and doesn't need to return a value. The function takes a pointer to the LinkedList structure as its parameter.

Function body breakdown:

while (lst->front)  // Continue while list is not empty
{
    Node *temp = lst->front;
    lst->front = lst->front->link;
    free(temp);
}

1. The while loop iterates until the front pointer becomes NULL
2. A temporary pointer stores the current front node
3. The front pointer advances to the next node
4. The original node is deallocated via free()

lst->rear = NULL;
lst->count = 0;

After all nodes are freed, the rear pointer is set to NULL and the element count is reset to zero.

Operation 2: Insert at Beginning

// Add element to the front of the list
LinkedList *add_front(LinkedList *lst, ELEMENT item)
{
    Node *new_node = allocate_node(item);
    if (!new_node)
        return NULL;
    if (lst->rear == NULL)
        lst->rear = new_node;
    new_node->link = lst->front;
    lst->front = new_node;
    lst->count++;
    return lst;
}

Function signature:

LinkedList *add_front(LinkedList *lst, ELEMENT item)

The function returns a pointer to the modified list for potential chaining. The first parameter is the list pointer, and the second parameetr is the data value to insert.

Function body breakdown:

1. A new node is allocated using the helper function
2. If allocation fails, NULL is returned immediately
3. For an empty list, the new node becomes both head and tail
4. The new node's link points to the current first element
5. The front pointer is updated to reference the new node
6. The element count increments

Operation 3: Insert at End

// Append element to the end of the list
LinkedList *add_rear(LinkedList *lst, ELEMENT item)
{
    Node *new_node = allocate_node(item);
    if (!new_node)
        return NULL;
    if (lst->rear)
        lst->rear->link = new_node;
    else
        lst->front = new_node;
    lst->rear = new_node;
    lst->count++;
    return lst;
}

Function signature:

LinkedList *add_rear(LinkedList *lst, ELEMENT item)

<p>This function mirrors the front insertion but operates on the tail end. It also returns the list pointer for convenience.</p>

<p><strong>Function body breakdown:</strong></p>

<ol>
<li>A new node is created with the provided data</li>
<li>If the list is not empty, the current tail's link is set to the new node</li>
<li>If the list is empty, the new node becomes the head</li>
<li>The rear pointer always points to the newly added node</li>
<li>The element count is incremented</li>
</ol>

<hr></hr>

<h3>Operation 4: Delete First Node</h3>

<code>// Remove the first element from the list
LinkedList *remove_first(LinkedList *lst)
{
    if (lst->front == NULL)  // Empty list condition
        return NULL;
    Node *victim = lst->front;
    lst->front = lst->front->link;
    free(victim);
    lst->count--;
    if (lst->count == 0)  // List became empty after removal
        lst->rear = lst->front;
    return lst;
}</code>

<p><strong>Function signature:</strong></p>

<code>LinkedList *remove_first(LinkedList *lst)</code>

<p>Returns NULL if the list was already empty, otherwise returns the modified list pointer.</p>

<p><strong>Function body breakdown:</strong></p>

<ol>
<li>The function first checks if the list contains any elements</li>
<li>The current head node is stored in a temporary variable</li>
<li>The front pointer advances to the second node</li>
<li>The original head node is deallocated</li>
<li>The element count is decremented</li>
<li>If the list becomes empty, both front and rear pointers are set to NULL</li>
</ol>

<hr></hr>

<h3>Operation 5: Delete Last Node</h3>

<code>// Remove the last element from the list
LinkedList *remove_last(LinkedList *lst)
{
    if (lst->count == 0)
        return NULL;
    Node *new_last = lst->front;
    Node *victim = lst->rear;
    if (lst->count > 1)
    {
        while (new_last->link != lst->rear)
            new_last = new_last->link;
        lst->rear = new_last;
        new_last->link = NULL;
    }
    else
    {
        lst->front = NULL;
        lst->rear = NULL;
    }
    free(victim);
    lst->count--;
    return lst;
}</code>

<p><strong>Functon signature:</strong></p>

<code>LinkedList *remove_last(LinkedList *lst)</code>

<p>This operation is more complex because singly linked lists lack a backward reference. The algorithm must traverse from the beginning to find the node preceding the tail.</p>

<p><strong>Function body breakdown:</strong></p>

<ol>
<li>If the list is empty, return NULL immediately</li>
<li>Store pointers to the current first and last nodes</li>
<li>If more than one node exists, iterate to find the second-to-last node</li>
<li>Update the rear pointer to the new last node</li>
<li>Set the new last node's link to NULL</li>
<li>If only one node existed, set both pointers to NULL</li>
<li>Deallocate the removed node and decrement the count</li>
</ol>

<hr></hr>

<p><strong>To be continued...</strong></p>