linked-list-using-C-Data-Structure
admin
#linked-list-using-C-Data-Structure
A linked list is a linear data structure where elements are not stored in contiguous memory locations, unlike arrays. Instead, each element in a linked list, called a node, contains data and a pointer to the next node in the sequence. This dynamic nature of linked lists makes them highly efficient for certain operations, such as insertion and deletion.
In this article, we’ll explore the basics of linked lists, discuss their types, and walk through C programs to implement both singly and circular linked lists.
Below is an implementation of a singly linked list, covering operations such as insertion, traversal, searching, and deletion.
#include <stdio.h>
#include <stdlib.h>
// Define the structure of a node
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
// Function to insert a new node at the end
void insert(int value) {
struct node *newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
} else {
struct node *temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
printf("Node with value %d inserted.\n", value);
}
// Function to traverse and print the linked list
void traverse() {
if (head == NULL) {
printf("The linked list is empty.\n");
return;
}
struct node *temp = head;
printf("Linked list elements: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// Function to search for a value in the linked list
void search(int value) {
struct node *temp = head;
while (temp != NULL) {
if (temp->data == value) {
printf("Value %d found in the linked list.\n", value);
return;
}
temp = temp->next;
}
printf("Value %d not found in the linked list.\n", value);
}
// Function to delete a node with a specific value
void delete(int value) {
struct node *temp = head, *prev = NULL;
if (temp != NULL && temp->data == value) {
head = temp->next;
free(temp);
printf("Node with value %d deleted.\n", value);
return;
}
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Value %d not found in the linked list.\n", value);
return;
}
prev->next = temp->next;
free(temp);
printf("Node with value %d deleted.\n", value);
}
// Main function
int main() {
int choice, value;
do {
printf("\nMenu:");
printf("\n1. Insert");
printf("\n2. Traverse");
printf("\n3. Search");
printf("\n4. Delete");
printf("\n0. Exit");
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
insert(value);
break;
case 2:
traverse();
break;
case 3:
printf("Enter value to search: ");
scanf("%d", &value);
search(value);
break;
case 4:
printf("Enter value to delete: ");
scanf("%d", &value);
delete(value);
break;
case 0:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice! Please try again.\n");
}
} while (choice != 0);
return 0;
}
Understanding Circular Linked Lists in C: Code Implementation and Key Concepts
Circular linked lists are a type of linked list where the last node points back to the first node, creating a circular structure. Unlike linear linked lists, where the last node points to NULL
, circular linked lists provide more flexibility in traversing nodes and managing memory efficiently.
next
pointer connects back to the first node, forming a continuous loop.NULL
pointer.NULL
to signify the end of the list; instead, the loop continues until a specific condition is met.Below is a comprehensive implementation of a circular linked list in C:
#include<stdio.h>
#include<alloc.h>
#include<conio.h>
struct node {
int no;
struct node *next;
};
struct node *start = NULL;
void append() {
struct node *p = start, *n;
n = (struct node *)malloc(sizeof(struct node));
printf("\nEnter no: ");
scanf("%d", &n->no);
n->next = NULL;
if (start == NULL) {
start = n;
start->next = start;
return;
}
while (p->next != start) {
p = p->next;
}
p->next = n;
n->next = start;
}
void traverse(struct node *q) {
struct node *r = q;
if (q == NULL) {
printf("\nList is empty");
return;
}
do {
printf(" %d", q->no);
q = q->next;
} while (q != r);
}
void tra_f_node(struct node *p) {
int val;
if (p == NULL) {
printf("\nList is empty");
return;
}
printf("\nEnter No from Which you want to search:");
scanf("%d", &val);
do {
if (val == p->no) {
traverse(p);
return;
}
p = p->next;
} while (p != start);
printf("\n%d Not Found", val);
}
void search() {
struct node *p = start;
int val;
if (p == NULL) {
printf("\nList is empty");
return;
}
printf("\nEnter element to be searched: ");
scanf("%d", &val);
do {
if (val == p->no) {
printf("\nElement found");
return;
}
p = p->next;
} while (p != start);
printf("\nElement not found");
}
void del_all() {
struct node *p;
if (start == NULL) {
printf("\nList is already empty");
return;
}
do {
p = start;
start = start->next;
free(p);
} while (start != p);
start = NULL;
}
void main() {
int ch;
do {
clrscr();
printf("\n1. Append\n2. Traverse\n3. Search\n4. Exit\nEnter your choice: ");
scanf("%d", &ch);
switch (ch) {
case 1:
append();
break;
case 2:
traverse(start);
break;
case 3:
search();
break;
case 4:
del_all();
printf("\nExiting...");
break;
default:
printf("\nInvalid choice");
}
printf("\nPress any key to continue...");
getch();
} while (ch != 4);
}
Linked lists are a fundamental data structure in computer science, offering dynamic memory management and efficient operations. The implementation of both singly linked lists and circular linked lists in C showcases how we can use pointers and structures to handle data flexibly.
By mastering linked lists, developers can efficiently handle complex data structures, making them invaluable in competitive programming and real-world applications.