Linked Lists in C: Creation and Operations of Singly Linked Lists

In data structures, linked lists are a very important linear data structure. Unlike arrays, linked lists do not require a predefined size and can dynamically increase or decrease in elements. In this article, we will detail how to create and operate on singly linked lists in C.

What is a Singly Linked List?

A singly linked list consists of a series of nodes, each containing two parts:

  1. Data field: stores the actual data.
  2. Pointer field: points to the address of the next node.

Diagram of a Singly Linked List

+------+-------+    +------+-------+| Data | Next  | -> | Data | Next  |+------+-------+    +------+-------+

Basic Operations of Singly Linked Lists

We will implement the following basic operations:

  1. Create a new node
  2. Insert a node
  3. Delete a node
  4. Traverse the list
  5. Free memory

1. Create a New Node

First, we need to define a structure to represent a single node:

#include <stdio.h>#include <stdlib.h>// Define the structure for a single nodestruct Node {    int data;            // Data field    struct Node* next;   // Pointer field, points to the next node};

Next, we can write a function to create a new node:

// Create a new node and return its pointerstruct Node* createNode(int data) {    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory    if (!newNode) { // Check if memory allocation was successful        printf("Memory allocation failed\n");        return NULL;    }    newNode->data = data; // Set the data value    newNode->next = NULL; // Initialize the next pointer to NULL    return newNode;}

2. Insert a Node

We can insert a new node at the head, tail, or a specified position. Here we implement head insertion:

// Insert a new node at the headvoid insertAtHead(struct Node** head, int data) {    struct Node* newNode = createNode(data); // Create a new node    if (newNode != NULL) {         newNode->next = *head; // New node points to the current head node         *head = newNode;       // Update head to the new node     }}

3. Delete the First Matching Value

Below is the function to delete the first matching value:

// Function to delete the first matching valuevoid deleteValue(struct Node** head, int value) {    struct Node* temp = *head;    if (temp != NULL && temp->data == value) {         *head = temp->next;   // If the head node is to be deleted, update the head         free(temp);           // Free the old head node memory          return;     }     struct Node* prev = NULL;     while (temp != NULL && temp->data != value) {           prev = temp;         temp = temp->next;     }     if (temp == NULL) return;     prev->next = temp->next;   // Link the previous node to the next node       free(temp);                 // Free the deleted node's memory   }

4. Traverse and Print the Entire List

The method to traverse the entire list and print each element is as follows:

// Print the entire linked list contentvoid printList(struct Node* node) {   while (node != NULL) {       printf("%d -> ", node->data);       node = node->next;   }   printf("NULL\n");   }

5. Clean Up Memory

Finally, to avoid memory leaks, we need to clean up all memory allocated for the linked list:

// Clean up all memory allocated for the linked listvoid freeList(struct Node** head){   struct Node* current= *head;   struct Node* next;   while(current!=NULL){      next=current->next;           free(current);               current= next ;           }   *head=NULL ;             }

Main Program Example

Now, let’s integrate these functions into the main program to test our code:

int main() {    struct Node* head = NULL;    // Insert some numbers at the beginning of the list    insertAtHead(&&head, 10);    insertAtHead(&&head, 20);    insertAtHead(&&head, 30);    printf("Current list: ");    printList(head);    // Delete a specific value    deleteValue(&&head,20);    printf("List after deleting 20: ");    printList(head);    // Clean up resources    freeList(&&head);    return 0;}

Conclusion

This article introduced singly linked lists in C, including how to create, insert, delete, traverse, and clean up resources. With this foundational knowledge, you can start using and expanding your data structure skills. I hope this article has been helpful to you!

Leave a Comment