Singly linked list of structs

Pages: 12
closed account (D80DSL3A)
Also, you will have other errors coming even after making the changes recommended by LB.

1) You need to add #include<string> before line 2.
2) Either provide a definition for the remove() function or just comment out the prototype on line 21.

The easiest way to remove a Node is from the front of the list:
1
2
3
4
5
6
7
8
9
10
// a workable definition for remove
void List::remove()
{
    if( head != NULL)
    {
    Node* temp = head;// point to 1st Node in list
    head = head->next;// point head at 2nd node in the list
    delete temp;// free the memory for this Node
    }
}

With insert() and remove() defined this way your List will function as a stack, ie. first-in last-out (or FILO).
EDIT: Code correction at line 8, and the sentence above.
Last edited on
Thank you guys so much. SSL have always been difficult for me. But you guys helped a lot.
Alright. I think I've learned a lot. But one thing I noticed is that with the code that you guys showed me, dosnt the list insert an item in front of older items(prepend) in this case? Because I would actually like to append each insertion. I think this requires an unchanging "root" Node but I am confused on the syntax. Does my request make any sense?
closed account (D80DSL3A)
Yes it does make sense. I wrote the insert() function that way because it's easier to write the code for that, so it seemed best for starting out.

To add a Node at the end of the list you will need to either iterate to the end of the list from the beginning (to reach the last Node), or add a Node* tail; member so you can go straight to the last Node in the list.

Taking the 1st approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void List::insert( datatype dat )
{
    if( head == NULL )// list is empty.Establish the head Node
    {
       head = new Node;
       head->data = dat;
       head->next = NULL;
    }
    else// iterate to the end of the list (but stop at the last Node)
    {
        Node* temp = head;
        while( temp->next != NULL ) temp = temp->next;
        // now temp points to the last Node. Add a new Node after it.
        temp->next = new Node;
        temp = temp->next;// now pointing to the new Node at the end.
        temp->data = dat;
        temp->next = NULL;// marking end of List
    }
}


EDIT: This is just a start on a properly written class. As is, your List class is leaking memory because the memory for the Nodes isn't released when the List goes out of scope. That's the job of the destructor. However, as soon as you write the destructor then common operations like equating two lists ListA = ListB; or copying a List on construction List ListB(ListA); will result in crashes.
You will need to write a destructor, copy constructor and overload operator= to make it work right. Google "rule of three".
Last edited on
Thank you for all the help. I am learning a lot. I am now trying to make Class method to print out the list but I am finding that difficult because I keep getting an error with the "<<" operator when I write cout << temp->data <<endl;. Why is that?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void List::print(datatype dat )
{
    if( head == NULL )
    {
cout <<"list is empty " <<endl;
    }
    else
    {
        Node* temp = head;
        while( temp->next != NULL ){
			
			cout << temp->data <<endl;

		}
        
    }
}


Is it because I have a custom datatype? And if so, how do I tell the computer how to output the information from the list?
Last edited on
datatype needa a friend function for operator<< with std::ostream. Look up how to output custom classes with friend function and ostream. It's not an issue with your list class.
Last edited on
I've been looking and I keep getting confused. What I have figured is that I need something like this:

friend std::ostream& operator<< (std::ostream& stream, const datatype& datatype);

But I am not sure what is happening or if I am close. I am looking at friendship and inheritance documentation(which all the documentation on this site is amazing) and I am still confused with how to use it in this case.
That looks correct; here is an example:
1
2
3
4
5
6
7
8
9
10
struct MyClass
{
    int x, y;
    //...
    friend std::ostream &operator<<(std::ostream &stream, const MyClass &mc)
    {
        stream << "MyClass: x=" << mc.x << ", y=" << mc.y << std::endl;
        return stream;
    }
};
Last edited on
Wait, seriously? I was just guessing lol. I'm a little confused by you making a struct called "myClass" by the way.

But even if the code was right on my guess, I still dont understand the whole friend/ostream thing.
Could you explain what exactly is going on here?
oudavid1 wrote:
I'm a little confused by you making a struct called "myClass" by the way.
In C++, there is no difference between the "struct" keyword and the "class" keyword except that structs default to public access level (as if there is an invisible public: at the start) and classes default to private access level (as if there is an invisible private: at the start).
oudavid1 wrote:
I still dont understand the whole friend/ostream thing.
Could you explain what exactly is going on here?
A friend function is a function which has access to the private and protected members of a class. operator<< is the function used when you write std::cout << "Hello, world!";, and you are overloading it with a version that takes an instance of your class.
Ah I see. Thank you. I think the syntax is just confusing to me.

friend std::ostream &operator<<(std::ostream &stream, const MyClass &mc)

I just want to understand what each command is doing in this line.
1
2
3
4
5
6
7
8
9
10
11
friend std::ostream &operator<<(std::ostream &stream, const MyClass &mc)
//Same as above, but split onto multiple lines:
friend //this function is not part of the class, but it has access to class private data
std::ostream & //this function returns a reference to a std::ostream
operator<< //this function is an overload of the << operator
( //parameter list opening paren
    std::ostream & //type of first parameter (the thing on the left side of <<)
        stream, //name of first parameter
    const MyClass & //type of second parameter (the thing on the right side of <<)
        mc //name of second parameter
) //parameter list closing paren 
You can define the function in the same place as the friend declaration, like in my example, or you can define it outside of the class. Here's both ways:
1
2
3
4
5
6
7
8
9
10
struct MyClass
{
    int x, y;
    //...
    friend std::ostream &operator<<(std::ostream &stream, const MyClass &mc) //inline definition
    {
        stream << "MyClass: x=" << mc.x << ", y=" << mc.y << std::endl;
        return stream;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
struct MyClass
{
    int x, y;
    //...
    friend std::ostream &operator<<(std::ostream &stream, const MyClass &mc); //delcaration
};
//...
std::ostream &operator<<(std::ostream &stream, const MyClass &mc) //notice: no reference to "MyClass" except for parameter
{
    stream << "MyClass: x=" << mc.x << ", y=" << mc.y << std::endl;
    return stream;
}
Last edited on
EDIT: Ok, I figured it out. Here is my code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
struct datatype
	{
		friend ostream &operator<< (ostream &stream, const datatype &dt){
			stream <<dt.name << " " << dt.id <<" "<< dt.amt <<endl;
			return stream;
		}
		string name;
		int id;
		float amt;
        datatype(string Name, int Id, float Amt): name(Name), id(Id), amt(Amt) {}
        datatype(void): name(""), id(0), amt(0.0f) {}
		
	};
struct Node
{
		
	datatype data;
	Node *next;
};

class List 
{
	Node *head;
public:
			
			void insert(datatype dat);
			void remove();
			void printEvery20();
			List(){head = NULL;}
};

void List::insert( datatype dat )
{
    if( head == NULL )
    {
       head = new Node;
       head->data = dat;
       head->next = NULL;
	
    }
    else
    {
        Node* temp = head;
        while( temp->next != NULL ) temp = temp->next;
        temp->next = new Node;
        temp = temp->next;
        temp->data = dat;
        temp->next = NULL;
		 
    }
}
void List::printEvery20()
{
    if( head == NULL )
    {
cout <<"list is empty " <<endl;
    }
    else
    {
        Node* temp = head;
        while( temp->next != NULL ){
		cout << temp->data;
		temp = temp->next;
		r++;
		}
        
    }
}


So in the struct Datatype, the friend function of ostream actually tells the line in void List::printEvery20 --- "cout <<temp->data;" how to print out the data? It tells the data part of the node how to be outputted? Right?
Last edited on
closed account (D80DSL3A)
Very good. You could also overload << for the List class to replace the printEvery20() function. Keep the << overload for the datatype structure, it can be used within the definition of << for the List class. The compiler can keep the definitions straight as it's determined by what object type appears as the right operand (object on the right side of << ).

It tells the data part of the node how to be outputted? Right?
That's correct.

About printEvery20 function: Line 61 should be while( temp != NULL );. As it is the last Node won't print out. In the insert() function we needed to stop early.
Also, since cout is used explicitly the function can only print to the console. Using ostream allows it to write to any output stream given, such as to a file.
What's the r++; line for?
On temp != NULL While loop.....I could have used you an hour ago lol. I finally figured out why my list was doing that. Thanks again.

This whole overloading thing still confuses me.

The r++ was just some housekeeping that I hadnt taken out yet.

The first part of your post you say I could eliminate the printevery...() function, I can sort of see what you're saying. But I'm not quite sure how. You dont need to explain it but if you dont mind I would appreciate it. Your explanations have been wonderful.
closed account (D80DSL3A)
You're welcome. LB has been the one giving detailed explanations. I've been lazy, mostly posting code.

Operator overloading is a bit confusing at first.
Add friend ostream &operator<< (ostream &stream, const List &L); to the List class (replacing line 28) then define it (replacing lines 52-68) as:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ostream &operator<< (ostream &stream, const List &L)
{
if( head == NULL )
    {
        stream <<"list is empty" << endl;
    }
    else
    {
        Node* temp = head;
        while( temp != NULL ){
		stream << temp->data;// here the << overload for datatype is used
		temp = temp->next;
		}        
    }
    return stream;
}

EDIT: This enables you to write the entire list to the console with
cout << ListA; according to the format you've built into the definition for <<.
Also, this doesn't have to replace the printEvery20() function. You could keep both if you want to.
Last edited on
I really appreciate all of this. I've learned a ton and will be coming back to thread to relearn if needed.
oudavid1 wrote:
the friend function of ostream
It's a friend function of your datatype struct; the return type just happens to be ostream.
Topic archived. No new replies allowed.
Pages: 12