Linked Lists in C
Introduction
A linked list is a linear data structure where each element is a separate object. Each element (commonly called a node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null indicating the end of the list.
Types of Linked Lists
There are several types of linked lists:
- Singly Linked List: Each node contains a single link to the next node.
- Doubly Linked List: Each node contains two links, one to the next node and one to the previous node.
- Circular Linked List: Last node contains a link to the first node.
Singly Linked List
In a singly linked list, each node contains a single link to the next node in the sequence.
Example Code
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
// Function to print linked list
void printList(struct Node* n) {
while (n != NULL) {
printf("%d ", n->data);
n = n->next;
}
}
int main() {
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// Allocate 3 nodes in the heap
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1; // Assign data in first node
head->next = second; // Link first node with the second node
second->data = 2; // Assign data to second node
second->next = third; // Link second node with the third node
third->data = 3; // Assign data to third node
third->next = NULL; // End the list at the third node
printList(head);
return 0;
}
Output:
1 2 3
Insertion in Linked List
Insertion in linked list can be done at the beginning, at the end, or at any given position in the linked list.
Insert at Beginning
void push(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
Insert at End
void append(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node *last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
return;
}
Deletion in Linked List
Deletion in a linked list can be done by key or by position.
Delete by Key
void deleteNode(struct Node **head_ref, int key) {
struct Node* temp = *head_ref, *prev;
if (temp != NULL && temp->data == key) {
*head_ref = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
Delete by Position
void deleteNodeAtPosition(struct Node** head_ref, int position) {
if (*head_ref == NULL) return;
struct Node* temp = *head_ref;
if (position == 0) {
*head_ref = temp->next;
free(temp);
return;
}
for (int i = 0; temp != NULL && i < position-1; i++) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) return;
struct Node* next = temp->next->next;
free(temp->next);
temp->next = next;
}
Doubly Linked List
In a doubly linked list, each node contains two links: one to the next node and another to the previous node.
Example Code
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void printList(struct Node* node) {
struct Node* last;
printf("Traversal in forward direction: ");
while (node != NULL) {
printf("%d ", node->data);
last = node;
node = node->next;
}
printf("\nTraversal in reverse direction: ");
while (last != NULL) {
printf("%d ", last->data);
last = last->prev;
}
}
void push(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
if ((*head_ref) != NULL) {
(*head_ref)->prev = new_node;
}
(*head_ref) = new_node;
}
int main() {
struct Node* head = NULL;
push(&head, 2);
push(&head, 4);
push(&head, 8);
printList(head);
return 0;
}
Output:
Traversal in forward direction: 8 4 2 Traversal in reverse direction: 2 4 8
Circular Linked List
In a circular linked list, the last node points to the first node, thus forming a circular structure.
Example Code
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void printList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
}
void push(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node* temp = *head_ref;
new_node->data = new_data;
new_node->next = *head_ref;
if (*head_ref != NULL) {
while (temp->next != *head_ref) {
temp = temp->next;
}
temp->next = new_node;
} else {
new_node->next = new_node;
}
*head_ref = new_node;
}
int main() {
struct Node* head = NULL;
push(&head, 2);
push(&head, 4);
push(&head, 8);
printList(head);
return 0;
}
Output:
8 4 2