Define a class DoublyLinkedBag that implements the ADT bag by using a doubly linked chain, as shown in Figure 4-9. Use the class of nodes that Exercise 10 defines. Demonstrate your double linked list implementation in a main function. Tips: Unlike the previous assignment (with arrays) we are not using integers as our data - but the ADT bag, which uses templates. It would be best to implement the ADT linked based implementation of bag first. This majority of this code is done for you in the textbook. Then simply modify the LinkedBag code to handle a double linked list.

• Inputs
  • Modification of the Node class: Constructor/descructor for the new node (w/ a next and prev pointers)
  • Modification of the Node class: addition of setPrev and getPrev Functions
• Processing
  • Modification of the LinkedBag class: constructors and destructors
  • Modification of the LinkedBag class: add and remove
• Output
  • main.cpp demonstrates the initialization and destruction of a double linked list.
  • main.cpp demonstrates an addition and removal from the double linked list.

FIGURE 4-9 (a) A linked chain and its (b) shallow copy; (c) deep copy 4 "ab" "cd""ef""gh" i temCount headPtr 4 Copy of i temCount Copy of headPtr Shallow copy 4 ab" "gh" Copy of Copy of Copy of the linked chain i temCount headPtr Deep copy FIGURE 4-9 (a) A linked chain and its (b) shallow copy; (c) deep copy 4 "ab" "cd""ef""gh" i temCount headPtr 4 Copy of i temCount Copy of headPtr Shallow copy 4 ab" "gh" Copy of Copy of Copy of the linked chain i temCount headPtr Deep copy