Singly linked list implementation
Singly Linked List Implementation
Aim
To implement basic operations on a Singly Linked List in C.
Objective
To study dynamic memory allocation using linked lists.
To perform Insert, Delete, Traverse operations.
To understand pointer manipulation in data structures.
Operations in Singly Linked List
Insert at Beginning
Insert at End
Insert at Position
Delete from Beginning
Delete from End
Delete from Position
Display List
Algorithm
Insert at Beginning
Create new node.
new->next = head.
head = new.
Insert at End
Create new node.
If list empty → head = new.
Else traverse to last node, set last->next = new.
Insert at Position
Traverse until position-1.
Link new node in between.
Delete from Beginning
If empty → print "Underflow".
Else move head to head->next, free old head.
Delete from End
If empty → print "Underflow".
Else traverse to last-1 node, set last->next = NULL, free last.
Delete from Position
Traverse until position-1.
Adjust links and free node.
Display
Traverse from head to NULL.
Print each node’s data.
Flowchart
C Code (Singly Linked List Implementation)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
int main() {
struct Node* head = NULL;
struct Node* temp;
struct Node* newNode;
int choice, item, pos, i;
while (1) {
printf("\n--- Singly Linked List Menu ---\n");
printf("1. Insert at Beginning\n");
printf("2. Insert at End\n");
printf("3. Insert at Position\n");
printf("4. Delete from Beginning\n");
printf("5. Delete from End\n");
printf("6. Delete from Position\n");
printf("7. Display\n");
printf("8. Exit\n");
printf("Enter choice: ");
scanf("%d", &choice);
if (choice == 1) { // Insert at Beginning
printf("Enter data: ");
scanf("%d", &item);
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = item;
newNode->next = head;
head = newNode;
}
else if (choice == 2) { // Insert at End
printf("Enter data: ");
scanf("%d", &item);
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = item;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
} else {
temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
}
else if (choice == 3) { // Insert at Position
printf("Enter position: ");
scanf("%d", &pos);
printf("Enter data: ");
scanf("%d", &item);
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = item;
if (pos == 1) {
newNode->next = head;
head = newNode;
} else {
temp = head;
for (i = 1; i < pos - 1 && temp != NULL; i++)
temp = temp->next;
if (temp == NULL)
printf("Invalid position!\n");
else {
newNode->next = temp->next;
temp->next = newNode;
}
}
}
else if (choice == 4) { // Delete from Beginning
if (head == NULL)
printf("List is empty!\n");
else {
temp = head;
head = head->next;
printf("Deleted: %d\n", temp->data);
free(temp);
}
}
else if (choice == 5) { // Delete from End
if (head == NULL)
printf("List is empty!\n");
else if (head->next == NULL) {
printf("Deleted: %d\n", head->data);
free(head);
head = NULL;
} else {
temp = head;
while (temp->next->next != NULL)
temp = temp->next;
printf("Deleted: %d\n", temp->next->data);
free(temp->next);
temp->next = NULL;
}
}
else if (choice == 6) { // Delete from Position
printf("Enter position: ");
scanf("%d", &pos);
if (head == NULL) {
printf("List is empty!\n");
} else if (pos == 1) {
temp = head;
head = head->next;
printf("Deleted: %d\n", temp->data);
free(temp);
} else {
struct Node* prev = head;
for (i = 1; i < pos - 1 && prev != NULL; i++)
prev = prev->next;
if (prev == NULL || prev->next == NULL) {
printf("Invalid position!\n");
} else {
temp = prev->next;
prev->next = temp->next;
printf("Deleted: %d\n", temp->data);
free(temp);
}
}
}
else if (choice == 7) { // Display
if (head == NULL)
printf("List is empty!\n");
else {
printf("List elements: ");
temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}
else if (choice == 8) {
printf("Exiting...\n");
break;
}
else {
printf("Invalid choice!\n");
}
}
return 0;
}
Comments
Post a Comment