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 9 months agoRelated Solutions
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)...
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.
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.
I know this code takes in a set of numbers into a doubly linked list and...
I know this code takes in a set of numbers into a doubly linked
list and sorts it using insertion sort. Could you explain exactly
how this code is working?
main.c Source Code:
#include
#include
#include "node.h"
int main()
{
struct mynode *head=NULL;
int value;
printf("Give first value: \n");
scanf("%d",&value);
printf("Give next values, and input 0 to end list: \n");
do{
if(value>0){
head = pushNode(head, value);
scanf("%d",&value);
}
}while (value>0);
printf("Before insertion sort: ");
printlist(head);
head=insertsort(head);
printf("After insertion...
This is the code what I have for doubly linked list for STACK. This is Python...
This is the code what I have for doubly linked list for STACK.
This is Python language and I want anyone to help me with the
following questions. Can you check for me if it is good Doubly
Linked List?
####THIS IS THE ENTIRE ASSIGNMENT####
ADD the Following feature:
Include a class attribute in the container class called
name.
In the implementation - Pod:
You should ask the user to enter the name of the container and
the program should...
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
(15 pts) Describe an O(n)-time algorithm that partitions a doubly linked list L into two doubly...
(15 pts) Describe an O(n)-time algorithm that partitions a
doubly linked list L into two doubly linked lists L1 and L2, where
L1 contains the odd-number-th elements in L and L2 contains the
even-number-th elements in L. Elements in both L1 and L2 should
appear in the same order as they appear in L. For example, if L
contains the numbers 4, 7, 9, 1, and -3, in that order, then the
output L1 should contain 4, 9, and -3,...
Description The purpose of this challenge is to implement a circular doubly-linked list using a dummy...
Description
The purpose of this challenge is to implement a
circular doubly-linked list using a dummy node. This challenge
simulates an operating system’s window manager.
Requirements
Write the following struct
struct Window { string appname; Window *next; Window
*prev; };
Create a class called WindowManager. In this
class, create a private variable Window * head. This will
keep track of the location of the head node.
Create private variables Window * current, *
dummy. current will keep track of the...
I need an example of how to swap and index within a doubly linked list with...
I need an example of how to swap and index within a doubly
linked list with index + 1. This is written in java.
public class A3DoubleLL<E> {
/*
* Grading:
* Swapped nodes without modifying values - 2pt
* Works for all special cases - 1pt
*/
public void swap(int index) {
//swap the nodes at index and
index+1
//change the next/prev connections,
do not modify the values
...
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- PLEASE ANSWER C&D ONLY . THE REST HAS ALREADY BEEN ANSWERED. Say the marginal tax rate...
- What's your opinion of the economy now?
- . Air in a 0.3 m3 cylinder is initially at a pressure of 10 bar and...
- the effects of the inhalation of smoke and E-cigarette vapor on gas exchange in the lungs;...
- During the 2004 Olympic Games, a shot putter threw a shot put with a speed of...
- A double pane window consists of two pieces of glass each of 8 mm thick that...
- DISTINGUISH BETWEEN ECONOMIES OF SCALE AND DISECONOMIES OF SCALE TRUE OR FALSE. A PRODUCER CAN OPERATE...
ADVERTISEMENT