-
Linked Lists
We just started using Linked Lists and quite frankly im lost. I understand the idea behind them and the purpose but im not sure exactly how to go about code-wise doing this. Any assistance to get me going would be greatly appreciated
here are the instructions
Code:
0. define EXACTLY one C++ string variable. As you proceed through the execution of the main program, because your program only has one C++ string variable it forgets the old one as soon as a new one is read.
1. define ONLY two node pointers, say Head and Current, i.e., two variables that can point to a Node. You cannot create more than two.
2. Read a string from the keyboard.
3. Allocate a new node and store the string just read in the data portion of the node, and make the link null, i.e., call the Node constructor to do this. You will need to remember this node created by setting Head to this node.
4. Read a second string from the keyboard.
5. Using if-stmts decide if this second string comes before the first string read, is the same as the first string read, or goes after the first string read.
6. If the two strings are the same, then skip to step 7.
6a Allocate a new node, store the second string read in the data portion of the node
6b Place the new node in the correct position, i.e., before or after the existing node.
7. Read another string from the keyboard.
8. Decide where this third string fits within the previous two read (before, same as, or after).
9. If the new string is the same, then skip to step 10.
9a Allocate a new node, store the third string in the data portion of the node
9b Place the new node in the correct position: at beginning, in middle, or at end.
10. At this time, you should have read three strings, appropriately created nodes, and inserted into a linked list.
10a. Now traverse your list while printing the data, i.e., as you come to a node, print the data found in that node. Remember, there may be one, two, or three nodes in the list. So you cannot just blindly print three things here. Example. If the input were a, b, b, then the output would be a b
Here is my main program
Code:
#include "Node.h"
#include <iostream>
using namespace std;
int main()
{
string userInput = "";
Node *Head;
Node *Current;
cin >> userInput;
Head = new Node;
Node( userInput, ???);
return 0;
}
So somehow I need to create a new node and store the data in that node. Then read in another, compare them and then put them in appropiate positions, and finally do the last one.
The input is : a, b, c
here is the header file (provided by the teacher)
Code:
#include <iostream>
using namespace std;
// The node class will represent each node in the linked list
class Node
{
public:
string Data; // the data portion of a node
Node* Link; // the link portion of a node
// default constructor
Node(string strData="", Node* ptrNode=NULL)
{
Data = strData;
Link = ptrNode;
}
// copy constructor
Node(Node* ptrNode)
{
Data = ptrNode->Data;
Link = ptrNode->Link;
}
};
-
That's what the constructor is for:
Code:
Head = new Node(input);