Question
Implementing an add function that will also sort in ascending order for a doubly linked list in C++.
I am having trouble implementing an add function with an algorithm that will add an item to the list and sort the doubly linked list in ascending order using nodes.
Sample input:
add(2);
add(9);
add(4);
add(7);
add(1);
Sample output: 1 2 4 7 9
Function:
Explanation / Answer
template bool SortedDoublyLinkedList::add(const ItemType &newEntry) { // Add an item to the sorted Doubly Linked list Node *nextNodePtr = new Node(); nextNodePtr->setItem(newEntry); nextNodePtr->setNext(head); head = nextNodePtr; size++; return true; } template SortedDoublyLinkedList::SortedDoublyLinkedList(const SortedDoublyLinkedList &list) { // Implement the copy constructor size = list.size; Node *origChainPtr = list.head; if(origChainPtr == nullptr) head = nullptr; // original list is empty else{ // copy first node head = new Node(); head->setItem(origChainPtr->getItem()); //copy remaining nodes Node *newChainPtr = head; origChainPtr = origChainPtr->getNext(); while(origChainPtr != nullptr) { // Get next item for original chain ItemType nextItem = origChainPtr->getItem(); Node *newNodePtr = new Node(nextItem); newChainPtr->setNext(newNodePtr); newChainPtr = newChainPtr->getNext(); origChainPtr = origChainPtr->getNext(); } newChainPtr->setNext(nullptr); } }