Single Linked List in C

A Single Linked List is a linear data structure where each element (node) contains two parts: data and a pointer to the next node.

Unlike arrays, linked lists do not store elements in contiguous memory locations. Each node points to the next node using a pointer.

1. Structure of Single Linked List

Each node in a single linked list contains:

• Data → Stores the value

• Next → Stores the address of the next node

struct Node {
    int data;
    struct Node *next;
};

The first node is called the HEAD. The last node points to NULL.

2. Basic Operations on Single Linked List

1. Insertion

2. Deletion

3. Traversal (Display)

4. Searching

3. C Program to Create and Display Single Linked List

This program creates a linked list by inserting nodes at the end and then displays the elements.

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

struct Node {
    int data;
    struct Node *next;
};

struct Node *head = NULL;

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;
    }
}

void display() {
    struct Node *temp = head;
    if(temp == NULL) {
        printf("List is empty\n");
        return;
    }

    while(temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    insert(10);
    insert(20);
    insert(30);
    insert(40);

    printf("Single Linked List:\n");
    display();

    return 0;
}

Output:
Single Linked List:
10 -> 20 -> 30 -> 40 -> NULL

4. Insertion at Beginning

To insert at the beginning:

1. Create new node.

2. Point newNode->next to head.

3. Update head to newNode.

void insertBeginning(int value) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

5. Deletion from Beginning

To delete the first node:

1. Store head in temporary pointer.

2. Move head to next node.

3. Free the old head node.

void deleteBeginning() {
    if(head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node *temp = head;
    head = head->next;
    free(temp);
}

6. Advantages of Single Linked List

• Dynamic memory allocation.

• Easy insertion and deletion.

• No need for continuous memory.

7. Disadvantages

• Extra memory required for pointer.

• Cannot traverse backward.

• Random access is not possible.

Conclusion

A Single Linked List is a fundamental data structure in C that uses nodes connected by pointers. It allows dynamic memory allocation and efficient insertion and deletion operations.

Understanding linked lists is essential for learning advanced data structures such as stacks, queues, and trees.