Singly Linked List Implementation in C Programming Language

A singly linked list is a fundamental data structure in computer science that consists of a sequence of elements, called nodes. Each node contains data and a pointer to the next node in the sequence. Unlike arrays, linked lists don’t store elements in contiguous memory locations, making them more flexible for dynamic data management.

Below is how a singly linked list looks like:

This article explores the structure and C implementation of singly linked lists, including key operations like insertion, deletion, searching, and traversal. It also covers time and space complexity analysis. We’ll start by declaring the structures for the singly linked list, and then implement all the basic operations.

Implementing the Singly Linked List Structure

To implement a singly linked list in C, we need to create two structures: Node and LinkedList.

`Node` Structure

The Node structure represents the structure of all individual nodes present in the Singly Linked list:

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

The purpose of each field in the structure is as follows:

data: Stores the actual value of the node.
next: A pointer to the next node in the list. Its value is initially set to NULL, indicating that there are no nodes after this node.

`LinkedList` Structure

The LinkedList structure manages the entire list:

typedef struct {
  Node* head;
  int size;
} LinkedList;

The purpose of each field in the structure is as follows:

head: Points to the first node in the list. Its value is initially set to NULL, indicating an empty list.
size: Keeps track of the number of nodes in the list.

This base implementation of linked list structure provides a foundation for adding more complex operations like insertion, deletion, and traversal, which we’ll explore in the following sections.

Implementing Basic Operations for Singly Linked List

`insert_at_beginning`

This operation adds a new node at the start of the list and makes the newly added node the new head of the singly linked list.

Algorithm:

Create a new node with the given data.
Set the new node’s next pointer to the current head.
Update the head to point to the new node.
Increment the size of the list.

Time Complexity: O(1) (constant time, as it only involves updating a few pointers)
Space Complexity: O(1) (only creates one new node, regardless of list size)

void insert_at_beginning(LinkedList* list, int data) {
  Node* new_node = (Node*)malloc(sizeof(Node));
  if (new_node == NULL) {
    fprintf(stderr, "Memory allocation failed\n");
    return;
  }
  new_node->data = data;
  new_node->next = list->head;
  list->head = new_node;
  list->size++;
}

Note: In C, we need to manually allocate memory for the new node using malloc(). It’s important to check if the allocation was successful by checking if new_node is not NULL before proceeding further.

`insert_at_end`

This operation appends a new node to the end of the singly linked list.

Algorithm:

Create a new node with the given data.
If the list is empty, make the new node the head.
Otherwise, traverse to the last node and set its next pointer to the new node.
Increment the size of the list.

Time Complexity: O(n), where n is the number of nodes in the list (need to traverse the entire list to reach the end)
Space Complexity: O(1) (only creates one new node, regardless of list size)

void insert_at_end(LinkedList* list, int data) {
  Node* new_node = (Node*)malloc(sizeof(Node));
  if (new_node == NULL) {
    fprintf(stderr, "Memory allocation failed\n");
    return;
  }
  new_node->data = data;
  new_node->next = NULL;

  if (list->head == NULL) {
    list->head = new_node;
  } else {
    Node* current = list->head;
    while (current->next != NULL) {
      current = current->next;
    }
    current->next = new_node;
  }
  list->size++;
}

`delete_node`

This operation removes a specific node from the singly linked list.

Algorithm:

Check if the list is empty. If so, return without doing anything.
Check if the head node contains the data to be deleted:
- If yes, update the head to point to the next node.
- Decrement the size of the list.
- Free the memory of the deleted node.
- Return from the function.
Traverse the list to find the node to delete and its previous node:
- Start from the head and move to the next node.
- Continue until we find a node with the matching data or reach the end of the list.
If a node with matching data is found:
- Update the previous node’s next pointer to skip the node to be deleted.
- Free the memory of the deleted node.
- Decrement the size of the list.

Time Complexity: O(n), where n is the number of nodes in the list (may need to traverse the entire list to find the node)
Space Complexity: O(1) (only uses a few temporary variables, regardless of list size)

void delete_node(LinkedList* list, int data) {
  if (list->head == NULL) {
    return;
  }

  if (list->head->data == data) {
    Node* temp = list->head;
    list->head = list->head->next;
    free(temp);
    list->size--;
    return;
  }

  Node* current = list->head;
  while (current->next != NULL && current->next->data != data) {
    current = current->next;
  }

  if (current->next != NULL) {
    Node* temp = current->next;
    current->next = current->next->next;
    free(temp);
    list->size--;
  }
}

Note: In C, we need to manually free the memory of the deleted node using free() to avoid memory leaks.

`search_node`

This operation searches for a node with a given value.

Algorithm:

Traverse the list from the head.
Compare each node’s data with the search value.
Return the node if found, or NULL if not found.

Time Complexity: O(n), where n is the number of nodes in the list (may need to traverse the entire list to find the node)
Space Complexity: O(1) (only uses a single temporary variable, regardless of list size)

Node* search_node(LinkedList* list, int data) {
  Node* current = list->head;
  while (current != NULL) {
    if (current->data == data) {
      return current;
    }
    current = current->next;
  }
  return NULL;
}

`get_size`

This operation returns the total number of nodes in the list.

Algorithm:

Return the size attribute of the list.

Time Complexity: O(1) (constant time, as it simply returns a pre-computed value)
Space Complexity: O(1) (no additional space used)

int get_size(LinkedList* list) {
  return list->size;
}

`print_list`

This operation displays all elements in the list sequentially.

Algorithm:

Traverse the list from the head.
Print each node’s data.

Time Complexity: O(n), where n is the number of nodes in the list (needs to visit every node once)
Space Complexity: O(1) (only uses a single temporary variable, regardless of list size)

void print_list(LinkedList* list) {
  Node* current = list->head;
  while (current != NULL) {
    printf("%d -> ", current->data);
    current = current->next;
  }
  printf("NULL\n");
}

Overall Implementation with Example Usage

Here’s a complete implementation of the singly linked list in C along with example usage:


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

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

typedef struct {
  Node* head;
  int size;
} LinkedList;

void insert_at_beginning(LinkedList* list, int data) {
  Node* new_node = (Node*)malloc(sizeof(Node));
  if (new_node == NULL) {
    fprintf(stderr, "Memory allocation failed\n");
    return;
  }
  new_node->data = data;
  new_node->next = list->head;
  list->head = new_node;
  list->size++;
}

void insert_at_end(LinkedList* list, int data) {
  Node* new_node = (Node*)malloc(sizeof(Node));
  if (new_node == NULL) {
    fprintf(stderr, "Memory allocation failed\n");
    return;
  }
  new_node->data = data;
  new_node->next = NULL;

  if (list->head == NULL) {
    list->head = new_node;
  } else {
    Node* current = list->head;
    while (current->next != NULL) {
      current = current->next;
    }
    current->next = new_node;
  }
  list->size++;
}

void delete_node(LinkedList* list, int data) {
  if (list->head == NULL) {
    return;
  }

  if (list->head->data == data) {
    Node* temp = list->head;
    list->head = list->head->next;
    free(temp);
    list->size--;
    return;
  }

  Node* current = list->head;
  while (current->next != NULL && current->next->data != data) {
    current = current->next;
  }

  if (current->next != NULL) {
    Node* temp = current->next;
    current->next = current->next->next;
    free(temp);
    list->size--;
  }
}

Node* search_node(LinkedList* list, int data) {
  Node* current = list->head;
  while (current != NULL) {
    if (current->data == data) {
      return current;
    }
    current = current->next;
  }
  return NULL;
}

int get_size(LinkedList* list) {
  return list->size;
}

void print_list(LinkedList* list) {
  Node* current = list->head;
  while (current != NULL) {
    printf("%d -> ", current->data);
    current = current->next;
  }
  printf("NULL\n");
}

void free_list(LinkedList* list) {
  Node* current = list->head;
  while (current != NULL) {
    Node* temp = current;
    current = current->next;
    free(temp);
  }
  list->head = NULL;
  list->size = 0;
}

int main() {
  LinkedList my_list = {NULL, 0};

  // Insert elements at the beginning
  insert_at_beginning(&my_list, 3);
  insert_at_beginning(&my_list, 2);
  insert_at_beginning(&my_list, 1);

  printf("After inserting 1, 2, 3 at the beginning:\n");
  print_list(&my_list);

  // Insert elements at the end
  insert_at_end(&my_list, 4);
  insert_at_end(&my_list, 5);

  printf("After inserting 4 and 5 at the end:\n");
  print_list(&my_list);

  // Delete a node
  delete_node(&my_list, 3);

  printf("After deleting node with value 3:\n");
  print_list(&my_list);

  // Search for a node
  Node* found_node = search_node(&my_list, 4);
  printf("Searched for 4, found: %s\n", found_node ? "Yes" : "No");

  // Get the size of the list
  printf("Size of the list: %d\n", get_size(&my_list));

  // Free the memory used by the list
  free_list(&my_list);

  return 0;
}

This implementation demonstrates the creation of a singly linked list and various operations such as insertion at the beginning and end, deletion, searching, and printing the list. The example usage shows how to create a list, add elements, delete a node, search for a value, and get the size of the list. When you run this code, you’ll see the list’s state after each operation, allowing you to visualize how the singly linked list changes with different operations.

Note that in C, we need to be careful about memory management. We’ve added a free_list function to properly clean up the memory used by the list when we’re done with it. This is crucial to prevent memory leaks in C programs.

Singly Linked List Implementation in C Programming Language

Implementing the Singly Linked List Structure

Node Structure

LinkedList Structure

Implementing Basic Operations for Singly Linked List

insert_at_beginning

insert_at_end

delete_node

search_node

get_size

print_list

Overall Implementation with Example Usage

`Node` Structure

`LinkedList` Structure

`insert_at_beginning`

`insert_at_end`

`delete_node`

`search_node`

`get_size`

`print_list`