Create a Doubly Linked List Class. Start with the linked list class (named LinkedClass)

dnode.h - the header file for the double linked list class

node1.cpp - contains the single linked list functions - you must save node1.cpp as dnode.cpp and revise the functions in this file to implement a doubly linked

Create a driver program that tests all the functions in the implementation file. Your files should be named: dnode.h, dnode.cpp, driver.cpp

Comment your driver program to show me what function you are testing.

Example: // Testing Constructor Function

// Testing List Search

You must add a traverse function to the linked list toolkit. This function will need to traverse the list both forwards and backwards in order to see that the links are correct.

You must get this class to work correctly (all functions).

LinkedClass

#include

#include

using namespace std;

typedef int value_type;

struct node

{

value_type data;

node * next;

};

void createlist(node* &);

void printlist(node*);

int main()

{

node * first;

createlist(first);

printlist(first);

system("pause");

return 0;

}

void createlist(node* & first)

{

node * current;

first = NULL;

for (int i = 1; i <= 4; i++)

{

current = new node;

cout << "Enter a number : ";

cin >> current->data;

current->next = first;

first = current;

}

}

void printlist(node* first)

{

node * current = first;

for (int i = 1; i <= 4; i++)

{

cout << current->data << endl;

current = current->next;

}

}

-

FILES:

-

node1.cpp

// FILE: node1.cpp // IMPLEMENTS: The functions of the node class and the // linked list toolkit (see node1.h for documentation). // INVARIANT for the node class: // The data of a node is stored in data_field, and the link in link_field.

#include // Provides assert #include // Provides NULL and size_t #include "node1.h"

size_t list_length(const node* head_ptr) { const node *cursor; size_t answer;

answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) ++answer; return answer; } void list_head_insert(node*& head_ptr, const value_type& entry) { head_ptr = new node(entry, head_ptr); }

void list_insert(node* previous_ptr, const value_type& entry) { node *insert_ptr; insert_ptr = new node(entry, previous_ptr->link( )); previous_ptr->set_link(insert_ptr); }

node* list_search(node* head_ptr, const value_type& target) { node *cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) if (target == cursor->data( )) return cursor; return NULL; }

const node* list_search(const node* head_ptr, const value_type& target) { const node *cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) if (target == cursor->data( )) return cursor; return NULL; }

node* list_locate(node* head_ptr, size_t position) { node *cursor; size_t i; assert (0 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != NULL); i++) cursor = cursor->link( ); return cursor; }

const node* list_locate(const node* head_ptr, size_t position) { const node *cursor; size_t i; assert (0 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != NULL); i++) cursor = cursor->link( ); return cursor; }

void list_head_remove(node*& head_ptr) { node *remove_ptr;

remove_ptr = head_ptr; head_ptr = head_ptr->link( ); delete remove_ptr; }

void list_remove(node* previous_ptr) { node *remove_ptr;

remove_ptr = previous_ptr->link( ); previous_ptr->set_link( remove_ptr->link( ) ); delete remove_ptr; }

void list_clear(node*& head_ptr) { while (head_ptr != NULL) list_head_remove(head_ptr); }

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) { head_ptr = NULL; tail_ptr = NULL;

// Handle the case of the empty list. if (source_ptr == NULL) return; // Make the head node for the newly created list, and put data in it. list_head_insert(head_ptr, source_ptr->data( )); tail_ptr = head_ptr; // Copy the rest of the nodes one at a time, adding at the tail of new list. source_ptr = source_ptr->link( ); while (source_ptr != NULL) { list_insert(tail_ptr, source_ptr->data( )); tail_ptr = tail_ptr->link( ); source_ptr = source_ptr->link( ); } }

dnode.h

// FILE: dnode.h // PROVIDES: A class for a node in a doubly linked list, and list manipulation // functions, all within the namespace main_savitch_5 // // TYPEDEF for the dnode class: // Each node of the list contains a piece of data and a pointers to the // previous and next nodes. The type of the data is defined as // dnode::value_type in a typedef statement. The value_type may be any // of the built-in C++ classes (int, char, ...) or a class with a copy // constructor, an assignment operator, and a test for equality (x == y). // // CONSTRUCTOR for the dnode class: // dnode( // const value_type& init_data = 0, // node* init_fore = NULL, // node* init_back = NULL // ) // Postcondition: The node contains the specified data and links. // NOTE: The default value for the init_data is obtained from the default // constructor of the value_type. In the ANSI/ISO standard, this notation // is also allowed for the built-in types, providing a default value of // zero. Both links have a default value of NULL. // // NOTE: // Some of the functions have a return value which is a pointer to a node. // Each of these functions comes in two versions: a non-const version (where // the return value is dnode*) and a const version (where the return value // is const dnode*). // EXAMPLES: // const dnode *c; // c->fore( ) activates the const version of fore // dnode *p; // p->fore( ) activates the non-const version of fore // // MEMBER FUNCTIONS for the dnode class: // void set_data(const value_type& new_data) // Postcondition: The node now contains the specified new data. // // void set_fore(dnode* new_fore) // and // void set_back(dnode* new_back) // Postcondition: The node now contains the specified new link. // // value_type data( ) const // Postcondition: The return value is the data from this dnode. // // const dnode* fore( ) const <----- const version // dnode* fore( ) <----------------- non-const version // const dnode* back( ) const <----- const version // dnode* back( ) <----------------- non-const version // See the note (above) about the const version and non-const versions: // Postcondition: The return value is a link from this dnode.

#ifndef DNODE_H #define DNODE_H #include // Provides size_t and NULL

// TYPEDEF typedef double value_type;

class dnode { public: // CONSTRUCTOR dnode(const value_type& init_data = 0.0, dnode* init_fore = NULL, dnode* init_back = NULL) { data_field = init_data; link_fore = init_fore; link_back = init_back; }

// Member functions to set the data and link fields: void set_data(const value_type& new_data) { data_field = new_data; } void set_fore(dnode* new_fore) { link_fore = new_fore; } void set_back(dnode* new_back) { link_back = new_back; }

// Const member function to retrieve the current data: value_type data( ) const { return data_field; }

// Two slightly different member functions to retrieve each current link: const dnode* fore( ) const { return link_fore; } dnode* fore( ) { return link_fore; } const dnode* back( ) const { return link_back; } dnode* back( ) { return link_back; } private: value_type data_field; dnode *link_fore; dnode *link_back; };

// FUNCTIONS for the linked list toolkit size_t list_length(const dnode* head_ptr); void list_head_insert(dnode*& head_ptr, const value_type& entry); void list_insert(dnode* previous_ptr, const value_type& entry); dnode* list_search(dnode* head_ptr, const value_type& target); const dnode* list_search (const dnode* head_ptr, const value_type& target); dnode* list_locate(dnode* head_ptr, size_t position); const dnode* list_locate(const dnode* head_ptr, size_t position); void list_head_remove(dnode*& head_ptr); void list_remove(dnode* remove_ptr); void list_clear(dnode*& head_ptr); void list_copy(const dnode* source_ptr, dnode*& head_ptr, dnode*& tail_ptr);

#endif