How to create a linked list in C?

In C, creating a linked list involves understanding the structure of nodes and implementing various operations for insertion, deletion, and traversal.

This comprehensive guide explores the step-by-step process of creating a linked list in C, covering essential concepts, code examples, and best practices.

Table of Contents

  1. Introduction to Linked Lists in C
  2. Structure of a Linked List Node
  3. Creating an Empty Linked List
  4. Inserting Elements into a Linked List
  5. Deleting Elements from a Linked List
  6. Traversing a Linked List
  7. Best Practices for Linked Lists in C
  8. Conclusion

1. Introduction to Linked Lists in C

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next one in the sequence.

Unlike arrays, linked lists dynamically allocate memory, allowing for efficient insertions and deletions.

In C, implementing a linked list involves defining the structure of a node and creating functions to manipulate the list.

2. Structure of a Linked List Node

A linked list node typically consists of two parts:

struct Node {
    int data;           // Data of the node
    struct Node* next;  // Pointer to the next node
};

3. Creating an Empty Linked List

To create an empty linked list, a pointer to the head node is initialized to NULL. The head pointer serves as the starting point for accessing the linked list.

struct Node* head = NULL;

4. Inserting Elements into a Linked List

a. Insert at the Beginning:

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

b. Insert at the End:

void insertAtEnd(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        head = newNode;
        return;
    }

    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

c. Insert at a Specific Position:

void insertAtPosition(int value, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (position == 1) {
        newNode->next = head;
        head = newNode;
        return;
    }

    struct Node* temp = head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        // Invalid position
        return;
    }

    newNode->next = temp->next;
    temp->next = newNode;
}

5. Deleting Elements from a Linked List

a. Delete from the Beginning:

void deleteFromBeginning() {
    if (head == NULL) {
        return; // Empty list
    }

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

b. Delete from the End:

void deleteFromEnd() {
    if (head == NULL) {
        return; // Empty list
    }

    if (head->next == NULL) {
        free(head);
        head = NULL;
        return;
    }

    struct Node* temp = head;
    struct Node* prev = NULL;

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

    prev->next = NULL;
    free(temp);
}

c. Delete at a Specific Position:

void deleteAtPosition(int position) {
    if (head == NULL) {
        return; // Empty list
    }

    struct Node* temp = head;

    if (position == 1) {
        head = temp->next;
        free(temp);
        return;
    }

    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        // Invalid position
        return;
    }

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

6. Traversing a Linked List

void traverse() {
    struct Node* temp = head;

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

    printf("NULL\n");
}

7. Best Practices for Linked Lists in C

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

8. Conclusion

Creating and manipulating linked lists in C is a fundamental skill for programmers dealing with dynamic data structures.

By understanding the structure of linked list nodes and implementing key operations, developers can leverage the flexibility and efficiency of linked lists for various applications.

Best practices, such as proper memory management and encapsulation, contribute to writing reliable and maintainable linked list code.

Mastery of linked lists opens the door to more advanced data structures and algorithms, making it an essential topic for every C programmer to grasp.