Assign
ment
Name: Harshit Choudhary
Roll No.: 241030093
Batch: 24A18
Q1. Form a list containing the UNION of the elements of two lists (singly
linked list).
def union(list1, list2):
result = set(list1) for
item in list2:
result.add(item)
return list(result)
Q2. Form a list containing the INTERSECTION of the elements of two lists
(singly linked list).
def intersection(list1, list2):
set1 = set(list1) set2 =
set(list2) return
list(set1.intersection(set2))
Q3. Insert an element after the nth element of a list (singly linked list).
class Node: def
__init__(self, data):
self.data = data
self.next = None
def insert_after_nth(head, n, data):
current = head count = 1
while count < n and current:
current = current.next
count += 1
if current:
new_node = Node(data)
new_node.next = current.next
current.next = new_node
Assign
ment
Q4. Place the elements of a list in increasing order (singly linked list).
def sort_linked_list(head):
values = []
current = head
while current:
values.append(current.data)
current = current.next
values.sort() current = head
for value in values:
current.data = value current
= current.next
Q5. Return the number of elements in a list (singly linked list).
def count_nodes(head):
count = 0
current = head while
current: count += 1
current = current.next
return count
Q6. Return the sum of integers in a list (doubly linked list).
class DoublyNode: def
__init__(self, data):
self.data = data
self.next = None
self.prev = None
def sum_doubly_linked_list(head):
total = 0
current = head
while current:
total += current.data
current = current.next return
total
Q7. Concatenate two lists (circular singly linked list).
Assign
ment
def concatenate_circular_lists(list1, list2):
if not list1: return list2 if not list2:
return list1 temp = list1 while
temp.next != list1: temp = temp.next
temp.next = list2 temp2 = list2 while
temp2.next != list2: temp2 =
temp2.next temp2.next = list1 return
list1
Q8. Move node (p) forward n positions in the list (circular doubly linked
list).
def move_node_forward(head, node, n):
current = head while current
and current != node:
current = current.next
if not current:
return for _
in range(n):
current = current.next node.data,
current.data = current.data, node.data
Q9. Recursive function to find the number of nodes in a linked list (singly
linked list).
def count_nodes_recursive(node):
if not node: return 0
return 1 + count_nodes_recursive(node.next)
Q10. Addition of long positive integers using circular lists.
def add_long_integers(list1, list2):
result = [] carry = 0
while list1 or list2 or carry:
digit1 = list1.pop() if list1
else 0 digit2 =
list2.pop() if list2 else 0
total = digit1 + digit2 + carry
carry = total // 10
result.append(total % 10)
result.reverse() return
result
Assign
ment
Q11. Addition of long integers using doubly linked lists.
def add_doubly_linked_lists(head1, head2):
stack1, stack2 = [], [] while head1:
stack1.append(head1.data)
head1 = head1.next while
head2:
stack2.append(head2.data)
head2 = head2.next carry = 0
result = None while stack1 or
stack2 or carry:
digit1 = stack1.pop() if stack1 else 0
digit2 = stack2.pop() if stack2 else 0
total = digit1 + digit2 + carry carry =
total // 10 new_node =
DoublyNode(total % 10)
new_node.next = result if result:
result.prev = new_node
result = new_node return
result
Q12. Represent polynomial in three variables (x, y, and z) using a circular
list.
class PolynomialNode: def
__init__(self, coefficient, x, y, z):
self.coefficient = coefficient
self.x = x self.y = y
self.z = z self.next = None
def create_polynomial(coefficients):
head = None for coef, x, y,
z in coefficients:
new_node = PolynomialNode(coef, x, y, z)
if not head:
head = new_node
head.next = head else:
temp = head
while temp.next != head:
temp = temp.next
temp.next = new_node
Assign
ment
new_node.next = head return
head
Q13. Add two polynomials (singly linked list).
def add_polynomials(poly1, poly2): result = PolynomialNode(0, 0, 0,
0) current = result while poly1 and poly2: if poly1.x == poly2.x
and poly1.y == poly2.y and poly1.z == poly2.z:
current.next = PolynomialNode(poly1.coefficient + poly2.coefficient, poly1.x, poly1.y,
poly1.z) poly1, poly2 = poly1.next, poly2.next elif poly1.x > poly2.x or (poly1.x
== poly2.x and poly1.y > poly2.y) or (poly1.x == poly2.x and poly1.y == poly2.y and poly1.z
> poly2.z):
current.next = PolynomialNode(poly1.coefficient, poly1.x, poly1.y, poly1.z)
poly1 = poly1.next else:
current.next = PolynomialNode(poly2.coefficient, poly2.x, poly2.y, poly2.z)
poly2 = poly2.next current = current.next while poly1:
current.next = PolynomialNode(poly1.coefficient, poly1.x, poly1.y, poly1.z)
poly1 = poly1.next current = current.next while poly2:
current.next = PolynomialNode(poly2.coefficient, poly2.x, poly2.y, poly2.z)
poly2 = poly2.next current = current.next return result.next
Q14. Multiply two polynomials (singly linked list).
def multiply_polynomials(poly1, poly2):
terms = {}
while poly1:
current_poly2 = poly2
while current_poly2:
x = poly1.x + current_poly2.x y = poly1.y +
current_poly2.y z = poly1.z + current_poly2.z
coeff = poly1.coefficient * current_poly2.coefficient
if (x, y, z) in terms:
terms[(x, y, z)] += coeff
else:
terms[(x, y, z)] = coeff current_poly2 = current_poly2.next poly1 =
poly1.next head = None for (x, y, z), coefficient in sorted(terms.items(), key=lambda
t: (-t[0][0], -t[0][1], -t[0][2])):
new_node = PolynomialNode(coefficient, x, y, z)
new_node.next = head head = new_node
return head
Assign
ment
Q15. Take the PARTIAL DERIVATIVE of polynomial with respect to any of its
variables (doubly linked list).
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int coeff, x, y, z;
struct Node* next;
struct Node* prev;
} Node;
Node* insert(Node* head, int coeff, int x, int y, int z) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->coeff = coeff; newNode->x = x;
newNode->y = y; newNode->z = z; newNode-
>next = head; newNode->prev = NULL; if
(head) head->prev = newNode; return
newNode;
Node* derivative(Node* head, char var) {
Node* temp = head; Node* result = NULL; while (temp) { if ((var == 'x' && temp->x
> 0) || (var == 'y' && temp->y > 0) || (var == 'z' && temp->z > 0)) { int coeff = temp-
>coeff; int x = temp->x, y = temp->y, z = temp->z; if (var == 'x') coeff *= x, x--;
Assign
ment
if (var == 'y') coeff *= y, y--; if (var == 'z') coeff *= z, z--; result = insert(result,
coeff, x, y, z);
temp = temp->next;
}
return result;
void display(Node* head) { while (head) { printf("%dx^%dy^%dz^%d
", head->coeff, head->x, head->y, head->z);
if (head->next) printf("+ ");
head = head->next;
} printf("\
n");
int main() {
Node* poly = NULL; poly
= insert(poly, 3, 2, 1, 0); poly
= insert(poly, 5, 1, 2, 1); poly
= insert(poly, 4, 0, 1, 2);
printf("Original Polynomial: ");
display(poly); char var = 'x';
Assign
ment
Node* deriv = derivative(poly, var);
printf("Partial Derivative w.r.t %c: ", var);
display(deriv);
return 0;
Q16. Divide the polynomial by another polynomial creating a QUOTIENT
and a REMAINDER polynomial (singly circular linked list).
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int coeff, exp; struct
Node* next;
} Node;
Node* insert(Node* head, int coeff, int exp)
{ Node* newNode =
(Node*)malloc(sizeof(Node)); newNode->coeff
= coeff; newNode->exp = exp;
if (!head) {
newNode->next = newNode;
return newNode;
}
Assign
ment
Node* temp = head; while (temp->next !=
head) temp = temp->next; temp->next =
newNode; newNode->next = head; return
head;
Node* divide(Node* dividend, Node* divisor, Node** remainder) {
Node* quotient = NULL;
*remainder = dividend;
while (*remainder && (*remainder)->exp >= divisor->exp) {
int newCoeff = (*remainder)->coeff / divisor->coeff; int
newExp = (*remainder)->exp - divisor->exp; quotient =
insert(quotient, newCoeff, newExp);
Node* tempDiv = divisor; Node* subPoly = NULL; while (tempDiv) {
subPoly = insert(subPoly, tempDiv->coeff * newCoeff, tempDiv->exp + newExp);
tempDiv = tempDiv->next; if (tempDiv == divisor) break;
Node* tempRem = *remainder;
Node* newRem = NULL; while
(tempRem) {
Node* tempSub = subPoly;
Assign
ment
int found = 0; while (tempSub) {
if (tempSub->exp == tempRem->exp) {
found = 1; break;
tempSub = tempSub->next;
int newCoeff = found ? tempRem->coeff - tempSub->coeff : tempRem->coeff;
if (newCoeff != 0) newRem = insert(newRem, newCoeff, tempRem->exp);
tempRem = tempRem->next; if (tempRem == *remainder) break;
*remainder = newRem;
if (!(*remainder)) break;
return quotient;
void display(Node* head)
{ Node* temp = head;
if (!head)
{ printf("0\n");
return;
} do { printf("%dx^%d ", temp->coeff,
temp->exp); if (temp->next != head)
printf("+ ");
Assign
ment
temp = temp->next;
} while (temp != head);
printf("\n");
int main() {
Node* dividend = NULL;
Node* divisor = NULL;
Node* remainder = NULL;
dividend = insert(dividend, 6, 3);
dividend = insert(dividend, 5, 2);
dividend = insert(dividend, 4, 1);
divisor = insert(divisor, 2, 1); divisor
= insert(divisor, 1, 0);
printf("Dividend: ");
display(dividend); printf("Divisor:
"); display(divisor);
Node* quotient = divide(dividend, divisor, &remainder);
printf("Quotient: "); display(quotient);
printf("Remainder: ");
display(remainder);
Assign
ment
return 0;
