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]
*/
}
Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.