Objective: Implement a simple data structure and verify its runtime complexity a

Question

Objective: Implement a simple data structure and verify its runtime complexity analysis

Synopsis: A sorted doubly linked list is a doubly-linked list that keeps all its content in order, either ascending or descending. Usually

Requirements: Implement the sorted doubly-linked list class with the standard inserting, deleting, and searching capabilities. You must use the given header file. Here is a list of items that must be done:

1. Implement all the functionalities listed in the header file

2. Design and implement a simple main program to test your class implementation and verify your analysis. You should use at least 15 set of random data with various size ranging from 100,000 to 100M. Each set of data must be tested 100 times to get the average time.

3. Graph your run-time vs. data and compare it with your previous analysis.

Explanation / Answer

#include#include#includetypedef struct dll { int data; struct dll *next,*prev; }node; int n; node *head; void create(); void insert(); void delete(); void display(); int main() { int choice; do { printf(" >>>>>>DOUBLY LINKED LIST ",temp->data); temp=temp->next; } while(temp!=NULL); getch(); } void insert() { node *temp,*new,*temp1; int loc,data,i; printf(" ENTER THE DATA IN THE NEW NODE: "); scanf("%d",&data); printf(" ENTER THE LOCATION OF THE NEW NODE: "); scanf("%d",&loc); new=(node*)malloc(sizeof(node)); if(loc==1) { new->data=data; new->next=NULL; new->prev=head->prev; temp=head->prev; temp->prev=new; } else { temp=head; for(i=2;(inext!=head));i++) {temp=temp->next;} temp1=temp->next; new->data=data; temp->next=new; new->prev=temp; temp1->prev=new; new->next=temp1; } n++; printf(" AFTER INSERTION: "); display(); } void delete() { node *new,*temp,*tempr,*templ; int ne; printf(" ENTER THE DATA TO BE DELETED: "); scanf("%d",&ne); temp=head; while(temp->data!=ne) { temp=temp->next; } templ=temp->prev; tempr=temp->next; free(temp); templ->next=tempr; tempr->prev=templ; printf(" AFTER DELETION "); display(); }

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.