Question

Consider a data structure with the following operations: INSERT(x), which inserts a given element x into the data structure • DELETE(x), which removes a given element x from the data structure, should it be present • MIN() which returns but doesn't remove the minimum element from the data structure Show that at least one of INSERT, DELETE, and MIN must take w(1) time to run.

Answer 1

INSERT (X) Linked List perform insertion in w(1) time. tail head Algorithm new node if (head == NULL) { head=ni tail an; an else { tail. next: ni tail - hi takes Delete (x) Ocn) time. time. min () takes och)

void deletekey(int key) { // Store head node Node temp = head, prev = null; // If head node itself holds the key // or multiple occurrences of key while (temp != null && temp.data key) { head temp temp.next; // Changed head head; // Change Temp } // Delete occurrences other than head while (temp != null) { // Search for the key to be deleted, // keep track of the previous node // as we need to change 'prev->next' while (temp != null && temp.data != key) { prev = temp; temp temp.next; سها // If key was not present in linked list if (temp == null) return; // Unlink the node from linked list prev.next = temp.next;

static int smallestElement(Node head) { // Declare a min variable and initialize // it with INT_MAX value. // INT_MAX is integer type and its value // is 32767 or greater. int min = Integer .MAX_VALUE; // Check loop while head not equal to NULL while (head != null) { // If min is greater then head->data then // assign value of head->data to min // otherwise node point to next node. if (min > head.data) min - head.data; head = head.next; } return min; بہا

if you have any doubts aks me...