Linked List: A linked list is a collection of structure or class instances, called nodes, that are dynamically allocated with the new operator and connected using pointers. For example:

// Make blueprint for node. Can have any variables inside the structor you want but last variable must be a pointer to udtNode.

typedef struct udtNode

{

int intValue;

udtNode *pudtNextNode;

} udtNodeType;

// Declare some pointers to nodes.

udtNodeType* pudtNode1 = 0;

udtNodeType* pudtNode2 = 0;

udtNodeType* pudtNode3 = 0;

// Create nodes using the new operator.

pudtNode1 = new udtNodeType;

pudtNode2 = new udtNodeType;

pudtNode3 = new udtNodeType;

// Set the value in the nodes

pudtNode1-> intValue = 10;

pudtNode2-> intValue = 20;

pudtNode3-> intValue = 30;

// Link nodes together

pudtNode1->pudtNextNode = pudtNode2;

pudtNode2->pudtNextNode = pudtNode3;

pudtNode3->pudtNextNode = 0; // End of list

// Get a pointer to first node

udtNodeType* pudtCurrentNode = 0;

pudtCurrentNode = pudtNode1;

// Traverse the list and print out the value for each node.

while( pudtCurrentNode != 0 )

{

cout << pudtCurrentNode->intValue; // Print value

pudtCurrentNode = pudtCurrentNode->pudtNextNode; // Move to next node

}

// Clean up/Free memory

delete pudtNode1;

pudtNode1 = 0;

delete pudtNode2;

pudtNode2 = 0;

delete pudtNode3;

pudtNode3 = 0;

// Now an example with loops and an unlimited number of values in the list

(continued on next page)

Step 1

Create a new project and type in the code pictured above and get it working.

Test the code and be sure to let the program terminate normally (dont click the X to close the DOS window).

Step 2

Modify the code from step 1:

Write a function that prompts the user to enter a file name. Return a pointer to a string (dynamically allocated) that contains the name of the file. For example: char* GetFileNameFromUser( )

Write a function that takes a pointer to a file name and returns a pointer to the top of a linked list. In the function read all the numbers from the file and add them to the linked list. Ill give you the file of numbers. You cant edit the numbers file. Use the typedef shown above. Use ifstream (input file stream) for opening and reading from the file. Use the insertion << and extraction >> operators for all input and output.

After the previous step is completed free the memory for the file name string.

Write a function that will take a pointer to the linked list and will print out the numbers in the list.

Write a function that will take a pointer to the linked list and will dispose of all the nodes in the list and set the pointer to 0 (must pass by reference). Print the pointer address from main after the procedure call to prove that it was set to 0.

Test the code and be sure to let the program terminate normally (dont click the X to close the DOS window).

Make sure your code is well commented. It should be sufficient to explain whats happen to you about three weeks ago but not over commented. You want a happy medium.

Slow Delete Fix

If your code executes slowly when deleting the linked list nodes theres fix. Add _NO_DEBUG_HEAP=1 to your environment settings. This can be done for C++ projects through the project properties (Project Properties -> Configuration Properties -> Debugging -> Environment).

(continued on the next page)

Time Code Execution Example

#include

clock_t clkStart = 0;

clock_t clkStop = 0;

// Start

clkStart = clock();

// Do something

// Stop

clkStop = clock();

// Elapsed time

cout << "Elapsed time: " << float( clkStop - clkStart ) / CLOCKS_PER_SEC

<< " seconds " << endl;

system( "pause" );

Extra Credit

Modify the code from step 1:

Write a function that will take a pointer to the linked list and will return the median value in the list.

More Extra Credit

Modify the code from step 1:

Bubble sort a linked list. (Idea from Tony Dolle 2013/09/19).