TASK NO: 2 A

TASK NAME : Linked List

PROBLEM TITLE: Singly Linked List: Operations in Ascending Order
AIM:
Design Develop and Implement the algorithm to perform the operation of sorting the elements in
ascending order using Singly Linked List ADT.

PROBLEM DESCRIPTION:
Sort the nodes of the given singly linked list in ascending order

ALGORITHM:
1. Create a class Node which has two attributes: data and next. Next is a pointer

to the next node in the list.

2. Create another class SortList which has two attributes: head and tail.

3. addNode() will add a new node to the list:

a. Create a new node.

b. It first checks, whether the head is equal to null which means the list is empty.
c. If the list is empty, both head and tail will point to a newly added node.
d. If the list is not empty, the new node will be added to end of the list such that tail's next
will point to a newly added node. This new node will become the new tail of the list.

4. sortList() will sort the nodes of the list in ascending order.

a. Define a node current which will point to head.

b. Define another node index which will point to node next to current.
c. Compare data of current and index node. If current's data is greater than the index's
data then, swap the data between them.
d. Current will point to current.next and index will point to index.next.
e. Continue this process until the entire list is sorted.

5. display() will display the nodes present in the list:

a. Define a node current which will initially point to the head of the list.
b. Traverse through the list till current points to null.
c. Display each node by making current to point to node next to it in each iteration.
Program
#include <stdio.h>
//Represent a node of the singly linked list
struct node{
int data;
struct node *next;
};
//Represent the head and tail of the singly linked list
struct node *head, *tail = NULL;
//addNode() will add a new node to the list
void addNode(int data) {
//Create a new node
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = NULL;
//Checks if the list is empty
if(head == NULL) {
//If list is empty, both head and tail will point to new node
head = newNode;
tail = newNode;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail->next = newNode;
//newNode will become new tail of the list
tail = newNode;
}
}
//sortList() will sort nodes of the list in ascending order
void sortList() {
//Node current will point to head
struct node *current = head, *index = NULL;
int temp;
if(head == NULL) {
return;
}
else {
while(current != NULL) {
//Node index will point to node next to current
index = current->next;
while(index != NULL) {
//If current node's data is greater than index's node data, swap the data between them
if(current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
 current = current->next;
}
}
}
//display() will display all the nodes present in the list
void display() {
//Node current will point to head
struct node *current = head;
if(head == NULL) {
printf("List is empty \n");
return;
}
while(current != NULL) {
//Prints each node by incrementing pointer
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main()
{
//Add data to the list
addNode(9);
addNode(7);
addNode(2);
addNode(5);
addNode(4);
//Displaying original list
printf("Original list: \n");
display();
//Sorting list
sortList();
//Displaying sorted list
printf("Sorted list: \n");
display();
return 0;
}

RESULT: Thus, the C program has been executed to sort the elements in singly linked list.

TASK NO: 2 B
 TASK NAME : Doubly Linked List

PROBLEM TITLE: Doubly Linked List: Get reversed in from the given order
AIM:
Design, Develop and Implement the algorithm to perform the operation reversing the elements in
Doubly Linked List ADT.
PROBLEM DESCRIPTION:
Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That
is, change the next and prev pointers of the nodes so that the direction of the list is reversed.

Note: The head node might be NULL to indicate that the list is empty.

ALGORITHM:
1. Create a function to reverse the linked list, which takes the head node as input.

2. Initialize three pointers: prevNode to NULL, currentNode to the head node, and
nextNode to NULL.
3. Traverse the linked list using a while loop until the currentNode pointer is not
NULL.
4. Inside the loop, assign nextNode as the next node of the currentNode using the next
pointer.

5. Set the next pointer of the currentNode to prevNode, effectively reversing the
pointer direction of the currentNode.
6. Update prevNode to the currentNode.

7. Update currentNode to the nextNode.

8. Finally, set the head node to prevNode and return it.

Program:
#include <stdio.h>
#include <stdlib.h>
/* a node of the doubly linked list */
struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
/* Function to reverse a Doubly Linked List */
void reverse(struct Node **head_ref)
{
struct Node *temp = NULL;
struct Node *current = *head_ref;
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
temp=temp->next;

}
if(temp != NULL )
*head_ref = temp->prev;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the Doubly Linked List */
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->prev = NULL;
new_node->next = (*head_ref);
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;
(*head_ref) = new_node;
}
/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked list */
void printList(struct Node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 2);
push(&head, 7);
push(&head, 1);
push(&head, 13);
push(&head, 17);
printf("\n Initial linked list before reversing: ");
printList(head);
reverse(&head);
printf("\n Resultant reversed linked list: ");
 printList(head);
getchar();
}

RESULT: Thus, the C program has been executed to reverse the elements in doubly linked list.
 TASK NO: 2 C
TASK NAME: Circular Linked List
PROBLEM TITLE: Circular Linked List: Choose the place in the end of the circle so that you
are the last one.
AIM: The aim of the program is to create a circular linked list and display its contents.
PROBLEM DESCRIPTION:
1. Create insertLast function which is used to insert a node at the end of the circular linked list.
If it is the first node being inserted, it becomes the head of the list. Otherwise, it is appended
after the current last node, and its next pointer is set to the head.
2. The display function is responsible for printing the contents of the circular linked list. It
traverses the list using a do-while loop and prints the data of each node until it reaches the
head again.
3. In the main function, a circular linked list is created by calling insertLast to add nodes with
values 0, 10, 20, 30, and 40 at the end of the list.
4. After creating the linked list, the display function is called to print its contents.
5. The program ensures proper memory deallocation by using a loop to free the memory
allocated for each node in the circular linked list. It starts from the head, stores the next node
in a temporary variable, frees the current node, and moves to the next node. The loop
continues until it reaches the last node, which is then freed separately. Finally, the head
pointer is set to NULL.
ALGORITHM:
1. Define the structure for a node in the circular linked list. Each node should have a data field
and a pointer to the next node.
2. Create a function insertLast that takes a double pointer to the head of the circular linked list
and an integer value to be inserted. This function performs the following steps:
• Allocate memory for a new node using malloc.
• Set the data of the new node to the given value.
• If the head is NULL, indicating an empty list, set the head to the new node and make
it circular by pointing its next to itself.
• If the list is not empty, traverse to the last node using a temporary pointer and make
the last node's next point to the new node.
• Make the new node's next point to the head, thus maintaining the circularity of the
linked list.
3. Create a function display that takes the head of the circular linked list as input. This function
performs the following steps:
• If the head is NULL, indicating an empty list, return.
 • Initialize a temporary pointer with the head.
• Traverse the circular linked list using a do-while loop, printing the data of each node
and moving to the next node until the pointer becomes equal to the head again.
4. In the main function:
• Declare a pointer to the head of the circular linked list and initialize it as NULL.
• Call insertLast function to insert nodes at the end of the linked list, providing the
address of the head pointer and the data values to be inserted.
• Call display function to print the contents of the circular linked list.
• Free the memory allocated for each node in the linked list by traversing it and using
free.
• Set the head to NULL to indicate an empty list.
5. Terminate the program.
Program:
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void insertLast (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
// if its the first node being entered
if (*head == NULL)
{
*head = newNode;
(*head)->next = *head;
return;
}
// if LL already as >=1 node
struct Node *curr = *head;
// traverse till last node in LL
while (curr->next != *head)
{
curr = curr->next;
temp=temp->next;
}
// assign LL's current last node's next as this new node
curr->next = newNode;
// assign this new node's next as current head of LL
newNode->next = *head;
 }
void display (struct Node *head)
{
// if there are no node in LL
if (head == NULL)
return;
struct Node *temp = head;
//need to take care of circular structure of LL
do
{
printf ("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
printf ("\n");
}
int main ()
{
struct Node *head = NULL;
int n,a[100];
printf("Enter the number of elements");
scanf("%d",&n);
printf("Enter the elements");
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
insertLast (&head, a[i]);
}
printf("The elements are");
display (head);
// Freeing the allocated memory
struct Node *current = head;
struct Node *next;
while (current != NULL && current->next != head) {
next = current->next;
free(current);
current = next;
}
free(current); // Free the last node
head = NULL; // Set head to NULL after deallocation
return 0;
}

RESULT:
Thus the program to create a circular linked list and display its contents are created and
executed successfully.