What is Linked List in C

A linked list is a linear data structure that consists of a sequence of elements, called nodes. Each node contains two parts:

1. Data: The actual value or data being stored.
2. Pointer (Next): A reference (or pointer) to the next node in the sequence.

In contrast to arrays, linked lists do not store elements in contiguous memory locations. Instead, each node points to the next node, and this allows dynamic memory allocation.

Types of Linked Lists

1. Singly Linked List: Each node contains a data part and a pointer to the next node.
2. Doubly Linked List: Each node contains a data part and two pointers: one pointing to the next node and another pointing to the previous node.
3. Circular Linked List: The last node points back to the first node.

Basic Operations on Linked List

1. Insertion: Add a new node at the beginning, end, or middle.
2. Deletion: Remove a node from the beginning, end, or middle.
3. Traversal: Visit all nodes to access their data.
4. Search: Find a node containing a specific value.

Singly Linked List Implementation in C

Below is an example of how to implement a singly linked list in C:

Structure of a Node

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

// Define a structure for the node
struct Node {
    int data;           // Data part
    struct Node* next;  // Pointer to the next node
};

Function to Create a New Node

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  // Allocate memory for a new node
    newNode->data = data;  // Assign the data to the new node
    newNode->next = NULL;   // Set the next pointer to NULL
    return newNode;
}

Function to Insert a Node at the Beginning

void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = createNode(data);  // Create a new node
    newNode->next = *head;  // Point new node's next to the current head
    *head = newNode;  // Make the new node the head of the list
}

Function to Print the Linked List

void printList(struct Node* head) {
    struct Node* current = head;  // Start from the head node
    while (current != NULL) {
        printf("%d -> ", current->data);  // Print the data of the current node
        current = current->next;  // Move to the next node
    }
    printf("NULL\n");
}

Main Function

int main() {
    struct Node* head = NULL;  // Start with an empty list

    insertAtBeginning(&head, 10);  // Insert 10 at the beginning
    insertAtBeginning(&head, 20);  // Insert 20 at the beginning
    insertAtBeginning(&head, 30);  // Insert 30 at the beginning

    printf("Linked List: ");
    printList(head);  // Print the list

    return 0;
}

Output

Linked List: 30 -> 20 -> 10 -> NULL

Explanation of Code

1. Node Structure: The struct Node defines the structure of a linked list node, containing an integer data and a pointer next that points to the next node.
2. createNode() Function: This function allocates memory for a new node, assigns the provided data to the node, and sets its next pointer to NULL (indicating it is the last node).
3. insertAtBeginning() Function: This function inserts a new node at the beginning of the linked list. It creates a new node, then points the next pointer of the new node to the current head of the list. The head pointer is updated to the new node.
4. printList() Function: This function traverses the entire list from the head and prints the data of each node until the end (NULL) is reached.

Other Operations on Linked List

1. Insertion at End: To insert at the end, we need to traverse to the last node and set its next pointer to the new node.
2. Deletion of a Node: To delete a node, we need to adjust the next pointer of the previous node to skip the node being deleted.
3. Searching for a Node: To search, traverse the list and compare the data of each node with the target value.

Advantages of Linked List

• Dynamic Size: Unlike arrays, linked lists can dynamically grow and shrink in size.
• Efficient Insertions and Deletions: Inserting and deleting nodes can be done in constant time, provided we have direct access to the nodes.

Disadvantages of Linked List

• Memory Usage: Each node requires extra memory for storing the pointer.
• Sequential Access: To access a specific node, we have to traverse from the head node, making it slower than arrays for random access.

Conclusion

Linked lists are fundamental data structures in C and are widely used in various applications like implementing stacks, queues, and dynamic memory allocation. The main advantage of linked lists over arrays is the ability to efficiently manage dynamic data.