C Linked List – Learn Linked List Implementation in C
A linked list is a linear data structure where each element (node) contains data and a reference (link) to the next node. It allows for efficient insertion and deletion of elements as it does not require shifting elements like arrays.
🔹 What is a Linked List?
A linked list consists of nodes, where each node contains two parts: data and a reference (link) to the next node. The last node in the list points to NULL, indicating the end of the list. Linked lists are dynamic and can grow or shrink in size during runtime.
📝 Example 1: Basic Linked List Node
This example demonstrates creating a simple linked list with one node containing an integer value.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data; // Data part of the node
struct Node* next; // Pointer to the next node
};
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node)); // Create a new node
head->data = 10; // Assign data to the node
head->next = NULL; // No next node, so it's NULL
printf("Linked list element: %d\n", head->data); // Accessing node data
free(head); // Free the allocated memory
return 0;
}
🔹 Inserting Nodes in Linked List
We can insert nodes at the beginning, middle, or end of the list. Inserting at the beginning is straightforward and often used to maintain the head pointer.
📝 Example 2: Inserting a Node at the Beginning
This example demonstrates inserting a new node at the beginning of the linked list.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void insertAtBeginning(struct Node** head, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // Create new node
new_node->data = new_data; // Assign data to the new node
new_node->next = *head; // Link the new node to the current head
*head = new_node; // Move the head pointer to the new node
}
int main() {
struct Node* head = NULL; // Start with an empty list
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
printf("Linked list elements: %d -> %d\n", head->data, head->next->data);
free(head->next); // Free the allocated memory
free(head);
return 0;
}
🔹 Traversing the Linked List
To print or access each node in the linked list, we need to traverse it from the head node until we reach the last node (which points to NULL).
📝 Example 3: Traversing the Linked List
This example shows how to traverse a linked list and print all the elements.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void traverse(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("Node data: %d\n", temp->data); // Print the data of each node
temp = temp->next; // Move to the next node
}
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = NULL; // Last node
traverse(head);
free(head->next); // Free the allocated memory
free(head);
return 0;
}
🔹 Deleting a Node
To delete a node, we need to change the next pointer of the previous node to the next pointer of the node to be deleted, and free the memory of the deleted node.
📝 Example 4: Deleting a Node
This example demonstrates deleting a node from the linked list.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;
// If the head node itself holds the key to be deleted
if (temp != NULL && temp->data == key) {
*head = temp->next; // Move the head to the next node
free(temp); // Free the old head
return;
}
// Search for the node to be deleted
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If the key was not present in the list
if (temp == NULL) return;
// Unlink the node from the list
prev->next = temp->next;
free(temp); // Free the memory of the node
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = NULL;
deleteNode(&head, 10); // Deleting node with data 10
// Traverse and print remaining list
struct Node* temp = head;
while (temp != NULL) {
printf("Node data: %d\n", temp->data);
temp = temp->next;
}
free(head); // Free the remaining allocated memory
return 0;
}
🎯 Key Takeaways
- A linked list is a dynamic data structure with nodes containing data and a pointer to the next node.
- Linked lists support efficient insertion and deletion of elements, especially compared to arrays.
- Operations like insertion, deletion, and traversal require pointer manipulation.
📝 Practice Time!
Modify the examples to experiment with linked list operations like adding more nodes, deleting nodes, and reversing the list!