Lab 3 Linked List

Objectives:

1. Get yourself familiar with the forward linked list creation and operations.

2. Manipulate pointers

3. Create linked node by is-a or has-a

Overview

1. A stock in a portfolio contains a stock symbol (e.g. AAPL), a cost (i.e. purchase price), and the number of shares.

2. Write the stock class.

3. Write a program that creates a forward linked list of at least 20 elements, where each element holds a stock. The stock symbol is a string which you can generate randomly or just do A1, A2, etc. The cost and number of shares are randomly generated between 0 and 99. Print the list. As you may eventually find out that "reading a stock file" into the linked list is actually easier than artificially generate one. You can choose that option instead.

4. Write the function "returnMiddleList" to find the middle element of the linked list in one pass. Print the element and the position of this element (starting at zero) in relation to the head (where the head = 0, the element pointed to by the head = 1, the element pointed to by the previous one = 2, etc).

5. Split the list in half at the middle element to create two entirely separate* linked lists of near equal size (+/- 1) and print the two lists. In other words, write the "split in half" function.

Discussions

1. Can you try both is-a and has-a implementation for node? What do you like or don't like?

2. If you add a length field, finding middle is fairly easy to do. What if you do not have length?

3. Do you do "add" to list when you create a new stock?

4. What if the stock portfolio is on a disk file?

Notes:

How to convert int to string so that we can concatenate A1, A2?

Try the simple test with stringstream:

stringstream s;

s << 123;

cout << s.str() << endl;

Notes (Fall20):

A few students have questionable object designs on this lab. Here is my approach for your reference:

• 1. I will create stock class similar to the complex class in previous labs. (stock.h and stock.cpp)

  2. I will create a stockNode class which inherit from stock class. (in this case, I will just add stockNode definition to stock.h or create a new stockNode.h file. No need for stockNode.cpp -- nothing to write)

  3. In main.cpp, I will have a stockNode *head; to represent the linked list and initialize to null;

  4. In main.cpp, I will write a few functions, the first is to create the list: createStockNodeList(stockNode *)

  5. Write the returnMiddleList(stockNode *);

  6. Write the splitInHalf(stockNode *, stockNode *, stockNode *); original list, first half list, second half list.

Once you have done this, then you'll be ready for Lab 4.