| C language content |
|---|
| Preprocessor Directives |
|---|
| Debugging and Testing |
|---|
Introduction to Linked Lists in C
A linked list is a fundamental data structure in computer science used to store a collection of elements. Unlike arrays, linked lists do not require contiguous memory locations, making them dynamic and flexible for insertion and deletion operations.
Types of Linked Lists
- Singly Linked List: Each node points to the next node.
- Doubly Linked List: Each node points to both the next and the previous node.
- Circular Linked List: The last node points back to the first node, forming a circle.
Components of a Linked List
A linked list is composed of nodes, where each node contains:
- Data: Stores the value.
- Pointer: Points to the next node in the sequence (or the previous node in a doubly linked list).
Singly Linked List Implementation in C
Node Structure
The node structure is defined using a ‘struct‘. Here is how you define a node for a singly linked list:
#include <stdio.h>
#include <stdlib.h>
// Define the node structure
struct Node {
int data;
struct Node* next;
};
Creating a New Node
To create a new node, you allocate memory dynamically and assign the data and next pointer.
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
Inserting a Node
At the Beginning:
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
At the End:
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
Deleting a Node
From the Beginning:
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
From the End:
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
struct Node* prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
free(temp);
}
Traversing the List
To print all the elements of the list:
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
Full Example Program
Here is a complete program demonstrating the creation, insertion, deletion, and traversal of a singly linked list:
#include <stdio.h>
#include <stdlib.h>
// Define the node structure
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
// Function to insert a node at the end
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// Function to delete a node from the beginning
void deleteFromBeginning(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}
// Function to delete a node from the end
void deleteFromEnd(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
struct Node* prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
free(temp);
}
// Function to print the linked list
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// Main function to test the linked list operations
int main() {
struct Node* head = NULL;
// Insert elements at the beginning
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 1);
// Insert elements at the end
insertAtEnd(&head, 4);
insertAtEnd(&head, 5);
// Print the list
printf("Linked List: ");
printList(head);
// Delete elements from the beginning
deleteFromBeginning(&head);
printf("After deleting from beginning: ");
printList(head);
// Delete elements from the end
deleteFromEnd(&head);
printf("After deleting from end: ");
printList(head);
return 0;
}
Conclusion
Linked lists are versatile and powerful data structures that provide efficient insertion and deletion operations. Understanding how to implement and manipulate linked lists in C is fundamental for various applications in computer science.
