What is linked list?
A collection of nodes, each node contains two parts, an data part and an link part.
Data part:- data part of a linked list contains the data to be stored in linked list.
Link part:- which contains the address of the next node. In the case of the current node is only node in the list or current node is last node in the list then address part contains NULL value in it.
Such a linked allocation based structure is called Linked list.
Types of linked list:-
There are 3 types of linked list.
1. Single Linked List (SLL).
2. Circular Linked List (CLL).
3. Double Linked List (DLL).
Some basic algorithms:
1.Design an algorithm to insert an element 'e' into a single linked list (SLL). So that the inserted element becomes first in the list.
Algorithm:- Insert_First_SLL.
Input:- F, address of first node of SLL.
e, element to be inserted.
Output:- F, updated.
Method:-
n = CreateNode();
n.data = e;
n.link = F;
F = n;
Algorithm ends
2. Design an algorithm to delete the very first node from a single linked list (SLL).
Algorithm:- Delete_First_SLL.
Input:- F, address of first node of SLL.
Output:- F, updated.
Method:-
if(F == NULL) then
print ("Empty list, No deletion");
else
Temp = F;
F = F.link;
Dispose(T);
if ends
Algorithm ends
3. Design an algorithm to insert a data element into a SLL such that inserted element becomes last in the list.
Algorithm:- Insert_last_SLL.
Input:- F, address of first node.
e, element to insert.
Output:- F, updated.
Method:-
n = CreateNode();
n.data = e;
n.link = NULL;
if(F ==NULL) then
F = n;
else
Temp = F;
while(Temp.link != NULL) do
Temp = Temp.link;
while end
Temp.link = n
Algorithm ends
4. Design an algorithm to delete the last element from a SLL.
Algorithm:- Delete_Last_SLL.
Input:- F, address of first node.
Output:- F, updated.
Method:-
if(F = = NULL) then
print("empty list, no deletion");
else
if(F.link == NULL) then
F = NULL;
else
Temp = F;
While( Temp.link.link != NULL) do
Temp = Temp.link;
while ends
Temp.link = NULL
if ends
if ends
Algorithm ends
All the above algorithms are implemented using c programming language.
#include <stdio.h>
#include <stdlib.h>
// Structure of a node
struct Node {
int data; // Data
struct Node* link; // Address
} *F, *T;
// Function to create a list of n nodes
void createList(int n) {
struct Node* newNode, * temp;
int data, i;
F = (struct Node*)malloc(sizeof(struct Node));
if (F == NULL) {
printf("Unable to allocate memory.\n");
return;
}
printf("Enter data for node 1: ");
scanf("%d", &data);
F->data = data;
F->link = NULL;
temp = F;
for (i = 2; i <= n; i++) {
newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Unable to allocate memory.\n");
break;
}
printf("Enter data for node %d: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->link = NULL;
temp->link = newNode;
temp = newNode;
}
}
// Function to insert a node at the beginning
void insertNodeAtBeginning(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Unable to allocate memory.\n");
return;
}
newNode->data = data;
newNode->link = F;
F = newNode;
printf("\nData in the list after Beginning insertion:\n");
displayList();
}
void insertNodeAtEnding(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Unable to allocate memory.\n");
return;
}
newNode->data = data;
newNode->link = NULL;
if(F == NULL)
F = newNode;
else
T=F;
while(T->link!=NULL)
T=T->link;
T->link = newNode;
printf("\nData in the list after End insertion:\n");
displayList();
}
void deleteNodeAtBeginning(int data) {
if(F == NULL)
printf("List is empty, deletion is not possible");
else
{
T = F;
F=F->link;
free(T);
}
printf("\nData in the list after Beginning deletion:\n");
displayList();
}
void deleteNodeAtEnding(int data) {
//struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if(F == NULL)
printf("List is empty, deletion is not possible");
else
if(F->link == NULL)
{
F->link = NULL;
}
else
{
T=F;
while(T->link->link != NULL)
{
T = T->link;
}
T->link = NULL;
}
printf("\nData in the list after Ending deletion:\n");
displayList();
}
// Function to display the list
void displayList() {
struct Node* temp = F;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->link;
}
printf("NULL\n");
}
int main() {
int n, data;
printf("Enter the total number of nodes: ");
scanf("%d", &n);
createList(n);
printf("\nData in the list:\n");
displayList();
printf("\nEnter data to insert at the beginning of the list: ");
scanf("%d", &data);
insertNodeAtBeginning(data);
printf("\nEnter data to insert at the Ending of the list: ");
scanf("%d", &data);
insertNodeAtEnding(data);
deleteNodeAtBeginning(data);
deleteNodeAtEnding(data);
return 0;
}
Sample Output of the above Program:
