Generating a Large Amount of Strings in a Linked List

[jheard901]

Inputting a large number for amount of strings to generate() is not as simple as I thought it would be. I need to be able to generate strings so that it takes on average 5-10 seconds to do so. However, I can not enter more than 3000 as an argument for the program to continue! If I enter 3000 it finishes generating the strings in 0.0078 seconds (or 78 milliseconds)!!! If I enter anything over that limit the program will continue to run, but not accept any user input imitating a state as if it is actually doing some work. What needs to be changed in my code?

the constructor I use:

SortedLinkedList::SortedLinkedList(const int& max)
{
	head = NULL;
	tail = NULL;
	currentPos = NULL; //could set this to head
	length = 0;
	maxList = max;
}

the driver used:

//global variables
int userChoice;
int strings;
string userInput;
int MAX_STRINGS = 10000;

//beginning of test driver
int main() {
	///////////////////////
	//Test Driver Program//
	///////////////////////
	cout << "Test Driver\n" << endl;
	SortedLinkedList list1(MAX_STRINGS); //creates a list

else if(userChoice == 9) {
			cout << "How many strings to create: ";
			cin >> strings;
			list1.Generate(strings);
		}

the class private members (no idea if this could be an issue):

private:
	typedef struct ptrNode //container for a node
	{
		string name; //name of node
		ptrNode* next; //points to next node
		ptrNode* prev; //points to previous node
	};
	ptrNode* head; //beginning of a list; same thing as listData in book
	ptrNode* tail; //end of a list
	ptrNode* currentPos; //current position in list
	int length;
	int maxList;

the class definition:

void SortedLinkedList::Generate(const int numValue)
{
	//variables
	int i;
	int j;
	int ranchar;
	//Timer started
	double start,end;
	start = GetTickCount();
	string *astring;
	astring = new string[numValue]; //creates an array of strings equal to numValue
	for(i = 0; i < numValue; i++) {
		for(j = 0; j < 5; j++) { //creates strings of random characters
			ranchar = rand()%26; //code from iLab doc
			astring[i] += ('a'+ranchar); //astring is the actual generated string
		}
		length++; 
		if(Empty()) { //basically a repeat of the PutItem() function
		ptrNode* temp = new ptrNode;
		head = temp;
		tail = temp;
		temp->prev = NULL;
		temp->next = NULL;
		temp->name = astring[i];
		}
		else { //decides where item should be inserted at into the list
			currentPos = head; //start from head
			while(astring[i] > currentPos->name && currentPos->next != tail->next) {
				currentPos = currentPos->next;
				//compares user value with currentPos name
				//continues until value is not greater than currentPos->name, or reaching the end of list
				//each iteration sets currentPos to the next node in list
			}
			if(currentPos == head && astring[i] < head->name) { //places value before head
				ptrNode* temp = new ptrNode;
				temp->name = astring[i]; //defines name of node as user's value
				temp->prev = NULL; //points back to head
				temp->next = currentPos; //points new node to head
				head->prev = temp; //points head to new node
				head = temp; //sets node as head of list
				//cout << "Inserted " << astring[i] << " before " << currentPos->name << " at the beginning" << endl; //feedback
			}
			else {
				if(currentPos == tail && astring[i] > tail->name) { //places value after tail
					ptrNode* temp = new ptrNode;
					temp->name = astring[i];
					temp->prev = tail; //prev ptr of new node points to tail
					temp->next = NULL; //new node points to nothing
					currentPos->next = temp; //tail points to new node
					tail = temp; //new node becomes tail
					//cout << "Added " << astring[i] << " at the end" << endl; //feedback
				}
				else { //places value before or after currentPos
					if(currentPos->name > astring[i]) { //places before
						ptrNode* temp = new ptrNode;
						temp->name = astring[i];
						temp->prev = currentPos->prev;
						temp->next = currentPos;
						(currentPos->prev)->next = temp;
						currentPos->prev = temp;
						//cout << "Inserted " << astring[i] << " before " << currentPos->name << endl; //feedback
					}
					else { //places after
						ptrNode* temp = new ptrNode;
						temp->name = astring[i];
						temp->prev = currentPos;
						temp->next = currentPos->prev;
						(currentPos->next)->prev = temp;
						currentPos->next = temp;
						//cout << "Inserted " << astring[i] << " after " << currentPos->name << endl; //feedback
					}
				}
			}
		}
		
	}
	//Timer ends
	end = GetTickCount();
	double timetaken = (end - start);
	cout << "This took " << timetaken << " milliseconds too complete\n";
}

No idea, how to fix this problem.

[jheard901]

When I step through the code, I notice this problem always occurs when I reach astring[i] for the 3997'th time. Any reason why it would do this?

[jheard901]

I found some kind of work around to my problem... making special cases (if statements) that execute in the case that astring[i]'s value is = to currentPos->name. Still, I get no variation in the time it takes to do operations insert(), delete(), and checkExists(). Should the time it takes for these operations not change regardless of the size of the list?