Lab for CSC1621



An introduction to doubly linked lists


Part I


For the first part of thislab, I would like to you add the backwards printing method of the linked list. We discussed how to do this in class. Copy the code from class, and, when the user wishes to print the linked list, first as the user whether they would like to print it forwards or backwards, and call the appropriate method.
When you have finished this, please show your work to one of the TAs.

Part II: Working with doubly linked lists


In class we learned about the reasons doubly linked lists may be a useful implementation for various problems involving the use of dynamic data structures.
Let's start with the following code, similar to what was developed in class from class: 


/* 
File: node2.h
Purpose: Contains the definitions of the functions that act on a node. For our
        purposed, we can think of a node as representing an item in a hardware store. 
        Each item contains an item name, item price, and number in stock.
*/

#ifndef _NODE2_H
#define _NODE2_H

#include <iostream>
#include <string>

using namespace std;

class node2 {
public:
 node2(string, float, int, node2 *, node2 *);
 node2 * GetNext();
 void SetNext(node2 *);
 node2 * GetPrev();
 void SetPrev(node2 *);
 int GetStock();
 void SetStock(int);
 float GetPrice();
 void SetPrice(float);
 string GetName();
 void SetName(string);

private:
 string name;
 float price;
 int stock;
 node2 * next;
 node2 * prev;
};

#endif


The following code contains the implementation of the class. 


/* 
File: node2.cpp
Purpose: Contains the implementations of the functions that act on a node. For our
        purposed, we can think of a node as representing an item in a hardware store. 
        Each item contains an item name, item price, and number in stock.
*/

#include <iostream>
#include <string>
#include <assert.h>

#include "node2.h"

using namespace std;

node2::node2(string s, float f, int val, node2 * n,node2 * p) {
 name = s;
 price = f;
 stock = val;
 next = n;
 prev = p;
}

node2 * node2::GetNext() {
 return next;
}

void node2::SetNext(node2 * p) {
 next = p;
 return;
}

node2 * node2::GetPrev() {
 return prev;
}

void node2::SetPrev(node2 * p) {
 prev = p;
 return;
}

int node2::GetStock() {
 return stock;
}

void node2::SetStock (int n) {
 stock = n;
 return;
}

float node2::GetPrice() {
 return price;
}

void node2::SetPrice (float f) {
 price = f;
 return;
}

string node2::GetName() {
 return name;
}

void node2::SetName (string s) {
 name = s;
 return;
}


The following is the definition of the doubly linked list class. 


/* 
File: doublelinkedlist.h
Purpose: Contains the definitions of the functions that act on a doubly linked list. 
        The doubly linked list will contain nodes, which are described in the node2.h file. 
        Each item (node) contains an item name, item price, and number in stock, as
        well as a pointer to the next (and previous) nodes in the list (or NULL).
*/

#ifndef _DOUBLELINKEDLIST_H
#define _DOUBLELINKEDLIST_H

#include <iostream>
#include <string>

#include "node2.h"

using namespace std;

class doublelinkedlist {
public:
 doublelinkedlist();
 ~doublelinkedlist();
 void addfront(string, float, int);
 void print();
 void printbackwards();
private:
 node2 * front;
 node2 * last();
};

#endif


The following code contains the implementation of a linked list. 

/* 
File: doublelinkedlist.cpp
Purpose: Contains the implementations of the functions that act on a doubly linked list. 
        The linked list will contain nodes, which are described in the node2.h file. 
        Each item (node) contains an item name, item price, and number in stock, as
        well as a pointer to the next (and previous) nodes in the list (or NULL).
*/

#include <iostream>
#include <string>
#include <assert.h>

#include "node2.h"
#include "doublelinkedlist.h"

using namespace std;


doublelinkedlist::doublelinkedlist() {
 front = NULL;
}

// removes all of the nodes from a linked list
doublelinkedlist::~doublelinkedlist() {
 while (front != NULL) {
  node2 * temp = front->GetNext();
  delete front;
  front = temp;
 }
 return;
}

// adds a node to the front of a doubly linked list
void doublelinkedlist::addfront(string n, float f, int i) {
 front = new node2(n, f, i, front, NULL);
 assert (front);
 if (front -> GetNext() != NULL) 
 	front -> GetNext() -> SetPrev(front);
 return;
}

// prints out the elements in a doubly linked list
void doublelinkedlist::print() {
 node2 * temp = front;
 while (temp != NULL) {
  cout << "Name: " << temp->GetName();
  cout << "   Price: " << temp->GetPrice();
  cout << "   InStock: " << temp->GetStock() << endl;
  temp = temp -> GetNext();
 }
 return;
}

// This private function returns a pointer to the last element in a doubly linked list 
node2 * doublelinkedlist::last() {
 node2 * temp = front;
 if (temp != NULL)  { 
	while (temp -> GetNext() != NULL) {
		temp = temp -> GetNext();
  	}
 }
 return temp;
}

// prints out the elements in a doubly linked list in reverse order
void doublelinkedlist::printbackwards() {
 node2 * temp = last();
 while (temp != NULL) {
  cout << "Name: " << temp->GetName();
  cout << "   Price: " << temp->GetPrice();
  cout << "   InStock: " << temp->GetStock() << endl;
  temp = temp -> GetPrev();
 }
 return;
}


Finally, here is a driver module that tests to make sure that the double linked list works! 



/* 
Name: 
program: link2.cpp
Program to begin practicing with doubly linked lists 

*/

#include<iostream> 
#include<string>

#include "doublelinkedlist.h"

using namespace std; 

int main()
{
    doublelinkedlist ll;

    // these variables are used for adding an element
    string n;
    float amt;
    int qty;
    char direction;

    char choice = ' ';
    
    while (choice != 'q')
      {
        /* the outer while loop continues until the user requests a quit */
        choice = ' '; 
        /* ask the user to select the appropriate action...and ignore any
           other input characters */
        do
          {
            cout << "Enter a to add item, p to print list,";
            cout << "or q to quit" << endl;
            cin >> choice;
          }
        while (choice != 'a' && choice != 'p'
            && choice != 'q');

        /* now perform the action */
        switch (choice)
         {
           case 'a':
                  cout << "Enter item name: ";
                  cin >> n;
                  cout << "Enter item price: ";
                  cin >> amt;
                  cout << "Enter number in stock: ";
                  cin >> qty;
                  ll.addfront(n, amt, qty);
              break;
            case 'p':
			cout << "Print forwards or backwards (f, b)? ";
			cin  >> direction;
			if (direction == 'f')
              		ll.print();
			else
				ll.printbackwards();
              break;
            case 'q':
              cout << "bye" << endl;
              break;
            default:
                 ;
          }  /* end the switch statement */
    }  /* end the outer while loop */
    return 0; 

}

Try out the code to see how it works! Make sure that you understand very well how this code works. Make sure that you are comfortable with how a doubly linked list works, and how it differs from an ordinary linked list.

I would like you to make the following addition to the code:
Add a function add_to_end which adds a new element to the end of the list. While this is quite similar to what you did a week ago, be careful! There are a few subtle differences.

Show the TA or me the finished program.

Optional (but well worth the effort): It is oftentimes useful to be able to keep not only a pointer to the front of the list, but a pointer to the end of the list as well. Let us add a new variable to our doublelinkedlist class: 


		node2 * lastone;
Now, what methods need to be changed to use this new implementation?

Show the TA or me the finished program.