INFR 2820U Assignment 2

Investigating the theoretical complexity and the actual running time of various operations done on a sorted doubly linked list. A sorted doubly linked list is a normal doubly linked list, with the items sorted in the list according to a specific value, priority. (Another way to refer to this form of lists is priority list)

What you need to do for this assignment?

• Write the code for the functions, declared in the DLList.h file. The code should go into the DLList.cpp. Both stub files are provided at the end of this assignment.
• Calculate the theoretical complexity for each function, in terms of the size of the sorted doubly linked list. Do your calculation based on lists of size n.
• Write a test program to :
  • Generate 1000 entries with random priorities and add them to your list.
  • Once you have 1000 item in the list, measure the system running time for each of the following functions: addNode(),removeMaxNode(),removeMinNode(),printList ().
  • Record the running time in the tables provided below. (you might use the code that was provided in assignment 1 to calculate the running time)
• Repeat step 2 for 10,000 and 50,000 random entries added to the list.
• Compare the theoretical and running time of your functions.

Table 1: Time analysis for n= 1000

Function
Name Complexity of the Algorithm (Big Oh) Actual Running Time (ms)
n=1000 n=10000 n=50000 n=1000 n=10000 n=50000
addNode() O(n) O(n) O(n) 4ms 520ms 25965ms
removeMaxNode() O(1) O(1) O(1) 0ms 0ms 0ms
removeMinNode() O(1) O(1) O(1) 0ms 0ms 0ms
printList() O(n) O(n) O(n) 1123ms 10014ms 50695ms

DLList.h

// Sorted Doubly Linked List
// The list is sorted based on priority, with the item that has the highest priority at the front
#ifndef DLLIST_H
#define DLLIST_H
using namespace std;

struct node {
int priority;
string *data;
node *next;
node *prev;
};

class DLList {
public:
DLList();

void addNode(string data, int priority);// add a node to the list.
// put it in the correct place
void removeMaxNode(); //Remove the node with the maximum priority
void removeMinNode(); //Remove the node with the lowest priority
void printList(); // Print the content of the whole list

private:
node *first; // pointer to the first node in the list
node *last; // pointer to the last node in the list
};
#endif

DLList.cpp

#include
#include

#include "DLList.h"
using namespace std;

DLList::DLList() {
first = NULL;
last = NULL;
count = 0;
}

void DLList::addNode(string data, int priority) {
//Add a node with the specified data and priority
}

void DLList::removeMaxNode() {
//Remove the node with the highest priority
}

void DLList::removeMinNode() {
//Remove the node with the lowest priority
}

void DLList::printList() {
//Print all elements in the following format from highest(1) to lowest(99) priority
/*
[|]
[1|homework.doc]
[5|BIT_Degree.psd]
[99|leafs_win.gif]
*/
}