linked-list-using-C-Data-Structure

admin

1/25/2025

#linked-list-using-C-Data-Structure

Go Back

Linked List Implementation in C: Data Structure Guide

A linked list is a linear data structure where elements are not stored in contiguous memory locations, unlike arrays. Instead, each element in a linked list, called a node, contains data and a pointer to the next node in the sequence. This dynamic nature of linked lists makes them highly efficient for certain operations, such as insertion and deletion.

In this article, we’ll explore the basics of linked lists, discuss their types, and walk through C programs to implement both singly and circular linked lists.


Key Features of a Linked List

  • Dynamic Size: Linked lists can grow or shrink dynamically during runtime without the need for contiguous memory allocation.
  • Efficient Insertion and Deletion: Adding or removing elements at the beginning or end of the list takes constant time, O(1)O(1).
  • Node Structure: Each node consists of two fields:
    • Data Field: Stores the actual value or payload.
    • Pointer Field: Stores the address of the next node.
  • Head Node: The head (or start) node acts as the entry point to access all other elements of the list.

Types of Linked Lists

  1. Singly Linked List: Each node contains one pointer that points to the next node.
  2. Doubly Linked List: Each node contains two pointers: one pointing to the next node and another to the previous node.
  3. Circular Linked List: The last node of the list points back to the first node, forming a circular structure.

Singly Linked List: Example in C

Below is an implementation of a singly linked list, covering operations such as insertion, traversal, searching, and deletion.

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

// Define the structure of a node
struct node {
    int data;
    struct node *next;
};

struct node *head = NULL;

// Function to insert a new node at the end
void insert(int value) {
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        head = newNode;
    } else {
        struct node *temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    printf("Node with value %d inserted.\n", value);
}

// Function to traverse and print the linked list
void traverse() {
    if (head == NULL) {
        printf("The linked list is empty.\n");
        return;
    }
    struct node *temp = head;
    printf("Linked list elements: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to search for a value in the linked list
void search(int value) {
    struct node *temp = head;
    while (temp != NULL) {
        if (temp->data == value) {
            printf("Value %d found in the linked list.\n", value);
            return;
        }
        temp = temp->next;
    }
    printf("Value %d not found in the linked list.\n", value);
}

// Function to delete a node with a specific value
void delete(int value) {
    struct node *temp = head, *prev = NULL;

    if (temp != NULL && temp->data == value) {
        head = temp->next;
        free(temp);
        printf("Node with value %d deleted.\n", value);
        return;
    }

    while (temp != NULL && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Value %d not found in the linked list.\n", value);
        return;
    }

    prev->next = temp->next;
    free(temp);
    printf("Node with value %d deleted.\n", value);
}

// Main function
int main() {
    int choice, value;
    do {
        printf("\nMenu:");
        printf("\n1. Insert");
        printf("\n2. Traverse");
        printf("\n3. Search");
        printf("\n4. Delete");
        printf("\n0. Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter value to insert: ");
                scanf("%d", &value);
                insert(value);
                break;
            case 2:
                traverse();
                break;
            case 3:
                printf("Enter value to search: ");
                scanf("%d", &value);
                search(value);
                break;
            case 4:
                printf("Enter value to delete: ");
                scanf("%d", &value);
                delete(value);
                break;
            case 0:
                printf("Exiting program.\n");
                break;
            default:
                printf("Invalid choice! Please try again.\n");
        }
    } while (choice != 0);

    return 0;
}

Circular Linked List: Example in C

Understanding Circular Linked Lists in C: Code Implementation and Key Concepts

Circular linked lists are a type of linked list where the last node points back to the first node, creating a circular structure. Unlike linear linked lists, where the last node points to NULL, circular linked lists provide more flexibility in traversing nodes and managing memory efficiently.

Key Characteristics of Circular Linked Lists

  1. Circular Structure: The last node's next pointer connects back to the first node, forming a continuous loop.
  2. Efficient Traversal: Starting from any node, you can traverse the entire list without worrying about reaching a NULL pointer.
  3. Dynamic Size: Like other linked lists, circular linked lists can dynamically grow or shrink during runtime.
  4. No Explicit End: There is no NULL to signify the end of the list; instead, the loop continues until a specific condition is met.

Circular Linked List Code Implementation in C

Below is a comprehensive implementation of a circular linked list in C:

#include<stdio.h>
#include<alloc.h>
#include<conio.h>

struct node {
    int no;
    struct node *next;
};

struct node *start = NULL;

void append() {
    struct node *p = start, *n;
    n = (struct node *)malloc(sizeof(struct node));
    printf("\nEnter no: ");
    scanf("%d", &n->no);
    n->next = NULL;
    if (start == NULL) {
        start = n;
        start->next = start;
        return;
    }
    while (p->next != start) {
        p = p->next;
    }
    p->next = n;
    n->next = start;
}

void traverse(struct node *q) {
    struct node *r = q;
    if (q == NULL) {
        printf("\nList is empty");
        return;
    }
    do {
        printf("  %d", q->no);
        q = q->next;
    } while (q != r);
}

void tra_f_node(struct node *p) {
    int val;
    if (p == NULL) {
        printf("\nList is empty");
        return;
    }
    printf("\nEnter No from Which you want to search:");
    scanf("%d", &val);
    do {
        if (val == p->no) {
            traverse(p);
            return;
        }
        p = p->next;
    } while (p != start);
    printf("\n%d Not Found", val);
}

void search() {
    struct node *p = start;
    int val;
    if (p == NULL) {
        printf("\nList is empty");
        return;
    }
    printf("\nEnter element to be searched: ");
    scanf("%d", &val);
    do {
        if (val == p->no) {
            printf("\nElement found");
            return;
        }
        p = p->next;
    } while (p != start);
    printf("\nElement not found");
}

void del_all() {
    struct node *p;
    if (start == NULL) {
        printf("\nList is already empty");
        return;
    }
    do {
        p = start;
        start = start->next;
        free(p);
    } while (start != p);
    start = NULL;
}

void main() {
    int ch;
    do {
        clrscr();
        printf("\n1. Append\n2. Traverse\n3. Search\n4. Exit\nEnter your choice: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                append();
                break;
            case 2:
                traverse(start);
                break;
            case 3:
                search();
                break;
            case 4:
                del_all();
                printf("\nExiting...");
                break;
            default:
                printf("\nInvalid choice");
        }
        printf("\nPress any key to continue...");
        getch();
    } while (ch != 4);
}

 


Why Use Linked Lists?

  • Flexible Memory Allocation: Linked lists don’t require contiguous memory, making them more suitable for dynamic memory management.
  • Efficient Operations: Unlike arrays, insertion and deletion operations in linked lists don’t require shifting elements.

Conclusion

Linked lists are a fundamental data structure in computer science, offering dynamic memory management and efficient operations. The implementation of both singly linked lists and circular linked lists in C showcases how we can use pointers and structures to handle data flexibly.

By mastering linked lists, developers can efficiently handle complex data structures, making them invaluable in competitive programming and real-world applications.

#linked-list-using-C-Data-Structure