Implementing Linked Lists in C: Creation, Traversal, and Operations of Singly Linked Lists
In data structures, a linked list is a very important linear data structure. Unlike arrays, the elements in a linked list do not need to be stored in contiguous memory locations; instead, they are connected through pointers. This article will detail how to implement a simple singly linked list using C, including its creation, traversal, and basic operations.
1. Definition of Singly Linked List
A singly linked list consists of a series of nodes, each containing two parts: a data field and a pointer to the next node. Below is a simple definition of the node structure:
typedef struct Node { int data; // Data field struct Node* next; // Pointer to the next node} Node;2. Creating a Singly Linked List
We can create new nodes by dynamically allocating memory and link them together to form a singly linked list. Here is an example code for creating a singly linked list and inserting a few elements:
#include <stdio.h>#include <stdlib.h>// Node structure definitiontypedef struct Node { int data; struct Node* next;} Node;// Create a new nodeNode* createNode(int value) { Node* newNode = (Node*)malloc(sizeof(Node)); // Dynamically allocate memory newNode->data = value; // Set data field newNode->next = NULL; // Initialize next pointer to NULL return newNode;}// Create a singly linked list and insert elementsNode* createLinkedList() { Node* head = NULL; // Initialize the head of the list to NULL for (int i = 1; i <= 5; i++) { // Insert 5 elements (1 to 5) Node* newNode = createNode(i); // Create a new node if (head == NULL) { // If head is NULL, the new node is the head head = newNode; } else { Node* temp = head; while (temp->next != NULL) { // Find the last node temp = temp->next; } temp->next = newNode; // Link the new node to the last position } } return head; // Return the address of the head node}Code Explanation:
<span>createNode</span>function is used to create a new node and return that node.<span>createLinkedList</span>function generates a singly linked list containing five integers (1 to 5).
3. Traversing a Singly Linked List
Traversal is a way to access each element, starting from the head node, evaluating its value at each node until reaching the end. Here is an example of a traversal function:
// Traverse and print all element valuesvoid traverseLinkedList(Node* head) { Node* current = head; while (current != NULL) { // Continue looping while the current pointer is not NULL printf("%d -> ", current->data); // Print the data of the current node current = current->next; // Move to the next node } printf("NULL\n"); // Indicate the end}Code Explanation:
<span>traverseLinkedList</span>function takes the head node as a parameter and prints the data of each node one by one until it encounters a NULL pointer.
4. Deleting a Node with a Specified Value
The functionality to delete a specific value is also a common requirement. Here, we provide a method to delete the first occurrence of a specified value:
// Delete the first occurrence of a specified valuevoid deleteValue(Node** head, int value) { if (*head == NULL) return; if ((*head)->data == value) { // If the head node is to be deleted Node* temp = *head; *head = (*head)->next; // free(temp); // return; } Node* current = *head; while (current->next != NULL && current->next->data != value) { current= current -> next ; } if(current -> next != NULL){ // Node *temp=current -> next ; current -> next=temp -> next ; free(temp); // }}Code Explanation:
<span>deleteValue</span>function first checks if the head node is the one to be deleted. If not, it finds the position of the target value and adjusts the links to remove that item.
5. Main Function Demonstration
Finally, we write the main function to demonstrate the above functionalities:
int main() { Node *listHead=createLinkedList(); // Create and get the head address of the list printf("Original List: "); traverseLinkedList(listHead); // Traverse and output the original list deleteValue(&&listHead,3); // Delete the number 3 printf("List after deletion: "); traverseLinkedList(listHead); // Traverse and output the updated list return 0 ;}Conclusion
This article introduced how to implement a basic singly linked list in C, including creation, traversal, and deletion operations. These foundational concepts are crucial for understanding more complex data structures and algorithms, and I hope they are helpful to you.