Implementation of linked list deletion operation:
Linked List:
A linear data structure where each element denotes a separate object is known as linked list.
- Each element of a list contains two items, the data and a pointer to next node.
- The last node would point to null.
- The “head” denotes point of entry into a linked list.
- If list is empty then the head is a null pointer.
- The structure of linked list is given below:
/*************************************************************
* This program demonstrates deletion of linked list *
* nodes corresponding to positions obtained from *
* two linked lists *
*************************************************************/
Explanation of Solution
Program:
//Include header files
#include<iostream>
using namespace std;
//Declare an array "la[]"
int la[100], i=0;
//Define a linked list node
struct lnode
{
//Define data of node
int ldata;
//Define pointer to next node
lnode *lnext;
}*start;
/*Function Prototypes */
lnode *lcreate_node(int lvalue);
void lsortedInsert(struct lnode** head_ref, struct lnode* lnew_node);
void ldisplay(struct lnode* head);
void ldeleteKey(struct lnode **head_ref, int lkey);
void merge(struct lnode *p, struct lnode **q);
struct lnode* lSortedMerge(struct lnode* la, struct lnode* lb);
void lFBS(struct lnode* lsource, struct lnode** frontRef, struct lnode** backRef);
/* Function "lcreate_node()" creates la new node, allocates the memory space and puts the data in it */
struct lnode *lcreate_node(int lnew_data)
{
//Allocate lnode
struct lnode* lnew_node = (struct lnode*) malloc(sizeof(struct lnode));
// Put in the ldata
lnew_node->ldata = lnew_data;
//Make the next of new node to NULL
lnew_node->lnext = NULL;
//Return the new node
return lnew_node;
}
//Define "merge()" that merges two linked lists
void merge(struct lnode *p, struct lnode **q)
{
//Declare nodes of type "lnode*"
struct lnode *lp_curr = p, *lq_curr = *q;
struct lnode *lp_next, *lq_next;
// Loop until positions are available
while (lp_curr != NULL && lq_curr != NULL)
{
// Save the next pointers
lp_next = lp_curr->lnext;
lq_next = lq_curr->lnext;
// Make lq_curr as next of lp_curr
lq_curr->lnext = lp_next;
lp_curr->lnext = lq_curr;
// Update the pointers
lp_curr = lp_next;
lq_curr = lq_next;
}
// Update second list's head pointer
*q = lq_curr;
}
//Define a function "MergeSort()" that sorts linked list by changing next pointers
void MergeSort(struct lnode** headRef)
{
//Declare nodes of type "lnode*"
struct lnode* head = *headRef;
struct lnode* la;
struct lnode* lb;
//If linked list is empty or has single element
if ((head == NULL) || (head->lnext == NULL))
{
return;
}
// Split head into sublists
lFBS(head, &la, &lb);
// Sort sublists
MergeSort(&la);
MergeSort(&lb);
// Merge lists that are sorted
*headRef = lSortedMerge(la, lb);
}
/*Define a function "lFBS()" that divides the list into two halves and returns refernce parameters of result*/
void lFBS(struct lnode* lsource, struct lnode** frontRef, struct lnode** backRef)
{
//Declare nodes "fast" and "slow" of type "lnode*"
struct lnode* fast;
struct lnode* slow;
//If list is empty or contains single element
if (lsource==NULL || lsource->lnext==NULL)
{
//If length < 2
*frontRef = lsource;
*backRef = NULL;
}
else
{
//If list contains more than one element
slow = lsource;
fast = lsource->lnext;
/* Traverse "fast" two nodes, and traverse "slow" one node */
while (fast != NULL)
{
//Traverse the "fast"
fast = fast->lnext;
/* Traverse the list until "fast" reaches null */
if (fast != NULL)
{
//Move to next element
slow = slow->lnext;
fast = fast->lnext;
}
}
/* "slow" is before list's midpoint, split it in two at that point. */
*frontRef = lsource;
*backRef = slow->lnext;
slow->lnext = NULL;
}
}
/* Define a function "lSortedMerge()" that merges the lists that are sorted, it takes header pointers of two lists as arguments */
struct lnode* lSortedMerge(struct lnode* la, struct lnode* lb)
{
//Declare node to store result
struct lnode* result = NULL;
//If either of list is empty
if (la == NULL)
return(lb);
else if (lb==NULL)
return(la);
//Chose either la or lb, and recur
if (la->ldata <= lb->ldata)
{
//Place "la" first
result = la;
//Continue with next element of "la" and "lb"
result->lnext = lSortedMerge(la->lnext, lb);
}
else
{
//place "lb" first
result = lb;
//Continue with next element of "lb" and "la"
result->lnext = lSortedMerge(la, lb->lnext);
}
//Return result
return(result);
}
//Define a main function
int main()
{
//Initialize variables
start = NULL;
//Make the head reference of new node to NULL
struct lnode* head = NULL;
//Insert first node into linked list
struct lnode *lnew_node = lcreate_node(5);
/*Call the function "lsortedInsert()" with "head" and "lnew_node" as arguments and inserts the node into it.*/
lsortedInsert(&head, lnew_node);
lnew_node = lcreate_node(10);
lsortedInsert(&head, lnew_node);
lnew_node = lcreate_node(20);
lsortedInsert(&head, lnew_node);
lnew_node = lcreate_node(30);
lsortedInsert(&head, lnew_node);
lnew_node = lcreate_node(40);
lsortedInsert(&head, lnew_node);
lnew_node = lcreate_node(50);
lsortedInsert(&head, lnew_node);
lnew_node = lcreate_node(60);
lsortedInsert(&head, lnew_node);
lnew_node = lcreate_node(70);
lsortedInsert(&head, lnew_node);
lnew_node = lcreate_node(80);
//Display the elements of list
cout<<"Elements of first list are: "<<endl;
//Call the function "ldisplay()" to display elements.
ldisplay(head);
//Make the head reference of new node to NULL
struct lnode* head1 = NULL;
//Insert the first node into linked list
struct lnode *new_node1 = lcreate_node(3);
lsortedInsert(&head1, new_node1);
/*Call the function "lsortedInsert()" with "head1" and "new_node1" as arguments and inserts the node into it.*/
new_node1 = lcreate_node(1);
lsortedInsert(&head1, new_node1);
new_node1 = lcreate_node(2);
lsortedInsert(&head1, new_node1);
//Display elements of linked list
cout<<"Elements of second list are: "<<endl;
ldisplay(head1);
//Make the head reference of new node to NULL
struct lnode* head2 = NULL;
//Insert the first node into linked list
struct lnode *new_node2 = lcreate_node(6);
lsortedInsert(&head2, new_node2);
/*Call the function "lsortedInsert()" with "head1" and "new_node1" as arguments and inserts the node into it.*/
new_node2 = lcreate_node(5);
lsortedInsert(&head2, new_node2);
new_node2 = lcreate_node(4);
lsortedInsert(&head2, new_node2);
//Display elements of linked list
cout<<"Elements of third list are: "<<endl;
ldisplay(head2);
//Call "merge()" to merge two linked lists
merge( head1, &head2);
printf("Linked List after merging second and third list: \n");
MergeSort(&head1);
ldisplay(head1);
//Store the values of second list into an array
while( head1!=NULL )
{
//Copy the data at the node into variable "c"
int c = head1->ldata;
//copy value in "c" into the array "la[]"
la[i] = c;
//Increment value of "i"
i++;
// Traverse each element
head1 = head1->lnext;
}
//Declare the variables
int lIndex = 0;
/*Search the element in first list with the position in second list */
for(int k=0;k<i;k++)
{
/*Declare la node "ltemp" and assign "head "into it */
struct lnode* ltemp = head;
//Declare the variables
lIndex=0;
/*Match the values in first array with index in second array */
while(lIndex !=la[k] && ltemp!=NULL)
{
//Traverse the list
ltemp = ltemp->lnext;
//Increment the index value
lIndex++;
}
/*Assign the value 0 to data that are at positions in second list */
ltemp->ldata = 0;
}
/*Call the function "ldeleteKey()" with "head" and value 0 as arguments */
ldeleteKey(&head,0);
//Display the result after deletion
cout<<"Elements of first list after deletion : "<<endl;
//Call "ldisplay()" to display list
ldisplay(head);
cout<<endl;
//Pause the console window
system("pause");
return 0;
}
/*Declare the function "lsortedInsert()" that takes head reference and new node as arguments and inserts the node into list in sorted order */
void lsortedInsert(struct lnode** head_ref, struct lnode* lnew_node)
{
//Declare la node "current"
struct lnode* current;
/*If list is empty or data of new node is less than or equal to present data of list */
if (*head_ref == NULL || (*head_ref)->ldata >= lnew_node->ldata)
{
//Make head reference to "lnew_node->lnext"
lnew_node->lnext = *head_ref;
//Assign new node to head reference
*head_ref = lnew_node;
}
else
{
//Locate node before insertion point
current = *head_ref;
//Place the node in sorted order
while (current->lnext!=NULL && current->lnext->
ldata < lnew_node->ldata)
{
//Traverse the list pointer
current = current->lnext;
}
//Make "current->lnext" to "lnew_node->lnext"
lnew_node->lnext = current->lnext;
//Assign new node to "current->lnext"
current->lnext = lnew_node;
}
}
/*The function "ldisplay()" takes the header pointer of list as arguments and elements of list are displayed */
void ldisplay(struct lnode* head)
{
//Declare a node "ltemp"
struct lnode *ltemp;
//If head is NULL
if (head == NULL)
{
//Display the message
cout<<"The List is Empty"<<endl;
return;
}
//Set "ltemp" as head node
ltemp = head;
/*Display the data in linked list until it reaches null */
while (ltemp != NULL)
{
//Display the data
cout<<ltemp->ldata<<"->";
//Move to next element
ltemp = ltemp->lnext;
}
//Display the end of list
cout<<"NULL"<<endl;
}
/*The function ldeletekey()" takes the header pointer and the deletion element as arguments and deletes the particular element from the list */
void ldeleteKey(struct lnode **head_ref, int lkey)
{
// Store head node
struct lnode* ltemp = *head_ref, *prev;
/*Check for all occurrences of the deletion element in the list */
while (ltemp != NULL && ltemp->ldata == lkey)
{
//Change header pointer
*head_ref = ltemp->lnext;
//Free old head
free(ltemp);
//change "ltemp"
ltemp = *head_ref;
}
//Delete all occurrences of element other than "head"
while (ltemp != NULL)
{
/*Search for key to be deleted, track previous node as 'prev->lnext' is to be changed*/
while (ltemp != NULL && ltemp->ldata != lkey)
{
prev = ltemp;
ltemp = ltemp->lnext;
}
//If key is not in list
if (ltemp == NULL) return;
//Unlink the node from list
prev->lnext = ltemp->lnext;
//Free memory
free(ltemp);
//Update "ltemp" for next loop iteration
ltemp = prev->lnext;
}
}
Explanation:
- The above program declares two linked list and deletes elements of first linked list at positions corresponding to elements in second linked list.
- The function “lcreate_node()” takes an integer value as parameter and creates a node of the linked list.
- The function “lsortedInsert()” takes header pointers of list and new node created as the parameters of the function and inserts the node in the list in sorted order.
- The function “ldisplay()” takes header pointers of linked list as arguments and displays the linked list contents.
- The function “ldeleteKey()” takes header reference pointer of linked list and element to delete as the function arguments and it deletes all element occurrences from list.
- The function “merge()” takes header reference pointer of two linked list as arguments and merges two lists.
- The function “lSortedMerge()”that merges the list that are sorted, it takes header pointers of two list as arguments.
- The function “lFBS()”that divides the list into two halves and returns reference parameters of result.
- In the main function three linked list are defined, elements of second list and third list are merged and then sorted which denotes deletion position index of first list.
- The data values in first list corresponding to positions in merged list are replaced with value 0.
- Delete function is called with header pointer of list and value 0 as function arguments so as to delete all occurrences of 0 from list.
- The final linked after the deletion process is displayed as result.
Output:
Elements of first list are:
5->10->20->30->40->50->60->70->NULL
Elements of second list are:
1->2->3->NULL
Elements of third list are:
4->5->6->NULL
Linked List after merging second and third list:
1->2->3->4->5->6->NULL
Elements of first list after deletion:
5->70->NULL
Press any key to continue . . .
Want to see more full solutions like this?
Chapter 3 Solutions
EBK DATA STRUCTURES AND ALGORITHMS IN C
- A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return . Otherwise, return . Example refers to the list of nodes The numbers shown are the node numbers, not their data values. There is no cycle in this list so return . refers to the list of nodes There is a cycle where node 3 points back to node 1, so return . Function Description Complete the has_cycle function in the editor below. It has the following parameter: SinglyLinkedListNode pointer head: a reference to the head of the list Returns int: if there is a cycle or if there is not Note: If the list is empty, will be null. Input Format The code stub reads from stdin and passes the appropriate argument to your function. The custom test cases format will not be described for this question due to its complexity. Expand the section for the main function and review the…arrow_forwardQuestion Given a singly linked list, you need to do two tasks. Swap the first node with the last node. Then count the number of nodes and if the number of nodes is an odd number then delete the first node, otherwise delete the last node of the linked list. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 2->3->4->1. Because 1 and 5 will be swapped and 5 will be deleted as the number of nodes in this linked list is 5 which is an odd number, that means the first node which contains 5 has been deleted. If the input linked list is NULL, then it should remain NULL. If the input linked list has 1 node, then this node should be deleted and a new head should be returned. Sample 1: Input: NULL output: NULL. Sample 2: Input: 1 output: NULL Sample 3: Input: 1->2 output: 2 Sample 4: Input: 1->2->3 output: 2->1 Sample 5: Input: 1->2->3->4 _output: 4->2->3 Sample 6: Input: 1->2->3->4->5->6 output: 6->2->3->4->5. Input: The function takes one argument…arrow_forwardBeginning with a singly linked list composed of 5 nodes, draw step-by-step the process of removing index 3 from the list.arrow_forward
- The special case(s) when deleting a node in a linked list is/are: а. The list is empty. O b. All c. The node to be deleted is the first node. O d. There is only one node in the list.arrow_forwardwrite a program to find second maximum node in circular link list. First you design structure of circular linked list then perform these functionality.arrow_forwardDetermine if an intersection exists between two (singly) linked lists. Return the intersection node. Keep in mind that the intersection is defined by reference rather than value. This indicates that they intersect if the kth node of the first linked list is the same as the jth node of the second linked list (by reference).arrow_forward
- Write a program that inserts the following numbers into two (2) empty doubly linked list.L1 50 30 25 75 82 28 77L2 50 40 25 75 80 21 37 30Hint: Put the median at the first element of linked list for both linked list and after insertingmedian element at the first node, do not pass that element again. Median Formula: (n+1)/2a) Implement an insert function for both L1 and L2.b) Implement a function to delete 80 from L2.c) Implement a function to check L1 and L2 are really the same list of nodes or not.Note: You are not allowed to use any built-in Data Structure classes to implement abovescenario.arrow_forwardWrite a Python code using the given function and conditions. Do not use Numpy. Use LinkedList Manipulation. Given function: def insert(self, newElement, index) Pre-condition: The list is not empty. Post-condition: This method inserts newElement at the given index of the list. If an element with the same key as newElement value already exists in the list, then it concludes the key already exists and does not insert the key. [You must also check the validity of the index].arrow_forwardTrue or FalseA Doubly Linked List has a Header and Trailer sentinels to facilitate a more generic approach when adding and removing the head and tail nodes.arrow_forward
- Sort the list L = 5, 1, 26, 15, 76, 34, 15 quickly. depicts the man stages of the sorting procedure. There is no sorting done when the partitioned sublists only have one entry. Additionally, notice how the pivot element 34 interacts with itself 17.8. 1, 5, 15, 15, 26, 34, and 76 make up the final sorted list.arrow_forwardTrue or False For each statement below, indicate whether you think it is True or False. If you like, you can provide a description of your answer for partial credit in case you are incorrect. Use the standard linked list below to answer True/False statements 9-12: 8 7 null 4 10 The “head” pointer of this list is pointing to Node 4 If we called “insert(5)”, the new node’s “next” pointer will point to Node 8 If we called “delete(10)”, Node 7’s “next” pointer will point to Node 8 If we called “search(20)”, the “head” pointer will be at Node 4 after the search function endsarrow_forwardSuppose there are two singly linked lists both of which intersect at some point and become a single linked list. The head or start pointers of both the lists are known, but the intersecting node is unknown. Also, the number of nodes in each of the list before they intersect are unknown and both the list may have it different. List1 may have n nodes before it reaches intersection point and List2 might have m nodes before it reaches intersection point where m and n may be m = n, m > n or m < n. Give an algorithm for finding the merging point. Hints: A brute force approach would be to compare every pointer in one list with every pointer in another list. But in this case the complexity would be O(mn)arrow_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education