Assume you have a sorted linked list of words (strings). Write C++ classes and a

Question

Assume you have a sorted linked list of words (strings). Write C++ classes and a C++ function to insert a node into a doubly linked list in the middle of the list (in decreasing order). Consider the list may be empty and duplicates are allowed. Explain best and worst case for an insertion

Explanation / Answer

1. template 2. Iterator List::insert(Iterator pos, const T& newItem) 3. { 4. LNode* nodePtr; 5. nodePtr = new LNode(newItem); 6. 7. if(pos == head) 8. { 9. nodePtr->prev = NULL; 10. nodePtr->next = head; 11. head->prev = nodePtr; 12. head = nodePtr; 13. } 14. if(pos != head && pos != tail) 15. pos->prev = nodePtr; 16. if(pos == tail) 17. { 18. nodePtr->next = NULL; 19. nodePtr->prev = tail; 20. tail->next = nodePtr; 21. tail = nodePtr; 22. } 23. return Iterator(nodePtr); 24. }

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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