I need justify and explain briefly in at least 3 sentences the complexity of each operation in buffer operations in terms of Big O notation of the below code: struct Node { char data; struct Node *next; }; struct Node* head1 = NULL; struct Node* head = NULL; void push(struct Node** head_ref, char new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void print_list(struct Node* Head) { printf("values are: "); while(Head) { printf("%c ", Head->data); Head = Head->next; } printf("\n"); } bool isEmpty() { return head == NULL; } void pop(struct Node **head_ref, int position) { // If linked list is empty if (*head_ref == NULL) return; // Store head node struct Node* temp = *head_ref; // If head needs to be removed if (position == 0) { *head_ref = temp->next; // Change head free(temp); // free old head return; } int i; // Find previous node of the node to be deleted for (i=0; temp!=NULL && inext; // If position is more than number of nodes if (temp == NULL || temp->next == NULL) return; // Node temp->next is the node to be deleted // Store pointer to the next of node to be deleted struct Node *next = temp->next->next; // Unlink the node from linked list free(temp->next); // Free memory temp->next = next; // Unlink the deleted node from list } char GetNth(struct Node* head, int index) { struct Node* current = head; int count = 0; // the index of the node we're currently looking at if ( index < 0 ) { printf( "invalid -ve index passes\n" ); //assert(0); } //printf( "starting ptr %p\n", current ); while (current != NULL) { //printf( "checking value %d against %d for ptr %p", count, index, current ); if (count == index) { printf( "found\n" ); return(current->data); } count++; current = current->next; } printf( "not found\n" ); //assert(0); // if we get to this line, the caller was asking // for a non-existent element so we assert fail. } void find_data(char item) { struct Node* current = (struct Node*) malloc(sizeof(struct Node)); int pos = 0; if(head==NULL) { printf("Linked List not initialized"); return; } current = head; while(current!=NULL) { if(current->data == item) { printf("%c found at position %d\n", item, pos); return; } current = current->next; pos++; } printf("%c does not exist in the list", item); } int getCountOfList() { struct Node* temp = head; //assign a temp node to the head of the list int count=0; while(temp) { count++; temp = temp->next; //move to next node } return count; } void left(int k){ int i; for (i = k; i >= 0; i--){ push(&head, head1->data); printf("Place = %d", k); pop(&head1, head1->data); } printf("cusrsor is shifted to %d pos left", k); } void right(int k){ int i=0; while (i!=k&&!head){ push(&head1, head->data); pop(&head,head1->data); i++; } printf("cusrsor is shifted to %d pos right", k); } void main() { int ch, a; char val, nval; //struct Node * head = NULL; printf("1) Push in list\n"); printf("2) Pop in list\n"); printf("3) Display value at nth position\n"); printf("4) Display values in buffer\n"); printf("5) Display values position\n"); printf("6) Get size\n"); printf("7) Move left\n"); printf("8) Move right\n"); printf("9) Exit\n"); do { printf("\nEnter choice: " ); scanf("%d", &ch); getchar(); switch(ch) { case 1: { printf("Enter value to be pushed: "); scanf("%c", &val); push(&head, val); break; } case 2: { int pos; printf("Enter position number that you want to pop in stack: "); scanf("%d", &pos); pop(&head, pos); break; } case 3: { printf("Enter the position number: "); scanf("%d", &a); nval = GetNth(head, a); printf("Char at Position number: %c", nval); break; } case 4: { print_list(head); break; } case 5: { char value; printf("Enter value to search their position in buffer: "); scanf("%c", &value); find_data(value); break; } case 6: { printf("size of buffer: %d", getCountOfList()); break; } case 7: { int j, place; printf("Enter how many places you want to move to left: "); scanf("%d", &j); int i = getCountOfList(); place = i - j; if (place < 0) { printf("not enough places in stack\n"); left(i); }else { left(place); } break; } case 8: { int j, place; printf("Enter how amny places you want to move to right: "); scanf("%d", &j); int i = getCountOfList(); place = i + j; if (place > i) { printf("not enough places in stack\n"); } else{ right(j); } break; } case 9: { printf("Exit"); break; } default: { printf("Invalid Choice"); } } }while(ch!=9); }
I need justify and explain briefly in at least 3 sentences the complexity of each operation in buffer operations in terms of Big O notation of the below code:
struct Node {
char data;
struct Node *next;
};
struct Node* head1 = NULL;
struct Node* head = NULL;
void push(struct Node** head_ref, char new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void print_list(struct Node* Head)
{
printf("values are: ");
while(Head)
{
printf("%c ", Head->data);
Head = Head->next;
}
printf("\n");
}
bool isEmpty() {
return head == NULL;
}
void pop(struct Node **head_ref, int position)
{
// If linked list is empty
if (*head_ref == NULL)
return;
// Store head node
struct Node* temp = *head_ref;
// If head needs to be removed
if (position == 0)
{
*head_ref = temp->next; // Change head
free(temp); // free old head
return;
}
int i;
// Find previous node of the node to be deleted
for (i=0; temp!=NULL && i<position-1; i++)
temp = temp->next;
// If position is more than number of nodes
if (temp == NULL || temp->next == NULL)
return;
// Node temp->next is the node to be deleted
// Store pointer to the next of node to be deleted
struct Node *next = temp->next->next;
// Unlink the node from linked list
free(temp->next); // Free memory
temp->next = next; // Unlink the deleted node from list
}
char GetNth(struct Node* head, int index) {
struct Node* current = head;
int count = 0; // the index of the node we're currently looking at
if ( index < 0 ) {
printf( "invalid -ve index passes\n" );
//assert(0);
}
//printf( "starting ptr %p\n", current );
while (current != NULL) {
//printf( "checking value %d against %d for ptr %p", count, index, current );
if (count == index) {
printf( "found\n" );
return(current->data);
}
count++;
current = current->next;
}
printf( "not found\n" );
//assert(0);
// if we get to this line, the caller was asking
// for a non-existent element so we assert fail.
}
void find_data(char item) {
struct Node* current = (struct Node*) malloc(sizeof(struct Node));
int pos = 0;
if(head==NULL) {
printf("Linked List not initialized");
return;
}
current = head;
while(current!=NULL) {
if(current->data == item) {
printf("%c found at position %d\n", item, pos);
return;
}
current = current->next;
pos++;
}
printf("%c does not exist in the list", item);
}
int getCountOfList()
{
struct Node* temp = head; //assign a temp node to the head of the list
int count=0;
while(temp) {
count++;
temp = temp->next; //move to next node
}
return count;
}
void left(int k){
int i;
for (i = k; i >= 0; i--){
push(&head, head1->data);
printf("Place = %d", k);
pop(&head1, head1->data);
}
printf("cusrsor is shifted to %d pos left", k);
}
void right(int k){
int i=0;
while (i!=k&&!head){
push(&head1, head->data);
pop(&head,head1->data);
i++;
}
printf("cusrsor is shifted to %d pos right", k);
}
void main() {
int ch, a;
char val, nval;
//struct Node * head = NULL;
printf("1) Push in list\n");
printf("2) Pop in list\n");
printf("3) Display value at nth position\n");
printf("4) Display values in buffer\n");
printf("5) Display values position\n");
printf("6) Get size\n");
printf("7) Move left\n");
printf("8) Move right\n");
printf("9) Exit\n");
do {
printf("\nEnter choice: " );
scanf("%d", &ch);
getchar();
switch(ch) {
case 1: {
printf("Enter value to be pushed: ");
scanf("%c", &val);
push(&head, val);
break;
}
case 2: {
int pos;
printf("Enter position number that you want to pop in stack: ");
scanf("%d", &pos);
pop(&head, pos);
break;
}
case 3: {
printf("Enter the position number: ");
scanf("%d", &a);
nval = GetNth(head, a);
printf("Char at Position number: %c", nval);
break;
}
case 4: {
print_list(head);
break;
}
case 5: {
char value;
printf("Enter value to search their position in buffer: ");
scanf("%c", &value);
find_data(value);
break;
}
case 6: {
printf("size of buffer: %d", getCountOfList());
break;
}
case 7: {
int j, place;
printf("Enter how many places you want to move to left: ");
scanf("%d", &j);
int i = getCountOfList();
place = i - j;
if (place < 0) {
printf("not enough places in stack\n");
left(i);
}else {
left(place);
}
break;
}
case 8: {
int j, place;
printf("Enter how amny places you want to move to right: ");
scanf("%d", &j);
int i = getCountOfList();
place = i + j;
if (place > i) {
printf("not enough places in stack\n");
}
else{
right(j);
}
break;
}
case 9: {
printf("Exit");
break;
}
default: {
printf("Invalid Choice");
}
}
}while(ch!=9);
}
Step by step
Solved in 4 steps
