Question
In: Computer Science
Write the following algorithms for a Doubly Linked List Inserting an item
- Write the following algorithms for a Doubly Linked List
- Inserting an item [7]
- Deleting an item [7]
Question two
- Take a queue containing numbers 10, 15, 5, 25, 30 in which 30 has been inserted first. After performing the following operations, what would be the contents of the queue?
- Delete two elements [2]
- Insert 7 and then 20 [2]
- Delete an element [2]
Solutions
Expert Solution
Answer:
I am giving the code to entire implementation of double linked list.
Question One:
code:
#include <stdio.h>
#include <stdlib.h>
struct node{
struct node *prev;
int data;
struct node *next;
};
struct node *start = NULL;
void display_main_choices(void);
void display_insertion_choices(void);
void display_deletion_choices(void);
void insertion_beginning(void);
void insertion_end(void);
void insertion_after_given_node(void);
void insertion_before_given_node(void);
void deletion_beginning(void);
void deletion_end(void);
void deletion_after_given_node(void);
void deletion_before_given_node(void);
void display_elements(void);
void main(){
int main_choice, insertion_choice, deletion_choice;
printf("Welcome to the world of programming .\n");
display_main_choices() ;
scanf("%d",&main_choice);
while(main_choice != -1){
switch(main_choice){
case 1:
display_insertion_choices();
scanf("%d",&insertion_choice);
while(insertion_choice != -1){
switch(insertion_choice){
case 1:
insertion_beginning();
//printf("Insertion at beginning\n");
break;
case 2:
insertion_end();
//printf("Insertion at end\n");
break;
case 3:
insertion_after_given_node();
//printf("Insertion after given node\n");
break;
case 4:
insertion_before_given_node();
//printf("Insertion before given node\n");
break;
default:
printf("You have choosen wrong choice. Please choose again.\n");
break;
}
display_insertion_choices();
scanf("%d",&insertion_choice);
}
break;
case 2:
display_deletion_choices();
scanf("%d",&deletion_choice);
while(deletion_choice != -1){
switch(deletion_choice){
case 1:
deletion_beginning();
//printf("Deletion at beginning\n");
break;
case 2:
deletion_end();
//printf("Deletion at end\n");
break;
case 3:
deletion_after_given_node();
//printf(("Deletion after given node\n"));
break;
case 4:
deletion_before_given_node();
//printf("Deletion before given node\n");
break;
default:
printf("You have choosen wrong choice. Please choose again.\n");
break;
}
display_deletion_choices();
scanf("%d",&deletion_choice);
}
break;
case 3:
display_elements();
break;
default:
printf("You have chosen wrong choice. Please choose again.\n");
break;
}
display_main_choices();
scanf("%d",&main_choice);
}
}
void display_main_choices(void){
printf("******************* Main Operations ****************\n");
printf(" 1 - Insertion\n");
printf(" 2 - Deletion\n");
printf(" 3 - Display\n");
printf(" Note : Enter -1 to QUIT\n");
printf("Please choose one option : ");
}
void display_insertion_choices(void){
printf("****************** Insertion Choices ***************\n");
printf(" 1 - Insertion at beginnning\n");
printf(" 2 - Insertion at end\n");
printf(" 3 - Insertion after a given node\n");
printf(" 4 - Insertion before a given node\n");
printf(" NOTE : Enter -1 to go to main menu\n");
printf("Please choose one option : ");
}
void display_deletion_choices(void){
printf("**************** Deletion Choices **************\n");
printf(" 1 - Deeltion at beginning\n");
printf(" 2 - Deletion at end\n");
printf(" 3 - Deletion after a given node\n");
printf(" 4 - Deletion before a given node\n");
printf(" NOTE : Enter -1 to go to main menu\n");
printf("Please choose one option : ");
}
void insertion_beginning(void){
struct node *newnode, *tmp;
tmp = start;
if(start == NULL){
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data for the newnode : ");
scanf("%d",&newnode->data);
newnode->next = NULL;
newnode->prev = NULL;
start = newnode;
}else{
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data for the newnode : ");
scanf("%d",&newnode->data);
newnode->prev = NULL;
newnode->next = start;
start->prev = newnode;
start = newnode;
}
}
void insertion_end(void){
struct node *newnode, *tmp;
tmp = start;
if(start == NULL){
insertion_beginning();
}
else{
while(tmp->next){
tmp = tmp->next;
}
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data for the new node : ");
scanf("%d",&newnode->data);
newnode->next = NULL;
newnode->prev = tmp;
tmp->next = newnode;
}
}
void insertion_after_given_node(void){
struct node *newnode, *tmp, *tmp2;
int node, found = 1;
tmp = start;
if(start == NULL){
printf("Linked List is empty till now. Please choose insertion at beginning\n");
}
else{
printf("Enter the node value : ");
scanf("%d",&node);
if(start->next == NULL){
if(start->data == node)
insertion_end();
else
printf("Wrong node entered. Please choose again.\n");
}
else{
while(tmp->data != node){
tmp = tmp->next;
if(tmp == NULL){
found = 0;
break;
}
}
if(found == 1){
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data for the newnode : ");
scanf("%d",&newnode->data);
tmp2 = tmp->next;
tmp->next = newnode;
newnode->prev = tmp;
newnode->next = tmp2;
}else{
printf("Node is not present in the existed linked list. Please choose again\n");
}
}
}
}
void insertion_before_given_node(void){
struct node *newnode, *tmp, *tmp2;
int node, found = 1;
tmp = start;
if(start == NULL){
printf("Linked List is empty till now. Please choose again\n");
}
else{
printf("Enter the node value : ");
scanf("%d",&node);
if(start->next == NULL){
if(start->data == node){
insertion_beginning();
}
else{
printf("Wrong node entered. Please choose again\n");
}
}
else if(start->data == node){
insertion_beginning();
}
else{
while(tmp->next->data != node){
tmp = tmp->next;
if(tmp->next == NULL){
found = 0;
break;
}
}
if(found == 1){
tmp2 = tmp->next;
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data for the new node : ");
scanf("%d",&newnode->data);
tmp->next = newnode;
newnode->prev = tmp;
newnode->next = tmp2;
}
else{
printf("Entered node value is not in the linked list. Please chooose again\n");
}
}
}
}
void deletion_beginning(void){
struct node *tmp;
if(start == NULL){
printf("Linked List is empty. Deletion is not possible.\n");
}
else{
tmp = start->next;
free(start);
start = tmp;
if(start != NULL){
start->prev = NULL;
}
}
}
void deletion_end(void){
struct node * tmp;
tmp = start;
if(start == NULL){
printf("Linked List is empty. Deletion is not possible.\n");
}
else{
if(start->next == NULL){
free(start);
start = NULL;
}
else{
while(tmp->next->next ){
tmp = tmp->next;
}
free(tmp->next);
tmp->next = NULL;
}
}
}
void deletion_after_given_node(void){
struct node *tmp, *tmp2;
tmp = start;
int node, found=1;
if(start == NULL){
printf("Sorry ! Linked List is empty. Please choose again.\n");
}
else{
printf("Enter the node value : ");
scanf("%d",&node);
if(start->next == NULL){
if(start->data == node){
printf("Sorry ! There is no node after the entered node value.\n");
}
else{
printf("Sorry ! Node value is not found.\n");
}
}
else{
while(tmp->data != node){
tmp = tmp->next;
if(tmp == NULL){
found = 0;
break;
}
}
if(found == 1){
if(tmp->next == NULL){
printf("Sorry ! There is no node after the entered node value.\n");
}else{
if(tmp->next->next == NULL){
deletion_end();
}else{
tmp2 = tmp->next;
tmp->next = tmp->next->next;
tmp->next->next->prev = tmp;
free(tmp2);
}
}
}else{
printf("Sorry ! Entered node value is not found in the existed linked list.\n");
}
}
}
}
void deletion_before_given_node(void){
struct node *tmp, *tmp2;
int node,found = 1;
tmp = start;
if(start == NULL){
printf("Sorry ! Linked List is empty. Deletion is not possible.\n");
}else{
printf("Enter the node value : ");
scanf("%d",&node);
if(start->data == node){
printf("Sorry ! There is no node before the entered node value.\n");
}
else if(start->next->next == NULL){
if(start->next->data == node)
deletion_beginning();
else
printf("Node value is not present.\n");
}
else if(start->next->data == node){
deletion_beginning();
}else{
while(tmp->next->next->data != node){
tmp = tmp->next;
if(tmp->next->next == NULL){
found = 0;
break;
}
}
if(found == 1){
tmp2 = tmp->next->next;
free(tmp->next);
tmp->next = tmp2;
tmp2->prev = tmp;
}else{
printf("Sorry ! There is no node value that you have entered.\n");
}
}
}
}
void display_elements(void){
struct node *tmp;
tmp = start;
printf("******************** Elements in the linked list *****************\n");
while(tmp){
printf("%d\n",tmp->data);
tmp = tmp->next;
}
}
QUESTION TWO:
Initially queue is 30->25->5->15->10
(i) After deleting two elements, queue is 5->15->10. This is because as queue follows first in first out principle.
(ii) After inserting 7 and then 20, queue is 5->15->20->7->20;
(iii) After deleting one element, queue is 15->20->7->20;
venereology answered 1 year agoRelated Solutions
Can you make this singular linked list to doubly linked list Create a Doubly Linked List....
Can you make this singular linked list to doubly linked
list
Create a Doubly Linked List.
Use this to create a Sorted Linked List,
Use this to create a prioritized list by use. Bring to front
those links recently queried.
-----link.h------
#ifndef LINK_H
#define LINK_H
struct Link{
int data;
Link *lnkNxt;
};
#endif /* LINK_H */
----main.cpp----
//System Level Libraries
#include <iostream> //I/O Library
using namespace std; //Libraries compiled under std
#include"Link.h"
//Global Constants - Science/Math Related
//Conversions, Higher Dimensions...
A circular doubly-linked list .(a) In a circular doubly-linked list, there is no front or end;...
A circular doubly-linked list
.(a) In a circular doubly-linked list, there is no front or end;
the nodes form a full circle. Instead of keeping track of the node
at the front, we keep track of a current node instead. Write a
class for a circular doubly-linked list using the attached Job
class as your node objects. It should have:
• A private instance variable for the current node
• A getCurrent() method that returns a reference to the current...
TITLE Updating Accounts Using Doubly Linked List TOPICS Doubly Linked List DESCRIPTION General Write a program...
TITLE
Updating Accounts Using Doubly Linked List
TOPICS
Doubly Linked List
DESCRIPTION
General
Write a program that will update bank accounts stored in a
master file using updates from a transaction file. The program will
maintain accounts using a doubly linked list.
The input data will consist of two text files: a master file and
a transaction file. See data in Test section below. The
master file will contain only the current account data. For each
account, it will contain account...
9.7 LAB: Inserting an integer in descending order (doubly-linked list) Given main() and an IntNode class,...
9.7 LAB: Inserting an integer in descending order (doubly-linked
list)
Given main() and an IntNode class, complete the IntList class (a
linked list of IntNodes) by writing the insertInDescendingOrder()
method to insert new IntNodes into the IntList in descending
order.
Ex. If the input is:
3 4 2 5 1 6 7 9 8 -1
the output is:
9 8 7 6 5 4 3 2 1
Sortedlist.java
import java.util.Scanner;
public class SortedList {
public static void main (String[] args)...
I was supposed to conver a singly linked list to a doubly linked list and everytime...
I was supposed to conver a singly linked list to a doubly linked
list and everytime I run my program the output prints a bunch of
random numbers constantly until I close the console.
Here is the code.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
struct node {
int data;
struct node *next;
struct node *prev;
};
//this always points to first link
struct node *head = NULL;
//this always points to last link
struct node *tail = NULL;...
Write in C++: create a Doubly Linked List class that holds a struct with an integer...
Write in C++:
create a Doubly Linked List class that holds a struct with an
integer and a string. It must have append, insert, remove, find,
and clear.
HI i will write user's manual for a doubly/singly linked list , How can i write...
HI i will write user's manual for a doubly/singly linked list ,
How can i write User's manual ?
Write a program of doubly Circular linked list to maintain records of employees. Take employee ID,...
Write a program of doubly Circular linked list to maintain
records of employees. Take employee ID, name and salary as data of
each employee. Search a particular record on ID and display the
previous and next records as well. Whichever ID it give, it should
display all the records because of being circular.
Code needed in Java.
Write PSEUDOCODE to insert a node at position 2 in a doubly-linked list (assume position follows...
Write PSEUDOCODE to insert a node at position 2 in a
doubly-linked list (assume position follows classic indexing from 0
to item_count - 1)
Evaluate and write an algorithm to find the largest item in an unsorted singly linked list...
Evaluate and write an algorithm to find the largest item in an
unsorted singly linked list with cells containing integers
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- Based on the loanable funds theory, explain how each of the following changes should impact interest...
- research paper: each student will be responsible for writing an argumentative research paper discussion a topic...
- In java based on the classes provided finish the program per the requirements: ----------------------------------------------Class1 package cardgame;...
- Identify two cultures and analyze the nurturing process within each culture and discuss the impact the...
- Digital security is an increasing concern is the Internet age. In order to protect sensitive information...
- the challenges experienced by companies considering full application of customer retention strategy in the face of...
- Respond to the following in a minimum of 175 words: The flow of a program is...
ADVERTISEMENT