A linked list in C is a fundamental data structure used to organize a collection of elements. Unlike arrays, linked lists allow dynamic memory allocation and efficient insertion and deletion operations. In this article, we’ll focus on implementing a singly linked list in C and explore how to add, delete, and find nodes within it.
Importance of Linked List in C:
Dynamic Size: Linked list can grow or shrink dynamically as needed, making them suitable for scenarios where the size of the data structure is unknown in advance.
Efficient Insertions and Deletions: Adding or removing elements from a linked list in C is efficient because it involves adjusting pointers rather than shifting memory blocks.
Versatility: Linked list in C serve as building blocks for other data structures like stacks, queues, and graphs.
Memory Allocation: Linked list in C allows for non-contiguous memory allocation, overcoming the limitations of fixed-size arrays.
Linked List Node Structure
A linked list consists of nodes, where each node contains two fields:
Data: Holds the actual value.
Next: Points to the next node in the list.
Data Field (Value):
The data field (also known as the value or payload) holds the actual information associated with the node. It can be any type of data, such as an integer, string, or a custom-defined structure.
For example, in a list of integers, the data field would store the numeric value itself.
Next Field (Pointer):
The next field (often called the next pointer) is crucial for maintaining the linkage between nodes in the list.
It contains the memory address (or reference) of the next node in the sequence.
Essentially, it points to the following node, allowing us to traverse the list from one node to the next.
In the last node of the list, the next field typically points to a special value (often NULL or nullptr) to indicate the end of the list.
Let’s define the structure for our linked list node:
struct Node {
int data;
struct Node* next;
};Basic Operations for Linked List in C
Insertion Operation
Linked list allow dynamic memory allocation and efficient insertion of elements. Key insertion scenarios:
Insertion at the Beginning: Create a new node and update the head pointer.
Insertion at the End: Traverse the list and append the new node.
Insertion in the beginning
When adding a new node at the beginning of the linked list, follow these steps:
Create a new node (let’s call it newNode).
Set the data field of newNode to the desired value.
Update the next field of newNode to point to the current head of the list.
Update the head pointer to point to newNode.
Here’s the C code snippet for inserting a node at the beginning:
#include <stdio.h>
#include <stdlib.h>
// Define Node structure
struct Node {
int data;
struct Node* next;
};
// Global variable head
struct Node* head = NULL;
// Function to insert a node at the beginning of the linked list
void insertAtBeginning(int value) {
// Allocate memory for new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
// Set data and next pointer of new node
newNode->data = value;
newNode->next = head;
// Update head to point to new node
head = newNode;
}
// Function to print the linked list
void printLinkedList() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Main function
int main() {
// Inserting elements at the beginning of the linked list
insertAtBeginning(3);
insertAtBeginning(5);
insertAtBeginning(7);
insertAtBeginning(10);
// Printing the linked list
printf("Each element is inserted at the beginning of the list\n");
printf("Linked list: ");
printLinkedList();
return 0;
}
Insert at the End
To insert a node at the end of the linked list, follow these steps:
Create a new node (again, let’s call it newNode).
Set the data field of newNode to the desired value.
If the list is empty (i.e., head is NULL), make newNode the new head.
Otherwise, traverse the list until you reach the last node (where next is NULL).
Update the next field of the last node to point to newNode.
Here’s the C code snippet for inserting a node at the end:
#include <stdio.h>
#include <stdlib.h>
// Define Node structure
struct Node {
int data;
struct Node* next;
};
// Global variable head
struct Node* head = NULL;
// Function to insert a node at the end of the linked list
void insertAtEnd(int value) {
// Allocate memory for new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
// Set data and next pointer of new node
newNode->data = value;
newNode->next = NULL;
// If the list is empty, make the new node the head
if (head == NULL) {
head = newNode;
return;
}
// Traverse to the end of the list
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
// Insert the new node at the end
temp->next = newNode;
}
// Function to print the linked list
void printLinkedList() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Main function
int main() {
// Inserting elements at the end of the linked list
insertAtEnd(3);
insertAtEnd(5);
insertAtEnd(7);
insertAtEnd(10);
// Printing the linked list
printf("Each element is inserted at the end of the list\n");
printf("Linked list: ");
printLinkedList();
return 0;
}
Delete by Value
The deleteNode function removes the first occurrence of a given value from the linked list. Here’s how it works:
Initialize two pointers: temp (to traverse the list) and prev (to keep track of the previous node).
While temp is not NULL and the data in the current node (temp->data) is not equal to the target value:
Update prev to temp.
Move temp to the next node.
If temp becomes NULL, the value was not found in the list. Print an appropriate message.
Otherwise:
If prev is NULL, the target value is in the head node. Update head to point to the next node.
Otherwise, update prev->next to skip the node containing the target value.
Free the memory occupied by the removed node.
Here’s the C code snippet for deleting a node by value:
#include <stdio.h>
#include <stdlib.h>
// Define Node structure
struct Node {
int data;
struct Node* next;
};
// Global variable head
struct Node* head = NULL;
// Function to delete a node with given value from the linked list
void deleteNode(int value) {
// Initialize pointers for traversal
struct Node* temp = head;
struct Node* prev = NULL;
// Traverse the list to find the node to delete
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}
// If node with given value is not found
if (temp == NULL) {
printf("Value %d not found in the list.\n", value);
return;
}
// If the node to be deleted is the head node
if (prev == NULL) {
head = temp->next;
} else {
// Update the previous node's next pointer to skip the node to be deleted
prev->next = temp->next;
}
// Free the memory occupied by the node to be deleted
free(temp);
}
// Function to print the linked list
void printLinkedList() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Main function
int main() {
// Code for testing deleteNode function
// Inserting elements into the linked list
struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
node1->data = 3;
node2->data = 5;
node3->data = 7;
head = node1;
node1->next = node2;
node2->next = node3;
node3->next = NULL;
// Deleting a node
deleteNode(5);
// Printing the linked list
printf("Linked list after deletion: ");
printLinkedList();
return 0;
}
Search
The search function checks whether a given value exists in the linked list. It returns 1 if the value is found and 0 otherwise:
Initialize a pointer temp to traverse the list.
While temp is not NULL:
If the data in the current node (temp->data) matches the target value, return 1.
Otherwise, move temp to the next node.
If the loop completes without finding the value, return 0.
Here’s the C code snippet for searching a value in the list:
#include <stdio.h>
#include <stdlib.h>
// Define Node structure
struct Node {
int data;
struct Node* next;
};
// Global variable head
struct Node* head = NULL;
// Function to search for a value in the linked list
int search(int value) {
// Initialize pointer for traversal
struct Node* temp = head;
// Traverse the list to search for the value
while (temp != NULL) {
if (temp->data == value) {
return 1; // Value found
}
temp = temp->next;
}
return 0; // Value not found
}
// Main function
int main() {
// Code for testing search function
// Inserting elements into the linked list
struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
struct Node* node3 = (struct Node*)malloc(sizeof(struct Node));
node1->data = 3;
node2->data = 5;
node3->data = 7;
head = node1;
node1->next = node2;
node2->next = node3;
node3->next = NULL;
// Searching for values
int value1 = 5;
int value2 = 8;
if (search(value1))
printf("%d is found in the list.\n", value1);
else
printf("%d is not found in the list.\n", value1);
if (search(value2))
printf("%d is found in the list.\n", value2);
else
printf("%d is not found in the list.\n", value2);
return 0;
}
Practical Examples
Linked list is used for:
1. Implementing Stacks and Queues:
Stacks: A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. Linked list can be used to implement stacks efficiently. The top of the stack corresponds to the head of the linked list.
Queues: A queue follows the First-In-First-Out (FIFO) principle. Linked list can serve as the underlying data structure for implementing queues.
2. Dynamic Memory Allocation:
Linked list allow dynamic memory allocation, which means you can create and remove nodes as needed during program execution.
When you allocate memory for a new node, it doesn’t have to be contiguous with other nodes, unlike arrays.
This flexibility is especially useful when dealing with variable-sized data or when memory requirements change dynamically.
3. Preparing for More Complex Data Structures:
Linked list serve as building blocks for more advanced data structures:
Graphs: Graphs can be represented using linked list (adjacency lists) to store connections between nodes (vertices).
Trees: Some tree structures (e.g., binary trees) can be implemented using linked list.
Hash Tables: Separate chaining in hash tables often uses linked list to handle collisions.
Conclusion
In this article, we explored the intricacies of linked list in C. These dynamic data structures play a pivotal role in programming, offering flexibility and efficient memory management. Linked list serve as building blocks for more complex data structures like graphs and trees.
תגובות