1. [30 points] Doubly-Linked List Implementation Given the linked list implementation (node class), your task is to implement a doublylinked list. A Doubly-Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly-linked list. The dnode class (in the LinkedList toolkit) has an implementation of doublylinked list. What you need to do is implementing the following three functions:

an insert function to insert an item into a doubly-linked list. The function has three parameters: the pointer to head node, previous node and a value (the data of the new node).

an erase one function to remove a node from a doubly-linked list. The function has two parameters: the pointer to head node and a pointer to the node we want to delete. If there is only one node in the linked list, then you must deallocate space and set head to NULL. Recall that in singly-linked lists, to delete a node, pointer to the previous node is needed. However, in doubly-linked list we can get the previous node using previous pointer.

a reverse function that reverses the order of the nodes similar to the first question. Again, you are not allowed to make a copy of the list.

2. [50 points] Linked List Implementation of Bag Use the linked list implementation ( node class) to implement Bag class. Your implementation should includes the following functions:

constructor(s)

a destructor

an insert function to insert an item into a bag.

an erase one function to remove an item from a bag (if more than one instance of that item exist in a bag, the function erases the first one)

an erase function to remove all instance of an item from a bag (the function returns the number of instances which are removed) The header file bag.h can be found in the LinkedList toolkit.

CLASS DNODE:

class dnode{ public: typedef double value_type; node(const value_type& d=value_type(), node* l=NULL, node* p=NULL){ data_field = d; link_field = l; prev_field = p; } void set_data(const value_type& d){ data_field = d;} void set_link(node* l) {link_field = l;} void set_prev(node* p) (prev_field = p;); value_type data() const {return data_field;}

node* link() {return link_field;}; const node* link() const {return link_field;};

node* prev() {return prev_field;}; const node* prev() const {return prev_field;}; private: value_type data_field; node* link_field; node* prev_field; };

HEADER BAG.H

#ifndef BAG_H #define BAG_H #include node.h

using namespace std;

class bag{ public: typedef std::size_t size_type; typedef node::value_type value_type;

bag();

bag(const bag& src);

~bag();

void insert(const value_type& entry); bool erase_one(const value_type& target); size_type erase(const value_type& target);

size_type size() const {return num_nodes;}; size_type count(const value_type&target) const;

private: node* head; size_type num_nodes;

#endif