Day 3 of DSA in C

July 31, 2025

Day 3 of DSA in C

Write a menu driven C program to create a single linked list and perform the following operations:

1. Append

2. Display

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

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

void append(node **p, int data)
{
    node *r;
    r = (node *)malloc(sizeof(node));
    r->data = data;
    r->next = NULL;
    if (*p == NULL)
    {
        *p = r;
    }
    else
    {
        node *t = *p;
        while (t->next != NULL)
        {
            t = t->next;
        }
        t->next = r;
    }
}

void display(node *p)
{
    printf("<--- Displaying Linked List -->\n");
    while (p != NULL)
    {
        printf(" %d ->", p->data);
        p = p->next;
    }
    printf(" NULL\n");
}

int main()
{
    node *start = NULL;
    int choice;
    do
    {

        printf("\nWelcome to Linked List Menu\n");
        printf("Press 1 to append elements in the linked list\n");
        printf("Press 2 to display the linked list\n");
        printf("Press 0 to end the program\n");
        printf("Enter your choice : ");
        if (scanf("%d", &choice) != 1)
        {
            printf("Invalid input. Please enter a number.\n");
            while (getchar() != '\n')
            choice = -1;
            continue;
        }

        switch (choice)
        {
        case 1:
        {
            int n, item;
            printf("No of elements you want to append : ");
            scanf("%d", &n);
            for (int i = 1; i <= n; i++)
            {
                printf("Enter the element : ");
                scanf("%d", &item);
                append(&start, item);
            }
        }
        break;
        case 2:
            display(start);
            break;
        case 0:
            break;
        default:
            printf("Invalid choice!\n");
        }

    } while (choice != 0);
    return 0;
}

Step 1:

Include the required header files: stdio.h and stdlib.h.

stdio.h is used for standard input/output functions like printf and scanf.
stdlib.h provides memory allocation functions like malloc.

Step 2:

Define the structure node for the linked list.

Each node contains an integer data and a pointer next to the next node.

Step 3:

Define the append function to add a new node at the end of the linked list.

Use malloc to dynamically allocate memory for a new node.
If the list is empty (i.e., *p == NULL), set the head pointer to the new node.
If not, traverse to the last node and set its next to the new node.

Step 4:

Define the display function to print the linked list.

Iterate through the list using a loop and print each node's data followed by an arrow.
After the last node, print NULL to indicate the end of the list.

Step 5:

Define the main function as the program’s entry point.

Declare a pointer start to represent the head of the linked list and initialize it to NULL.

Step 6:

Use a do-while loop to present a menu to the user until they choose to exit.

Print menu options for appending and displaying the linked list, and for exiting the program.
Use scanf to get the user's choice. If input is invalid, flush the input buffer using getchar() and repeat the loop.

Step 7:

Handle each user choice with a switch statement.

Case 1 (Append): Ask how many elements to insert, then call append for each item entered.
Case 2 (Display): Call the display function to print the linked list.
Case 0: Exit the program.
Default: Print an error message for invalid menu options.

Step 8:

After exiting the loop, the program returns 0 and ends.

Write a menu driven C program to create a single linked list and perform the following operations:
1. Insertion
i. Insert at the beginning
ii. Insert at the end
iii. Insert at any given position
iv. Insert before a given node
v. Insert after a given node
2. Display the linked list

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

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

void insert_at_beginning(node **p, int data)
{
    node *r;
    r = (node *)malloc(sizeof(node));
    r->data = data;
    r->next = *p;
    *p = r;
}

void insert_at_end(node **p, int data)
{
    node *r;
    r = (node *)malloc(sizeof(node));
    r->data = data;
    r->next = NULL;
    if (*p == NULL)
    {
        *p = r;
    }
    else
    {
        node *t = *p;
        while (t->next != NULL)
        {
            t = t->next;
        }
        t->next = r;
    }
}

void insert_at_position(node **p, int data, int index)
{
    node *r;
    r = (node *)malloc(sizeof(node));
    r->data = data;
    r->next = NULL;

    if (index == 1)
    {
        r->next = *p;
        *p = r;
        return;
    }

    node *t = *p;
    for (int i = 1; i < index - 1 && t != NULL; i++)
    {
        t = t->next;
    }

    if (t == NULL)
    {
        printf("Index is out of bound\n");
        return;
    }

    r->next = t->next;
    t->next = r;
}

void insert_before_key(node **p, int data, int key)
{
    node *r;
    r = (node *)malloc(sizeof(node));
    r->data = data;
    r->next = NULL;
    if (*p == NULL)
    {
        printf("List is empty, cannot insert before key.\n");
        return;
    }
    if ((*p)->data == key)
    {
        r->next = *p;
        *p = r;
        return;
    }
    else
    {
        node *t = *p;
        while (t->next != NULL && t->next->data != key)
        {
            t = t->next;
        }
        if (t->next == NULL)
        {
            printf("Given key is not found in the list");
            return;
        }
        r->next = t->next;
        t->next = r;
    }
}

void insert_after_key(node **p, int data, int key)
{
    node *r;
    r = (node *)malloc(sizeof(node));
    r->data = data;
    r->next = NULL;

    if (*p == NULL)
    {
        printf("List is empty, cannot insert after key.\n");
        return;
    }

    node *t = *p;
    while (t != NULL && t->data != key)
    {
        t = t->next;
    }

    if (t == NULL)
    {
        printf("Given key is not found in the list.\n");
        return;
    }

    r->next = t->next;
    t->next = r;
}

void display(node *p)
{
    printf("\n<--- Displaying Linked List -->\n");
    while (p != NULL)
    {
        printf(" %d ->", p->data);
        p = p->next;
    }
    printf(" NULL\n");
}

int main()
{
    node *start = NULL;
    int choice;

    do
    {
    main_menu:
        printf("\nWelcome to Linked List Menu\n");
        printf("Press 1 to insert elements in the linked list\n");
        printf("Press 2 to display the linked list\n");
        printf("Press 0 to end the program\n");
        printf("Enter your choice : ");
        if (scanf("%d", &choice) != 1)
        {
            printf("Invalid input. Please enter a number.\n");
            while (getchar() != '\n');
            choice = -1;
            continue;
        }

        switch (choice)
        {
        case 1:
        {
            int n, item, subchoice;

            printf("Enter the method of insertion:\n");
            printf("Press 1 for at the beginning\n");
            printf("Press 2 for at the end\n");
            printf("Press 3 for at an index\n");
            printf("Press 4 for before key node\n");
            printf("Press 5 for after key node\n");
            printf("Press 6 to main menu\n");
            printf("Press 0 to exit the program\n");

            printf("Enter your choice : ");
            if (scanf("%d", &subchoice) != 1)
            {
                printf("Invalid input. Please enter a number.\n");
                while (getchar() != '\n');
                break;
            }

            switch (subchoice)
            {
            case 1:
                printf("No of elements to insert : ");
                scanf("%d", &n);
                for (int i = 1; i <= n; i++)
                {
                    printf("Enter the element : ");
                    scanf("%d", &item);
                    insert_at_beginning(&start, item);
                }
                break;

            case 2:
                printf("No of elements to insert : ");
                scanf("%d", &n);
                for (int i = 1; i <= n; i++)
                {
                    printf("Enter the element : ");
                    scanf("%d", &item);
                    insert_at_end(&start, item);
                }
                break;

            case 3:
            {
                int index;
                printf("Enter the position : ");
                scanf("%d", &index);
                printf("No of elements to insert : ");
                scanf("%d", &n);
                for (int i = index; i < index + n; i++)
                {
                    printf("Enter the element : ");
                    scanf("%d", &item);
                    insert_at_position(&start, item, i);
                }
                break;
            }

            case 4:
            {
                int key;
                printf("Enter the key : ");
                scanf("%d", &key);
                printf("Enter the element : ");
                scanf("%d", &item);
                insert_before_key(&start, item, key);
                break;
            }

            case 5:
            {
                int key;
                printf("Enter the key : ");
                scanf("%d", &key);
                printf("Enter the element : ");
                scanf("%d", &item);
                insert_after_key(&start, item, key);
                break;
            }

            case 6:
                goto main_menu;

            case 0:
                return 0;

            default:
                printf("Invalid choice!\n");
                break;
            }
            break;
        }

        case 2:
            display(start);
            break;

        case 0:
            break;

        default:
            printf("Invalid choice!\n");
            break;
        }

    } while (choice != 0);

    return 0;
}

Step 1:

Include the required header files: stdio.h and stdlib.h.

stdio.h is used for standard input/output functions like printf and scanf.
stdlib.h provides memory allocation functions like malloc.

Step 2:

Define the structure node for the linked list.

Each node contains an integer data and a pointer next to the next node in the list.

Step 3:

Define the insertion functions for the linked list.

insert_at_beginning: This function inserts a new node at the very start of the list. It first allocates memory for the new node. The new node's `next` pointer is then set to point to the current first node of the list (which is pointed to by `*p`). Finally, the head pointer of the list (`*p`) is updated to point to the new node, effectively making it the new beginning of the list. This operation takes constant time, or O(1).
insert_at_end: This function adds a new node to the end of the list. It begins by allocating memory and initializing the new node's data. If the list is empty (`*p == NULL`), the new node becomes the head. If the list already contains nodes, a temporary pointer is used to traverse the list from the beginning until it reaches the last node (the one whose `next` pointer is `NULL`). Once the last node is found, its `next` pointer is updated to point to the new node.
insert_at_position: This function inserts a new node at a specific index within the list. It handles the edge case of inserting at the first position (`index == 1`), which is the same as inserting at the beginning. For any other index, a temporary pointer traverses the list to stop at the node *before* the desired insertion point. The new node is then linked into place by setting its `next` pointer to the node that was previously at the insertion point, and updating the previous node's `next` pointer to the new node. An error message is printed if the specified index is out of bounds.
insert_before_key: This function inserts a new node just before a node with a specific data value (`key`). It first checks for two special cases: an empty list or if the key is in the very first node. In the general case, it traverses the list, but stops when the *next* node's data matches the key. This allows the new node to be correctly linked between the current node and the key node. If the key is not found after traversing the entire list, an appropriate message is displayed.
insert_after_key: This function inserts a new node immediately after a node with a specific data value (`key`). It traverses the list until it finds the node with the matching key. Once found, the new node's `next` pointer is set to point to the node that was originally after the key, and the key node's `next` pointer is updated to point to the new node. If the key is not found in the list, the new node is not inserted and an error message is printed.

Step 4:

Define the display function to print the linked list.

It iterates through the list using a `while` loop, starting from the head (`p`).
In each iteration, it prints the `data` of the current node followed by an arrow, and then moves to the next node.
After the last node, it prints NULL to indicate the end of the list.

Step 5:

Define the main function as the program's entry point.

Declare a pointer start to represent the head of the linked list and initialize it to NULL.
Use a `do-while` loop to present the main menu to the user until they choose to exit.

Step 6:

Handle user choices with a main `switch` statement.

Case 1: Presents a sub-menu for different insertion methods (beginning, end, position, before/after key). It uses a nested `switch` to handle these sub-options.
Case 2: Calls the display function to print the current linked list.
Case 0: Breaks the `do-while` loop, ending the program.
Default: Prints an error message for invalid menu choices.

Step 7:

Handle sub-menu choices with a nested `switch` statement.

Based on the user's `subchoice`, it prompts for the necessary data (number of elements, position, or key) and calls the corresponding insertion function.
Case 6 (main menu): Uses a `goto` statement to jump back to the `main_menu` label, allowing the user to return to the main menu without exiting the program.
Case 0: Returns 0 from `main`, ending the program directly.

Step 8:

After the `do-while` loop finishes, the program returns 0 from `main`, indicating successful execution.

Search This Blog

Byte Invasion

Day 3 of DSA in C

Write a menu driven C program to create a single linked list and perform the following operations:

1. Append

2. Display

Write a menu driven C program to create a single linked list and perform the following operations:
1. Insertion
i. Insert at the beginning
ii. Insert at the end
iii. Insert at any given position
iv. Insert before a given node
v. Insert after a given node
2. Display the linked list

Comments

Popular Posts

Home

University Assignments

Day 3 of DSA in C

Write a menu driven C program to create a single linked list and perform the following operations: 1. Append 2. Display

Write a menu driven C program to create a single linked list and perform the following operations: 1. Insertion i. Insert at the beginning ii. Insert at the end iii. Insert at any given position iv. Insert before a given node v. Insert after a given node 2. Display the linked list

Comments

Popular Posts

Home

University Assignments

Write a menu driven C program to create a single linked list and perform the following operations:

1. Append

2. Display

Write a menu driven C program to create a single linked list and perform the following operations:
1. Insertion
i. Insert at the beginning
ii. Insert at the end
iii. Insert at any given position
iv. Insert before a given node
v. Insert after a given node
2. Display the linked list