Linked Lists
This chapter focuses on linked lists, a dynamic data structure where elements are stored in nodes connected by pointers. It covers different types of linked lists (singly, doubly, circular), their operations, and applications. The chapter also discusses the representation of polynomial equations using linked lists.
Questions And Solutions.
2078 Chaitra
Consider two linked lists that represent two polynomials. Substract them and return the difference as a linked list. Write an algorithm and program to implement above scenario.
Solution
Algorithm to difference two polynomial
1.Initialize Pointers:
- Set p1 to the head of the first polynomial linked list (poly1).
- Set p2 to the head of the second polynomial linked list (poly2).
- Create a dummy head node for the result linked list; set current to this dummy node.
2.Traverse Both Linked Lists:
- While both p1 and p2 are not NULL:
- Compare Exponents:
- If p1->exponent equals p2->exponent:
- Compute the difference: coeff_diff = p1->coefficient - p2->coefficient.
- If coeff_diff is not zero, create a new node with coeff_diff and p1->exponent; append it to the result list.
- Advance both p1 and p2 to their respective next nodes.
- Else if p1->exponent is greater than p2->exponent:
- Create a new node with p1->coefficient and p1->exponent; append it to the result list.
- Advance p1 to its next node.
- Else (p2->exponent is greater than p1->exponent):
- Create a new node with -p2->coefficient and p2->exponent; append it to the result list.
- Advance p2 to its next node.
3.Handle Remaining Terms:
- If p1 is not NULL (remaining terms in poly1):
- For each remaining node in p1:
- Create a new node with p1->coefficient and p1->exponent; append it to the result list.
- Advance p1 to its next node.
- If p2 is not NULL (remaining terms in poly2):
- For each remaining node in p2:
- Create a new node with -p2->coefficient and p2->exponent; append it to the result list.
- Advance p2 to its next node.
4.Finalize the Result:
- The result linked list starts from the node following the dummy head.
- Return this node as the head of the resultant polynomial linked list.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int coff;
int exp;
struct Node *next;
} Node;
Node *createNode(int coff, int exp)
{
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->coff = coff;
newNode->exp = exp;
newNode->next = NULL;
return newNode;
}
Node *insertTerm(Node *head, int coff, int exp)
{
Node *newNode = createNode(coff, exp);
if (!head || head->exp < exp)
{
newNode->next = head;
return newNode;
}
Node *current = head;
while (current->next && current->next->exp > exp)
{
current = current->next;
}
if (current->exp == exp)
{
current->coff += coff;
free(newNode);
}
else
{
newNode->next = current->next;
current->next = newNode;
}
return head;
}
Node *subtractPolynomials(Node *poly1, Node *poly2)
{
Node *result;
Node *p1 = poly1;
Node *p2 = poly2;
while (p1 && p2)
{
if (p1->exp == p2->exp)
{
int coffDiff = p1->coff - p2->coff;
if (coffDiff != 0)
{
result = insertTerm(result, coffDiff, p1->exp);
}
p1 = p1->next;
p2 = p2->next;
}
else if (p1->exp > p2->exp)
{
result = insertTerm(result, p1->coff, p1->exp);
p1 = p1->next;
}
else
{
result = insertTerm(result, -p2->coff, p2->exp);
p2 = p2->next;
}
}
while (p1)
{
result = insertTerm(result, p1->coff, p1->exp);
p1 = p1->next;
}
while (p2)
{
result = insertTerm(result, p2->coff, p2->exp);
p2 = p2->next;
}
return result;
}
void displayPolynomial(Node *poly)
{
if (!poly)
{
printf("0\n");
return;
}
Node *current = poly;
while (current)
{
if (current->coff > 0 && current != poly)
{
printf("+");
}
else if (current->coff < 0)
{
printf("-");
}
printf("%dx^%d", abs(current->coff), current->exp);
current = current->next;
}
printf("\n");
}
void freePolynomial(Node *poly)
{
Node *temp;
while (poly)
{
temp = poly->next;
poly = poly->next;
free(temp);
}
}
int main()
{
Node *poly1 = NULL;
Node *poly2 = NULL;
poly1 = insertTerm(poly1, 3, 4);
poly1 = insertTerm(poly1, 2, 2);
poly1 = insertTerm(poly1, 1, 0);
poly2 = insertTerm(poly2, 5, 4);
poly2 = insertTerm(poly2, 3, 3);
poly2 = insertTerm(poly2, 1, 0);
printf("Polynomial 1: ");
displayPolynomial(poly1);
printf("\nPolynomial 2: ");
displayPolynomial(poly2);
Node *result = subtractPolynomials(poly1, poly2);
printf("\nResult (Polynomial 1 - Polynomial 2): ");
displayPolynomial(result);
freePolynomial(poly1);
freePolynomial(poly2);
freePolynomial(result);
return 0;
}
Output
Polynomial 1: 3x^4+2x^2+1x^0
Polynomial 2: 5x^4+3x^3+1x^0
Result (Polynomial 1 - Polynomial 2): -2x^4-3x^3+2x^2
2078 Poush
How do you represent polynomial equation using linked list? Write an algorithm to add two polynomial equations using linked list
Solution We can represent these terms in the form of a linked list. So, we can define each term as a node and we will have a set of nodes for a single polynomial. So let us define a node for a single term. Here is the node that is having a coefficient, an exponent, and a pointer (next) to the next node.
typedef struct Node
{
int coff;
int exp;
struct Node *next;
} Node;
**Algorithm to add two polynomial **
1.Initialize Pointers:
- Set p1 to the head of the first polynomial linked list (poly1).
- Set p2 to the head of the second polynomial linked list (poly2).
- Create a dummy head node for the result linked list; set current to this dummy node.
2.Traverse Both Linked Lists:
- While both p1 and p2 are not NULL:
- Compare Exponents:
- If p1->exponent equals p2->exponent:
- Compute the difference: coeff_sum = p1->coefficient + p2->coefficient.
- If coeff_diff is not zero, create a new node with coeff_sum and p1->exponent; append it to the result list.
- Advance both p1 and p2 to their respective next nodes.
- Else if p1->exponent is greater than p2->exponent:
- Create a new node with p1->coefficient and p1->exponent; append it to the result list.
- Advance p1 to its next node.
- Else (p2->exponent is greater than p1->exponent):
- Create a new node with -p2->coefficient and p2->exponent; append it to the result list.
- Advance p2 to its next node.
3.Handle Remaining Terms:
- If p1 is not NULL (remaining terms in poly1):
- For each remaining node in p1:
- Create a new node with p1->coefficient and p1->exponent; append it to the result list.
- Advance p1 to its next node.
- If p2 is not NULL (remaining terms in poly2):
- For each remaining node in p2:
- Create a new node with -p2->coefficient and p2->exponent; append it to the result list.
- Advance p2 to its next node.
4.Finalize the Result:
- The result linked list starts from the node following the dummy head.
- Return this node as the head of the resultant polynomial linked list.
2078 Ashwin
Explain how a circular linked list is different from a linear linked list. Write an algorithm to delete a node in a circular linked list.
Solution
linear linked list
structure: A linear linked list is a sequential chain of nodes, where each node points to the next node in the sequence. The last node in the list typically points to NULL.
Traversal: To traverse a linear linked list, you start at the head node and follow the
next pointers until you reach the NULL node.
Applications: More versatile and widely used in various applications, including implementing stacks, queues, and representing trees.
Circular linked list
structure: A circular linked list is similar to a linear linked list, but the last node in the list points back to the first node, forming a circular loop.
Traversal: You can start at any node in the list and traverse the entire list without encountering a
NULL node.
Applications: Circular Linked Lists Often used in applications where continuous looping is required, such as round-robin scheduling algorithms, implementation of data structures like FIFO queues, and undo/redo functionality in text editors.
Deletion of node from the beginning of the circular linked list
1.Check if List is Empty:
If last is nullptr, print “List is empty” and return nullptr.
2.Get Head Node:
Set head to last->next.
2.Check for Single Node:
If head equals last, delete head and set last to nullptr.
2.Handle Multiple Nodes:
Update last->next to point to head->next.
Delete head.
2.Return Updated last
Deletion at specific position in circular linked list
- Check if List is Empty (last is nullptr) then print “List is empty, nothing to delete” and return nullptr.
- Set curr to last->next (head) and prev to last.
- Check for single node, if node’s data matches key, delete it and set last to nullptr.
- Check for first node to delete, if head node’s data matches key, update last->next and delete the head.
- Loop through the list to find the node with the specified key.
If node found then update prev->next to skip the deleted node. If the deleted node is last, update last to prev.
Otherwise, print “Node with data [key] not found.” - Return the modified last.
Deletion at the end of Circular linked list
1 . Check if List is Empty (last is nullptr) then print “List is empty, nothing to delete” and return nullptr.
2 . Get head node by Setting head to last->next.
3 . Check for single node, if head equals last, delete last and set last to nullptr.
4 . Find second last node by traversing the list until curr->next equals last.
5 . Update Pointer by setting curr->next to point to head.
6 . Delete last and update last to curr.
7 . Return the updated last.
2078 Ashwin(Back)
Explain how to insert a new node at the beginning, at the end, and at a given position in the circular linked list.
Solution
For inserting a new node at the beginning
Algorithm
1.ptr = (node *) malloc(sizeof(node))
2. set ptr->info = ITEM
3. if start == NULL then
set ptr->next = ptr
set start = ptr
set last = ptr
elese follow step 4 to 6
4. set ptr->next = start
5.set start = ptr
6 set last->next = ptr
For inserting a new node at the end
Algorithm
1.ptr = (node *) malloc(sizeof(node))
2.set ptr->info = ITEM
3.if start == NULL then
set ptr->next = ptr
set start = ptr
set last = ptr
elese follow step 4 to 6
4.set last->next = ptr
5.set last = ptr
6.set last->next = start
For inserting a new node at the end
Algorithm
1.ptr = (node *) malloc(sizeof(node))
2.Set ptr->info = ITEM
3.If start == NULL then
a. Set ptr->next = ptr
b. Set start = ptr
c. Set last = ptr
Return
4.If pos == 1 then
a. Set temp = start
b. While temp->next != start do
i. Set temp = temp->next
c. Set ptr->next = start
d. Set start = ptr
e. Set temp->next = start
Return
5.Initialize temp = start and count = 1
6.While count < pos - 1 and temp->next != start do
a. Set temp = temp->next
b. Increment count
7.Set ptr->next = temp->next
8.Set temp->next = ptr
9.If temp == last then
a. Set last = ptr
2078 Chaitra (Back)
What are the advantages of doubly linked list over singly linked list? Write an algorithm to insert a node before a given node in a singly linked list.
Solution
Advantages of doubly linked list are -:
- Reversing the doubly linked list is very easy.
- It can allocate or reallocate memory easily during its execution.
- As with a singly linked list, it is the easiest data structure to implement.
- Doubly linked lists have a low overhead compared to other data structures such as arrays.
- Insertion and Deletion at Both Ends
Algorithm
- Traverse the list to find the node just before the target node.
- Create a new node and assign data to it.
- Set the new node’s next pointer to point to the target node.
- Update the previous node’s next pointer to point to the new node.
Pseudocode
Node* insertBefore(Node* head) {
Node *newNode, *ptr, *preptr;
int values;
newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
return head;
}
printf("Enter the data for the new node: ");
scanf("%d", &newNode->data);
printf("Enter the value before which the new node should be inserted: ");
scanf("%d", &values);
if (head == NULL) {
printf("The list is empty. Cannot insert before %d.\n", values);
free(newNode);
return head;
}
if (head->data == values) {
newNode->next = head;
return newNode;
}
ptr = head;
preptr = NULL;
while (ptr != NULL && ptr->data != values) {
preptr = ptr;
ptr = ptr->next;
}
if (ptr == NULL) {
printf("Value %d not found in the list.\n", values);
free(newNode);
return head;
}
preptr->next = newNode;
newNode->next = ptr;
return head;
}
2074 Bhadra
How do you delete a node at the end of the doubly linked list? Explain how the addition of polynomial equations is done using linked list
Solution
To delete a node at the end in doubly linked list, we can use the following steps:
- Check if the doubly linked list is empty. If it is empty, then there is nothing to delete.
- If the list is not empty, then move to the last node of the doubly linked list, say curr.
- Update the second-to-last node’s next pointer to NULL, curr->prev->next = NULL.
- Free the memory allocated for the node that was deleted.
The addition of polynomial equations is done using linked list as We compare the power of the first polynomial of both lists. If it is the same then we simply add their coefficient and push them into the resultant list otherwise we push the polynomial of the list whose power is greater than the other polynomial.
Pseudocode
- Declare variables that point to the head of the linked list.
- Compare the power of the first polynomial of both lists.
a. If it is the same then add their coefficients and push them into the resultant list. Also, increment both the variables so that it points to the next polynomial.
b. If it is the same then add their coefficients and push them into the resultant list. Also, increment both the variables so that it points to the next polynomial. - Keep repeating the 2nd step until one of the variables reaches the end of the list.
- Then check for the remaining data in both of the lists and add it to the resultant list.
2073 Bhadra
How do you perform a push and pop operation in stack as a linked list? How do you insert and delete a node at the i^th position of the doubly linked list.
Solution
Push() elements in the stack using linked list
Adding or inserting a new element to a stack is known as the Push() operation in the stack. Elements can only be pushed at the top of the stack.
Steps to push an element into a Stack:
1.Create a new node using dynamic memory allocation and assign value to the node.
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 10;
2.Check if stack is empty or not, i.e, (top == NULL).
3.If it is empty, then set the next pointer of the node to NULL.
newNode->next = NULL;
4.If it is not empty, the newly created node should be linked to the current top element of the stack, i.e.,
newNode->next = top;
5.Make sure that the top of the stack should always be pointing to the newly created node.
top = newNode;
Algorithm for push()
if the top is equal to NULL
newNode -> next = NULL
else
newNode -> next = top
Example of push operation
struct Node {
int data;
struct Node *next;
};
Node* top = NULL;
int pop() {
if (top == NULL) {
printf("\nEMPTY STACK");
} else {
struct Node *temp = top;
int temp_data = top->data;
top = top->next;
free(temp);
return temp_data;
}
}
pop() elements from the stack using linked list:
Removing or deleting an element from a stack is known as the Pop() operation in the stack. Elements are popped from the top of the stack. There should be at least one element in the stack to perform the pop() operation.
Steps to pop an element from a Stack:
1.Check if stack is empty or not, i.e, (TOP == NULL).
2.If it is empty, then print Stack Underflow.
print "Stack Underflow"
3.If it is not empty, then create a temporary node and set it to top. Now, create another variable and copy the data of top element to this variable.
struct Node *temp = top;
int temp_data = top->data;
4.Now, make top point to the next node.
top = top->next;
5.Delete the temporary node and return the value stored in temp_data.
free(temp);
return temp_data;
Algorithm for pop()
if top == NULL
print "Stack Underflow"
else
create temporary node, *temp = top
create temporary variable, temp_data = top->data
top = top->next
free(temp)
return temp_data
Example of Pop() Operation:
struct Node {
int data;
struct Node *next;
}
Node* top = NULL;
int pop() {
if (top == NULL) {
printf("\nEMPTY STACK");
} else {
struct Node *temp = top;
int temp_data = top->data;
top = top->next;
free(temp);
return temp_data;
}
}
To insert a node at the i^th position of the doubly linked list.
The idea is to traverse the linked list to find the node at position - 1, say current node. If the position is valid, create a new node with the given data and update its pointers: Set the next pointer of new node to next of current node and previous pointer of new node to current node. Similarly, update next pointer of current node to the new node and prev pointer of new node’s next to the new node.
To insert a new node at a specific position:-
To perform the deletion, If the position is 1, we update the head to point to the next node and delete the current head. For other positions, we traverse the list to reach the node just before the specified position. If the target node exists, we adjust the next of this previous node to point to next of next nodes, which will result in skipping the target node.
2072 Ashwin
Define different types of linked list with suitable example. Write an algorithm creates a single linked list.
Solution
Types of Linked Lists
1.Singly Linked List: Singly linked list is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type.
Use Case
struct Node {
int data;
Node* next;
};
Example
Node1 -> Node2 -> Node3 -> NULL
2. Doubly linked list: A doubly linked list or a two-way linked list is a more complex type of linked list that contains a pointer to the next as well as the previous node in sequence.
Use Case
struct Node {
int data;
Node* prev;
Node* next;
};
Example
NULL <- Node1 <-> Node2 <-> Node3 -> NULL
3. Circular Linked list A circular linked list is a type of linked list in which the last node’s next pointer points back to the first node of the list, creating a circular structure. This design allows for continuous traversal of the list, as there is no null to end the list.
Use Case
struct Node {
int data;
Node* next;
};
Example (Singly circular)
Node1 -> Node2 -> Node3 -> Node1
Example (Doubly circular)
Node1 <-> Node2 <-> Node3 <-> Node1
4.Circular Doubly Linked List: A circular doubly linked list is defined as a circular linked list in which each node has two links connecting it to the previous node and the next node.
Example
Node1 <-> Node2 <-> Node3 <-> Node1
Use Case
struct Node {
int data;
Node* next;
Node* prev;
};
Algorithm: CREATE (HEAD, ITEM)
- [Create NEW node]
a) Allocate memory for NEW node.
b) IF NEW = NULL then Print: “Memory not Available” and Return
c) Set NEW→DATA = ITEM
d) Set NEW→LINK = NULL - [Whether List is empty, head is the content of HEADER]
If HEAD = NULL then Set HEAD = NEW - Else
a) Set Temp = HEAD
b) While Temp→LINK ≠ NULL do
Set Temp = Temp→LINK
[End of while]
c) Set Temp→LINK = NEW
[End of IF] - Return
2066 Jestha
What are the types of linked list? Discuss the consideration that has to be taken while developing algorithm/program with a linked list. Why alias variables are dangerous in a linked list? Write an algorithm to delete the first node in a singly linked list.
Solution
Types of linked list are:
- singly linked list.
- doubly linked list.
- circular linked list.
- doubly circular linked list.
Developing an algorithm or program with a linked list requires careful consideration to ensure correctness, efficiency, and maintainability. Here are the key factors to consider:
1.Memory management:
Dynamic Memory Allocation: Ensure proper allocation of memory for each node using functions like malloc (in C) or new (in C++/Java).
Deallocation: Avoid memory leaks by freeing unused nodes (free in C or delete in C++/Java).
Null Pointers: Handle null pointers carefully to prevent segmentation faults or crashes.
2.Node struct:
Design the node to hold necessary data and the link to the next (and/or previous) node.
struct Node {
int data;
struct Node* next;
};
3.Initialization: Properly initialize the linked list (e.g., setting head to NULL for an empty list).
4.traversal: Use a temporary pointer to traverse the list without modifying the head.& Ensure traversal stops when the pointer reaches NULL.
5.Insertion, deletion, time Complexity.
6.recursive operation, Performance optimization, testing, error handling.
Aliases can be dangerous in linked lists because they may lead to subtle bugs, unexpected behavior, and data corruption if not handled carefully.
Algorithm for deleting the first node of the singly linked list
let *head be the pointer to the first node in current list
1.if(head == NULL) Then
print "void deletion" and exit.
2. store the address of first node in a temporary variable temp
temp = head
3. set head to next of head
head = head->next
4.free the memory Reversed by temp variable.
free (temp)
5.end
2066 Bhadra
Write an algorithm to move one node to another place after a node in singly linear linked list.
Solution:
Algorithm to move one node to another place after a node in a singly linear linked list: Identify the node to be moved and the target node after which it should be placed.
- If the list is empty or
nodeToMoveis NULL, return (no operation can be performed). - Find the node
prevNode(the node beforenodeToMove). - Set
nodeToMove->nextto NULL. - If
targetNodeis NULL, it means there is no valid target; handle the case accordingly. - Set
nodeToMove->nexttotargetNode->next. - Set
targetNode->nexttonodeToMove. - Return (the node has been successfully moved).
2065 Shrawan
What are linked list? Write an algorithm for inserting a node before a node and deleting a node after a node in singly linked list.
Solution:
Linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. It allows for efficient insertion and deletion of elements.
Algorithm for inserting a node before a given node in a singly linked list:
- Create a new node with the desired data.
- If the list is empty or the node to insert before is NULL, return (no operation can be performed).
- If the node to insert before is the head of the list, set the new node's next to the head and update the head to the new node.
- Traverse the list to find the node just before the target node.
- Set the new node's next to the target node and update the previous node's next to the new node.
- Return (the node has been successfully inserted).
Algorithm for deleting a node after a given node in a singly linked list:
- If the list is empty or the node after which to delete is NULL, return (no operation can be performed).
- If the node to delete is the last node, handle the case accordingly.
- Set the next pointer of the given node to skip the node to be deleted.
- Free the memory of the node to be deleted.
- Return (the node has been successfully deleted).
2063 Baishakh
Discuss the merits and demerits of contiguous list and linked list. Write algorithms to insert and delete a node after a node in a singly linked list.
Solution
Merits of contiguous list
1.Predictable Memory Allocation
2.Memory Efficiency
3.Ease of Sorting
4.Faster Traversal
Demerits of contiguous list
1.Poor Cache Performance:
2.Difficulty in Resizing
3.Limited Flexibility
4.Poor Cache Performance
Merits of linked list
1.Efficient Insertion and Deletion.
2.No Memory Waste
3.Easy Implementation of Abstract Data Types
4.Efficient Sorting in Some Cases
Demerits of linked list
1.Inefficient Random Access.
2.Extra Memory Usage.
3.Complexity in Implementation.
4.Difficulty in Reverse Traversal.
Insertion a node after a node in a singly linked list
insert_after(struct node *head, int x, int info){
struct node *ptr1, *new;
new = (struct node*)malloc(sizeof(struct node));
new->data = info;
ptr1 = head;
while(ptr1->data != key && ptr1 != null ){
ptr1= ptr1->next;
}
if(ptr1->data == x){
new->next = ptr1->next;
ptr1->next = new;
}
return head;
}
Delete a node after a node in a singly linked list
delete_after(struct node *head, int key){
struct node *ptr1, *ptr2;
ptr1 = head;
while(ptr1->next != NULL ){
if(ptr1->data == key){
ptr2 = ptr1->next;
ptr1->next = ptr2->next;
free(ptr2);
break;
}
ptr1= ptr1->next;
}
return head;
}