WEEK 3

3. a) Detecting and Removing Duplicate Elements from a Linked List

Aim: To detect and remove duplicate elements from a linked list.

Description: To detect and remove duplicate elements from a linked list, there are two main
approaches: a time-efficient approach using a hash set for an unsorted list, or a space-efficient
approach for a sorted list that compares adjacent nodes. The hash set is represented by a simple
fixed-size array to store unique data values. As it traverses the linked list, if a data value is
already in the set, the node is deleted and it is removed from a linked list.

Processing Steps:

1. struct Node: Defines the basic unit of the linked list.

2. createNode: A utility function to allocate memory for a new node and initialize it.
3. printList: A utility function to traverse and print the list elements.
4. removeDuplicates:
1. It uses a boolean array seen[] as a simple hash set.
2. It iterates through the list with a current pointer and keeps track of the previous node.
3. If the current node's data has been seen before, it is a duplicate. The code
updates previous->next to skip the current node and then frees the memory of the
duplicate.
4. If the data is unique, it marks the value as true in the seen array and moves
both previous and current pointers forward.

Source Code:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Define the structure for a linked list node
typedef struct Node
{
int data;
struct Node* next;
} Node;
// Function to create a new node
Node* createNode(int data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode)
{
 printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to print the linked list
void printList(Node* head)
{
Node* current = head;
while (current != NULL)
{
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// Function to remove duplicates using a hash set
void removeDuplicates(Node* head)
{
if (head == NULL)
{
return;
}
// A simple fixed-size array to act as a hash set (assuming data values are within range 0-99)
// For more robust solutions, use an actual hash map library or dynamic array.
bool seen[100] = {false};
Node* current = head;
Node* previous = NULL;
while (current != NULL)
{
// If the data is already seen (is a duplicate)
if (seen[current->data]) {
// Bypass the current node
previous->next = current->next;
// Free the duplicate node
free(current);
// Move current to the next node (previous remains the same)
current = previous->next;
}
else
{
// Mark the data as seen
seen[current->data] = true;
// Move pointers normally
previous = current;
 current = current->next;
}
}
}
int main()
{
// Create the linked list: 10 -> 20 -> 10 -> 30 -> 20 -> NULL
Node* head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(10);
head->next->next->next = createNode(30);
head->next->next->next->next = createNode(20);
printf("Original list: ");
printList(head);
removeDuplicates(head);
printf("List after removing duplicates: ");
printList(head);
// Free allocated memory (omitted for brevity, as the program ends immediately)
return 0;
}
Test Data:
Original list: 10 -> 20 -> 10 -> 30 -> 20 -> NULL
List after removing duplicates: 10 -> 20 -> 30 -> NULL
Result: The C program was successfully implemented to detect and remove duplicate elements
from a linked list.

3. b) Addition of Two Polynomials using Linked List

Aim: To perform the addition of two polynomials using linked list.

Description: Implementing a linked list to represent polynomials involves creating a structure

for a term (coefficient and exponent) and linking these terms together. Addition is performed by
traversing both lists and combining like terms.

Processing Steps:
struct Node: Represents a single term in the polynomial, storing
its coefficient, exponent, and a pointer (next) to the subsequent term.
createNode: A utility function to allocate memory for a new node and initialize its
values.
 insertTerm: This function manages adding a term to the linked list while maintaining the
order by exponent (descending). It also handles combining terms with the same exponent
and removing terms that become zero. This is crucial for keeping the polynomial in a
standard, simplified form.
addPolynomials: This function takes two polynomial heads as input. It iterates through
both input lists and inserts every term into a new result list using the insertTerm function,
which automatically handles the logic for combining like terms.
printPolynomial: A function to display the polynomial in a readable mathematical
format.

Source Code:
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a polynomial term (node)
typedef struct Node
{
int coefficient;
int exponent;
struct Node* next;
} Node;
// Function to create a new node
Node* createNode(int coeff, int exp)
{
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL)
{
printf("Memory allocation failed\n");
exit(1);
}
newNode->coefficient = coeff;
newNode->exponent = exp;
newNode->next = NULL;
return newNode;
}
// Function to insert a term into a polynomial (sorted by exponent, descending)
Node* insertTerm(Node* head, int coeff, int exp)
{
if (coeff == 0) return head; // Don't insert zero terms
Node* newNode = createNode(coeff, exp);
// If the list is empty or the new exponent is greater than the head's
if (head == NULL || exp > head->exponent)
{
 newNode->next = head;
return newNode;
}
Node* current = head;
// Find the correct position to insert the new node
while (current->next != NULL && current->next->exponent >= exp)
{
// If an existing term has the same exponent, just add the coefficient
if (current->next->exponent == exp)
{
current->next->coefficient += coeff;
// If the resulting coefficient is zero, remove the term
if (current->next->coefficient == 0)
{
Node* temp = current->next;
current->next = temp->next;
free(temp);
}
free(newNode); // Don't need the new node anymore
return head;
}
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
return head;
}
// Function to add two polynomials
Node* addPolynomials(Node* poly1, Node* poly2)
{
Node* result = NULL;
Node* current1 = poly1;
Node* current2 = poly2;
// Traverse both lists and add terms to the result list
while (current1 != NULL)
{
result = insertTerm(result, current1->coefficient, current1->exponent);
current1 = current1->next;
}
while (current2 != NULL)
{
result = insertTerm(result, current2->coefficient, current2->exponent);
current2 = current2->next;
}

return result;
}
// Function to print a polynomial
void printPolynomial(Node* head)
{
if (head == NULL)
{
printf("0\n");
return;
}
Node* current = head;
while (current != NULL)
{
printf("%dx^%d", current->coefficient, current->exponent);
current = current->next;
if (current != NULL)
{
if (current->coefficient >= 0)
{
printf(" + ");
} else {
printf(" ");
}
}
}
printf("\n");
}

// Main function to demonstrate the implementation

int main()
{
Node* poly1 = NULL;
Node* poly2 = NULL;
Node* polySum = NULL;
// Create the first polynomial: 5x^3 + 2x^2 + 4
poly1 = insertTerm(poly1, 5, 3);
poly1 = insertTerm(poly1, 2, 2);
poly1 = insertTerm(poly1, 4, 0);
printf("Polynomial 1: ");
printPolynomial(poly1);
// Create the second polynomial: 3x^3 + 1x^2 - 1x^1 + 5
poly2 = insertTerm(poly2, 3, 3);
poly2 = insertTerm(poly2, 1, 2);
poly2 = insertTerm(poly2, -1, 1);
poly2 = insertTerm(poly2, 5, 0);
printf("Polynomial 2: ");
printPolynomial(poly2);
 // Add the two polynomials
polySum = addPolynomials(poly1, poly2);
printf("Sum of Polynomials: ");
printPolynomial(polySum);
// Free allocated memory (important for C)
// A proper free function should be implemented for linked lists.
// ...
return 0;
}
Test Data:
Polynomial 1: 5x^3 + 2x^2 + 4x^0

Polynomial 2: 3x^3 + 1x^2 -1x^1 + 5x^0

Sum of Polynomials: 5x^3 + 3x^3 + 3x^2 -1x^1 + 9x^0

Result: The C program was successfully implemented to perform the addition of two
polynomials using linked list.

3. c) Implementing Double-ended Queue (deque) with essential operations

Aim: To implement double-ended queue (deque) with essential operations.

Description: A deque (double-ended queue) can be implemented using either a circular array
or a doubly linked list to allow for constant time insertion and deletion at both ends. The deque is
implemented using a struct for list nodes and functions for essential deque operations:
initialization, insertion/deletion at both front and rear, checking if empty, and displaying
elements.
Processing Steps:
The processing steps involve managing two pointers, front and rear, and handling conditions
such as empty or full states for each operation.

1. Declare an array (for array-based implementation) of a fixed size, say n.

2. Initialize two pointers: front = -1 and rear = -1 (or rear = 0 in some implementations) to
indicate the deque is initially empty.
3. The main operations on a deque are insertion and deletion at both ends.
Source Code:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Structure for a deque node
typedef struct DequeNode
{
int data;
struct DequeNode *next;
struct DequeNode *prev;
} DequeNode;
// Structure for the deque itself
typedef struct Deque
{
DequeNode *front;
DequeNode *rear;
} Deque;
// Function to create a new deque
Deque* createDeque()
{
Deque *dq = (Deque*)malloc(sizeof(Deque));
if (!dq)
{
printf("Memory allocation failed!\n");
exit(EXIT_FAILURE);
}
dq->front = NULL;
dq->rear = NULL;
return dq;
}
// Function to check if the deque is empty
bool isEmpty(Deque *dq)
{
return dq->front == NULL;
}
// Function to add an element to the front of the deque
void insertFront(Deque *dq, int data)
{
DequeNode *newNode = (DequeNode*)malloc(sizeof(DequeNode));
if (!newNode)
{
printf("Memory allocation failed!\n");
exit(EXIT_FAILURE);
}
newNode->data = data;
 newNode->next = dq->front;
newNode->prev = NULL;
if (isEmpty(dq))
{
dq->front = newNode;
dq->rear = newNode;
}
else
{
dq->front->prev = newNode;
dq->front = newNode;
}
printf("Inserted %d at front\n", data);
}
// Function to add an element to the rear of the deque
void insertRear(Deque *dq, int data)
{
DequeNode *newNode = (DequeNode*)malloc(sizeof(DequeNode));
if (!newNode)
{
printf("Memory allocation failed!\n");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = dq->rear;

if (isEmpty(dq))
{
dq->front = newNode;
dq->rear = newNode;
}
else
{
dq->rear->next = newNode;
dq->rear = newNode;
}
printf("Inserted %d at rear\n", data);
}
// Function to delete an element from the front of the deque
void deleteFront(Deque *dq)
{
if (isEmpty(dq))
{
printf("Deque is empty, cannot delete from front\n");
return;
 }
DequeNode *temp = dq->front;
dq->front = dq->front->next;
if (dq->front == NULL)
{
dq->rear = NULL;
} else {
dq->front->prev = NULL;
}
printf("Deleted %d from front\n", temp->data);
free(temp);
}
// Function to delete an element from the rear of the deque
void deleteRear(Deque *dq)
{
if (isEmpty(dq))
{
printf("Deque is empty, cannot delete from rear\n");
return;
}
DequeNode *temp = dq->rear;
dq->rear = dq->rear->prev;

if (dq->rear == NULL)
{
dq->front = NULL;
} else {
dq->rear->next = NULL;
}
printf("Deleted %d from rear\n", temp->data);
free(temp);
}
// Function to display the elements in the deque (from front to rear)
void displayDeque(Deque *dq)
{
if (isEmpty(dq))
{
printf("Deque is empty\n");
return;
}
DequeNode *current = dq->front;
printf("Deque elements: ");
while (current != NULL)
{
printf("%d ", current->data);
current = current->next;
 }
printf("\n");
}
// Main function to demonstrate the deque operations
int main()
{
Deque *dq = createDeque();
insertRear(dq, 5);
insertFront(dq, 10);
insertRear(dq, 15);
insertFront(dq, 20);
displayDeque(dq); // Expected: 20 10 5 15
deleteFront(dq); // Deletes 20
deleteRear(dq); // Deletes 15
displayDeque(dq); // Expected: 10 5
deleteFront(dq); // Deletes 10
deleteRear(dq); // Deletes 5
displayDeque(dq); // Expected: Deque is empty
insertFront(dq, 99);
displayDeque(dq); // Expected: 99
// Remember to free the deque structure itself and any remaining nodes if needed for a
production environment.
// For this example, we will just exit.
return 0;
}

Test Data:
Inserted 5 at rear
Inserted 10 at front
Inserted 15 at rear
Inserted 20 at front
Deque elements: 20 10 5 15
Deleted 20 from front
Deleted 15 from rear
Deque elements: 10 5
Deleted 10 from front
Deleted 5 from rear
Deque is empty
Inserted 99 at front
Deque elements: 99

Result: The C program was successfully implemented double-ended queue (deque) with
essential operations.