A linked list is a data structure in C that consists of a sequence of elements, each containing a data part and a reference (link) to the next element in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, which allows for efficient insertion and deletion of elements.
A linked list is composed of two main components:
A node in a linked list is typically defined as a structure in C. Here’s how a node can be represented in C:
#include <stdio.h>
struct Node {
int data;
struct Node* next;
};
In this example, struct Node contains two members: data (which stores the value of the node) and next (a pointer to the next node in the list).
Common operations that can be performed on a linked list include insertion, deletion, traversal, and searching.
Inserting a new node into a linked list can be done in several ways: inserting at the beginning, at the end, or at a specific position.
To insert a node at the beginning, we create a new node, set its next pointer to the current head, and then update the head to point to the new node.
#include <stdio.h>>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to insert at the beginning
void insertAtBeginning(struct Node** head, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = *head;
*head = newNode;
}
// 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");
}
int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 30);
printList(head); // Output: 30 -> 20 -> 10 -> NULL
return 0;
}
In this example, the function insertAtBeginning inserts a new node at the beginning of the list. The new node becomes the head of the list.
Deleting a node from a linked list can be done in various ways, such as deleting the first node, the last node, or a specific node.
To delete the first node, we update the head to point to the next node, effectively removing the first node from the list.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to delete the first node
void deleteFirstNode(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
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");
}
int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 30);
printf("Original List:\n");
printList(head); // Output: 30 -> 20 -> 10 -> NULL
deleteFirstNode(&head);
printf("List after deletion:\n");
printList(head); // Output: 20 -> 10 -> NULL
return 0;
}
In this example, the function deleteFirstNode deletes the first node from the linked list. After deletion, the new head points to the second node.
Traversing a linked list involves visiting each node in the list, starting from the head and following the next pointers until reaching the end (NULL).
#include <stdio.h>
struct Node {
int data;
struct Node* next;
};
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
printList(head); // Output: NULL
return 0;
}
In this example, the printList function traverses the linked list and prints each node's data until the end of the list (NULL).
Linked lists are a powerful and flexible data structure in C that allow efficient insertion and deletion of elements. By understanding the structure of a linked list and how to perform basic operations like insertion, deletion, and traversal, you can efficiently work with dynamic data in your programs.