1 answer

IN C ONLY PLZ (read the instruction carefully plz) You will implement the following functions: List...

Question:

IN C ONLY PLZ (read the instruction carefully plz)

You will implement the following functions:

List * initIntegerList( ) // Return empty list

int insertAtHead(int k, List*) // Insert k at head

int insertAtTail(int k, List*) // Insert k at tail

int removeHead(List *) // Remove head and return its key

int getListSize(List *) // Return number of elements in list

void printHead(List *) // Print key in head

void moveHeadToTail(List *) // Move key at head to tail

This doesn’t seem so bad – and it isn’t. However, there is a performance requirement that must be satisfied: all of the functions must take only a constant amount of time independent of the length of the list, i.e., they must all have O(1) complexity. Does this make things much more difficult? No, you just need to define a struct (List) that contains a pointer to the head of a linked list; a pointer to the tail of the list; and an integer containing the number of items/keys in the list. (Note that nodes in the linked list will not be List structs.) The information in the List struct is what will allow all operations to be satisfied in O(1) time.

Note that the above prototypes impose restrictions on how you handle potential error conditions, e.g., if the user tries to remove the head of an empty list, so you will need to document those situations for the user. For example, the function printHead will need documentation telling the user that nothing is printed if the list is empty. The two insert functions, however, have integer return values that can be used for error codes.


Answers

// C program to implement Linked list operations in O(1) time

#include <stdio.h>

#include <stdlib.h>

// structure to represent a node in the linked list

typedef struct Node

{

       int data;

       struct Node *next;

}Node;

// structure to represent the list

typedef struct List

{

       Node *head;

       Node *tail;

       int size;

}List;

// function prototype

List * initIntegerList( ); // Return empty list

int insertAtHead(int k, List*); // Insert k at head

int insertAtTail(int k, List*); // Insert k at tail

int removeHead(List *); // Remove head and return its key

int getListSize(List *); // Return number of elements in list

void printHead(List *); // Print key in head

void moveHeadToTail(List *); // Move key at head to tail

int main(void) {

       printf("\nInsert At Head :");

       List *list = initIntegerList();

       int result;

       if(list != NULL)

       {

             int i;

             for(i=1;i<=5;i++ )

             {

                    result = insertAtHead(i,list);

                    if(result == 0)

                    {

                           exit(1);

                    }

                    printHead(list);

             }

             printf("\nInsert At Tail :");

             for(i=6;i<=10;i++)

             {

                    result = insertAtTail(i,list);

                    if(result == 0)

                           exit(1);

             }

             printHead(list);

             printf("\nSize : %d",getListSize(list));

             printf("\nMove Head to Tail :");

             for(i=0;i<getListSize(list);i++)

             {

                    printHead(list);

                    moveHeadToTail(list);

             }

             printHead(list);

             printf("\nSize : %d",getListSize(list));

             printf("\nRemove Head :");

             while(getListSize(list) > 0)

             {

                    //printHead(list);

                    printf("\nRemoved : %d",removeHead(list));

             }

       }

       return EXIT_SUCCESS;

}

// function that creates and returns a new empty list, returns NULL if memory allocation failed

List * initIntegerList( ) // Return empty list

{

       // create a new List

       List *list = (List*)malloc(sizeof(List));

       // check if memory is allocated successfully

       if(list != NULL)

       {

             // initialize head and tail to NULL and set size to 0

             list->head = NULL;

             list->tail = NULL;

             list->size = 0;

       }

       return list; // return list

}

// function to insert the node at the head of the list

// returns 1 if insertion is successful else 0

int insertAtHead(int k, List *list) // Insert k at head

{

       Node *node = (Node*)malloc(sizeof(Node)); // create a new node to contain k

       // if memory allocation is successful

       if(node != NULL)

       {

             // insert the node at head

             node->data = k;

             node->next = list->head;

             list->head = node;

             if(list->tail == NULL)

                    list->tail = node;

             list->size++;

             return 1; // insertion successful

       }

       return 0; // insertion unsuccessful

}

// function to insert a node at the tail

// returns 1 if insertion is successful else 0

int insertAtTail(int k, List *list) // Insert k at tail

{

       // create a new node to contain k

       Node *node = (Node*)malloc(sizeof(Node));

       // if memory allocation is successful

       if(node != NULL)

       {

             // insert node at the tail

             node->data = k;

             node->next = NULL;

             if(list->tail !=NULL)

             {

                    list->tail->next = node;

             }else

                    list->head = node;

             list->tail = node;

             list->size++;

             return 1; // insertion successful

       }

       return 0; // insertion unsuccessful

}

// function to remove and return the value at the head of the list

// return the key value if deletion is successful else returns -999

int removeHead(List *list) // Remove head and return its key

{

       if(list->head == NULL) // empty list

       {

             printf("\nEmpty list");

             return -999;

       }

       else

       {

             // delete the node at the head

             int k = list->head->data;

             Node *node = list->head;

             list->head = list->head->next;

             if(list->head == NULL)

                    list->tail = NULL;

             list->size--;

             free(node);

             return k;

       }

}

// function to return the size of the list

int getListSize(List *list) // Return number of elements in list

{

       return list->size;

}

// function to print the value at the head of the list

void printHead(List *list) // Print key in head

{

       if(list->head == NULL) // empty list

             printf("\nEmpty list");

       else // non-empty list

             printf("\nHead : %d",list->head->data);

}

// function to move the node at head to the tail

void moveHeadToTail(List *list) // Move key at head to tail

{

       if(list->head == NULL) // empty list

             printf("\nEmpty list");

       else

       {

             if(list->head->next != NULL) // more than 1 node

             {

                    // move the head node to tail

                    Node *node = list->head;

                    list->head = list->head->next;

                    node->next = NULL;

                    list->tail->next = node;

                    list->tail = node;

             }else // 1 node so no movement

                    printf("\nList has only one element");

       }

}

//end of program

Output:

Insert At Head Head 1 Head 2 Head 3 Head 4 Head 5 Insert At Tail Head 5 Size 10 Move Head to Tail Head 5 Head 4 Head 3 Head 2

.

Similar Solved Questions

1 answer
The system is subject to a pressure of 101.175kPa on the right side. If PA=146kPa, what...
The system is subject to a pressure of 101.175kPa on the right side. If PA=146kPa, what is the length L of the manometer? (Note: the manometer is filled with both, mercury and water, and the angle is measured with respect to the vertical axis) Consider 7Hg=132.756kN/m3, SGair=2.0x10-3, PH20=997.5kg/...
1 answer
A box with an initial speed of #5 m/s# is moving up a ramp. The ramp has a kinetic friction coefficient of #7/5 # and an incline of #(5 pi )/12 #. How far along the ramp will the box go?
A box with an initial speed of #5 m/s# is moving up a ramp. The ramp has a kinetic friction coefficient of #7/5 # and an incline of #(5 pi )/12 #. How far along the ramp will the box go?...
1 answer
All of these problems should be done by hand. You may use a computer or calculator...
All of these problems should be done by hand. You may use a computer or calculator to find roots of polynomials with constant coefficients. All hand calculations can of course be verified with a computer. Show calculations for asymptote angles, center of mass, angles of departure, etc. for full cred...
1 answer
Need help on this. Thanks in advance Question 7 Determine whether the set of vectors is...
need help on this. Thanks in advance Question 7 Determine whether the set of vectors is a basis for R3. s{{JAMA). Given the set of vectors decide which of the following statements is true: A: Set is linearly independent and spans R. Set is a basis for R. B: Set is linearly independent but does no...
1 answer
You are considering purchasing a CNC machine which costs $140,000. This machine will have an estimated...
You are considering purchasing a CNC machine which costs $140,000. This machine will have an estimated service life of 9 years with a net after-tax salvage value of $14,000. Its annual after-tax operating and maintenance costs are estimated to be $52,000. To expect an 16% rate of return on investmen...
1 answer
Which is correct and why is it correct The profit from a put bear spread strategy...
Which is correct and why is it correct The profit from a put bear spread strategy when both options are out of the money is O-X1 + ST + P1 + X2 - ST - P2 0 -X1 + ST + P1 - P2 O X1 - ST-P1 - X2 + ST + P2 O P1 + x2 - ST-P2 o P1 – P2...
1 answer
Which attacking species shown below would be the best choice to enforce an E2 pathway over...
Which attacking species shown below would be the best choice to enforce an E2 pathway over an Sp2 pathway for the reaction below? Attacking Species? Br H CH,MpBr HC-0 NH (a) H (b) e OH H₂C_&_• SH Els (d) (1)...
1 answer
Material science Questions: In the given crystal structure ? (1) Write the postions for the four...
material science Questions: In the given crystal structure ? (1) Write the postions for the four dots. (II) Write the direction for the arrow....
1 answer
36. The transition from Phase 2 to Phase 3 of the Demographic Cycle is often referred...
36. The transition from Phase 2 to Phase 3 of the Demographic Cycle is often referred to as the Demographic Transition. a. What are the socio-economic correlates of this transition? b. What population policies does the transition suggest?...
1 answer
Which of the following is true regarding fermentation? Group of answer choices Fermentation occurs in the...
Which of the following is true regarding fermentation? Group of answer choices Fermentation occurs in the cell membrane of organisms Yeast produces lactic acid through fermentation At the end of fermentation NADH is converted back into NAD+ The end product pyruvate proceeds into the Krebs cycle...
1 answer
Find the principal needed now to get the given amount; that is, find the present value....
Find the principal needed now to get the given amount; that is, find the present value. To get $300 after 2 years at 7% compounded monthly The present value of $300 is $ (Round to the nearest cent as needed)...
1 answer
06: The results shown in the table below were obtained from a series of consolidated- undrained...
06: The results shown in the table below were obtained from a series of consolidated- undrained triaxial tests for specimens of saturated clay. Answer TWO of the followings: (a) Compute effective principle stresses for all specimens (b) Draw (by scale) Mohr Circle for total and effective stresses fo...
1 answer
Use electron pushing/arrow formalism that shows the formation of your proposed product in the previous problem.
Use electron pushing/arrow formalism that shows the formation of your proposed product in the previous problem....
1 answer
What is the antiderivative of # (5x)/(x^2+1) #?
What is the antiderivative of # (5x)/(x^2+1) #?...
1 answer
Five cubic feet of an aqueous hydrochloric acid (HCl) having a molarity of 2.0 is to...
Five cubic feet of an aqueous hydrochloric acid (HCl) having a molarity of 2.0 is to be prepared. Assuming the SG of the solutions is 1.02, determine: (a) How many gram of pure HCl is needed? (b) How many liters of pure water is needed? (c) What is the mole fraction of HCl in the solution? (d) What ...
1 answer
1. a. Complete the Ramachandran Plot below: label each axis with its name and angle values...
1. a. Complete the Ramachandran Plot below: label each axis with its name and angle values by filling in the blanks. On the plot, place an "X" approximately where an amino acid might be found that is part of a protein, with 6 = +105° and y=-115º. Next place a "O" on the plot...
1 answer
014 10.0 points How much energy is required to change a 35 g ice cube from...
014 10.0 points How much energy is required to change a 35 g ice cube from ice at -12°C to steam at 111°C? The specific heat of ice is 2090 J/kg.° C, the specific heat of water is 4186 J/kg.° C, the specific heat of stream is 2010 J/kg.° C, the heat of fusion is 3.33 x 10° J/...
1 answer
Find The number of teeth of the gear, the pitch circle diameter, the pitch circle diameter...
Find The number of teeth of the gear, the pitch circle diameter, the pitch circle diameter of the worm, the lead angle, the pitch circumferential speed, and the tangential force component of the worm(= Axial force component of the worm), slip velocity(Coefficient friction=0.026), tangential force co...