C++ Programming Exercises: 1) We want to implement list of items sorted by some

Question

C++ Programming Exercises:

1) We want to implement list of items sorted by some attribute. (For example they might be books, sorted by their ISBN numbers.) Operations include getMin(), removeMin(), getMax(), removeMax(), getItem(position), insert(item, position), remove(item, position). Discuss the pros and cons of using an array vs. a linked list for our implementation?

2) In a doubly linked list each DNode has a both a previous pointer and a next pointer in addition to member int val. Suppose we want to insert a value v into the list right after the DNode pointed to by p. Write one or more statements to accomplish this. The DNode struct type has members int value, DNode *previous and DNode* next.

Can someone please give me the answers for these two problems?

Explanation / Answer

If our list and arrays are sorted

1.

getMin() takes constant time for both array and linked list implementations

since you just have to return the first element

2.

removeMin() takes constant time for linked list and linear time for array implementations

since removing first node is easy for linked lists

but for arrays you have to rearrange the elements

3.

getMax() and removeMax() takes constant time for arrays

getMax() and removeMax() takes linear time for linked lists

since, you have to go till the end of the list

getItem(position) takes constant time for arrays

and linear time(position) for linked lists

insert and remove takes linear time for both arays and linked lists

__________________________________________________________________________________

Dnode *temp = new node;
temp->value = v;
temp->next = p->next;
if (temp->next != NULL){
   temp->next->previous = temp;
}
p->next = temp;
temp->previous = p;

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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