A linked list is a linear data structure where elements, called nodes, are connected using pointers. Each node contains data and a pointer to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory, which allows dynamic memory allocation and easy insertion or deletion of elements. Linked lists are fundamental in data structures, forming the basis for stacks, queues, and more advanced structures.
with hands-on learning.
get the skills and confidence to land your next move.
Understanding the Problem
The main challenge in implementing a linked list is managing pointers correctly. Operations such as insertion, deletion, and traversal must carefully adjust the next pointers to maintain the structure. Additionally, memory management is crucial—nodes must be allocated dynamically and freed after deletion to avoid memory leaks. Proper implementation ensures that the list remains intact during all operations.
Program 1: Singly Linked List with Insertion and Display
This program demonstrates the basic operations of a singly linked list: inserting nodes at the end and displaying the list. Each node contains an integer data and a pointer to the next node.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
head = newNode;
} else {
Node *temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
printf("%d inserted at end\n", value);
}
void display() {
if (!head) {
printf("Linked List is empty\n");
return;
}
Node *temp = head;
printf("Linked List: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
insertEnd(10);
insertEnd(20);
insertEnd(30);
display();
return 0;
}In this program, insertEnd dynamically allocates memory for new nodes and appends them to the end of the list. The display function traverses the list from head to NULL, printing each node’s data.
Program 2: Insertion at Beginning and Specific Position
Linked lists allow insertion at any position. This program demonstrates inserting a node at the beginning and at a specific position.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
head = newNode;
} else {
Node *temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
printf("%d inserted at end\n", value);
}
void insertBeginning(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = head;
head = newNode;
printf("%d inserted at beginning\n", value);
}
void insertAtPosition(int value, int pos) {
if (pos == 1) {
insertBeginning(value);
return;
}
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
Node *temp = head;
for (int i = 1; i < pos - 1 && temp; i++) {
temp = temp->next;
}
if (!temp) {
printf("Position out of bounds\n");
free(newNode);
return;
}
newNode->next = temp->next;
temp->next = newNode;
printf("%d inserted at position %d\n", value, pos);
}
void display() {
Node *temp = head;
if (!temp) {
printf("Linked List is empty\n");
return;
}
printf("Linked List: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
insertBeginning(10);
insertEnd(20);
insertAtPosition(15, 2);
display();
return 0;
}In this program, inserting at the beginning updates head to the new node, while insertion at a specific position requires traversing to the node before the target position.
Program 3: Deletion from Beginning – End and Specific Position
Deletion is another key operation. This program shows how to remove nodes from the beginning, end, and any given position.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *head = NULL;
void insertEnd(int value) {
Node *newNode = (Node*) malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!head) {
head = newNode;
} else {
Node *temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
printf("%d inserted at end\n", value);
}
void deleteBeginning() {
if (!head) {
printf("List is empty\n");
return;
}
Node *temp = head;
head = head->next;
printf("%d deleted from beginning\n", temp->data);
free(temp);
}
void deleteEnd() {
if (!head) {
printf("List is empty\n");
return;
}
if (!head->next) {
printf("%d deleted from end\n", head->data);
free(head);
head = NULL;
return;
}
Node *temp = head;
while (temp->next->next) {
temp = temp->next;
}
printf("%d deleted from end\n", temp->next->data);
free(temp->next);
temp->next = NULL;
}
void deleteAtPosition(int pos) {
if (!head) {
printf("List is empty\n");
return;
}
if (pos == 1) {
deleteBeginning();
return;
}
Node *temp = head;
for (int i = 1; i < pos - 1 && temp->next; i++) {
temp = temp->next;
}
if (!temp->next) {
printf("Position out of bounds\n");
return;
}
Node *del = temp->next;
temp->next = del->next;
printf("%d deleted from position %d\n", del->data, pos);
free(del);
}
void display() {
Node *temp = head;
if (!temp) {
printf("List is empty\n");
return;
}
printf("Linked List: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
insertEnd(10);
insertEnd(20);
insertEnd(30);
display();
deleteBeginning();
display();
deleteEnd();
display();
deleteAtPosition(2);
display();
return 0;
}Here, deletion requires careful pointer updates to avoid breaking the list or causing memory leaks.
FAQs
Q1: What is the time complexity of insertion and deletion?
Insertion and deletion at the beginning are O(1), while at a specific position or end, they are O(n).
Q2: Can a linked list contain duplicate elements?
Yes, linked lists can store duplicate values.
Q3: What is the difference between an array and linked list?
Arrays require contiguous memory and fixed size, while linked lists use dynamic memory and can grow or shrink.
Q4: What are applications of linked lists?
Linked lists are used in stacks, queues, deques, adjacency lists for graphs, and memory management.
Conclusion
Linked lists are flexible and fundamental data structures that support dynamic memory allocation, allowing efficient insertion and deletion at various positions. Mastering linked lists is essential for understanding advanced structures such as stacks, queues, and graphs. Proper pointer management and memory handling are crucial for safe operations.
References & Additional Resources
A curated set of textbooks and tutorials for mastering singly linked lists, memory management, and related operations in C.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – The classic reference for C programming, covering pointers and dynamic memory, which are core to linked list implementations.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of linked lists, including insertion, deletion, and traversal operations.
- GeeksforGeeks: Singly Linked List in C – Implementation examples of singly linked lists with step-by-step explanation.
- Programiz: Linked List Operations – Beginner-friendly guide on linked list basics and operations in C.
- Tutorialspoint: What is Dynamic Memory Allocation in C? – Overview of
malloc(),calloc(),realloc(), andfree()functions, essential for linked list management. - C Standard Library Documentation – Official reference for memory management functions used in dynamic data structures.
