Linked List - Overload ++ operator

[cbaechle]

So we were in class today and my professor said that, while iterating through a linked list you can use the ++ operator to get the next node. Here's an example linked list...

#include <iostream>

using namespace std;

class Node {
public:
	int data;
	Node * next;
};

class List {
public:
	List();
	void append(int i);
	void print();
	void test();

private:
	Node* front;
	Node* back;
};

List::List() {
	front = back = NULL;
}

void List::append(int i) {
	
	Node *n = new Node;
	n->data = i;
	n->next = NULL;

	if (front == NULL) {
		front = back = n;
	} else {
		back->next = n;
		back = n;
	}
}

void List::print() {
	cout << "printing" << endl;
	for (Node *n = front; n != NULL; n = n->next) {
		cout << n->data << endl;
	}
}

int main() {
	List l;
	l.append(1);
	l.append(2);
	l.append(3);
	l.print();
	return 0;
}

The line of interest is in print().

for (Node *n = front; n != NULL; n = n->next)

He claimed you can just do n++ instead of n = n->next. I disagree. While it may work sometimes if the nodes grab memory quick enough they are grabbing contiguous memory addresses, it would fail if the addresses were not contiguous.

This lead me to wanting to over load the ++ operator to achieve the behavior he described.

I ran into some problems... n isn't a Node, it's a pointer to a Node. So we'd have to overload the operator with the pointer as an argument instead of a Node. I couldn't really see a way to do this as a member.

The other issue is, we'd have to reassign the address of this. We'd be saying this = this->next. I'm pretty sure you can't do that because this isn't an lvalue.

So does anyone have an elegant way of overloading the ++ operator so the following is valid?

for (Node *n = front; n != NULL; n++)

[Tom Gunn]

He claimed you can just do n++ instead of n = n->next. I disagree.

With your List class that's true. But C++ allows you to overload operators to do different things. You can overload the ++ operator to do n = n->next. That's what the list<T>::iterator does:

#include <iostream>
#include <list>

using namespace std;

int main()
{
    list<int> values;

    for (int x = 0; x < 10; ++x) values.push_back(x);

    for (list<int>::iterator x = values.begin();
         x != values.end();
         ++x)
    {
        cout << *x << '\n';
    }
}

list<T>::iterator is a class that overloads the ++ operator and other things to match certain rules about how the iterator type should work. In a way list<T>::iterator corresponds to your Node class.

[edit]
This is a quick example to show what I mean. It uses a wrapper around Node to implement an iterator. It's not fancy or 100%, but it shows the concept a little better than the first example.

#include <iostream>
#include <cstddef>

using namespace std;

class Node {
public:
	int data;
	Node * next;
};

class Iterator {
    friend class List;
    Node *_node;
public:
    Iterator(Node *node=NULL): _node(node) {}
    int& operator*() { return _node->data; }
    Iterator& operator++()
    {
        _node = _node->next;
        return *this;
    }
    friend bool operator==(const Iterator& lhs, const Iterator& rhs)
    {
        return lhs._node == rhs._node;
    }

    friend bool operator!=(const Iterator& lhs, const Iterator& rhs)
    {
        return !(lhs._node == rhs._node);
    }
};

class List {
public:
	List();
	void append(int i);
	void print();
	void test();

private:
    Iterator front;
    Iterator back;
};

List::List() {
	front = back = NULL;
}

void List::append(int i) {
	
	Node *n = new Node;
	n->data = i;
	n->next = NULL;

	if (front == Iterator()) {
        front._node = back._node = n;
	} else {
        back._node->next = n;
        back._node = n;
	}
}

void List::print() {
	cout << "printing" << endl;
	for (Iterator n = front; n != Iterator(); ++n) {
		cout << *n << endl;
	}
}

int main() {
	List l;
	l.append(1);
	l.append(2);
	l.append(3);
	l.print();
	return 0;
}

[csurfer]

Well this is what I got to say,

@cbaechle:
Your thought flow is in the right direction. Looking at the code and assuming you are still at the initial stages(that you haven't yet come across complex stuff) ya n=n->link becomes more or less equal to n++ when n is allocated memory statically that is through the array as ++ would simply mean move to the next block which can be assumed to be correct even though it can cause many problems.But ya as in the code if n is allocated memory randomly then there is now way to say n=n->link => n++.

About overloading ++ here is something you can start with (this is just a starter) :) :

const ClassType& ClassType::operator++()
 {
     myValue=myValue->link;
     return *this;
 }

@Tom Gunn :
I really don't think the instructor thought of all the things you mentioned in basic classes on overloading.

[cbaechle]

@csurfer
Thanks. I wanted to make sure my reasoning wasn't flawed.

[Tom Gunn]

I really don't think the instructor thought of all the things you mentioned in basic classes on overloading.

I guess I wasn't any help then. :(

[csurfer]

I guess I wasn't any help then. :(

OP learnt a new concept,thats good,but he/she learnt it too early thats the problem ;)

[cbaechle]

I know it could be solved with an iterator design pattern and that's how it's done in the real world and with STL. I guess I was more curious if the problem could be solved with the parameters given and was more of an academic question than a real world one. Thanks for your input though. I did read and compile all your code so it wasn't in vein.

[cbaechle]

@csurfer
Where does myvalue come from? I know how to overload the increment operator in general, but the problems I run into are that I need to assign the address of the current object (this) and it's being passed a pointer not a node. I guess I'm missing something.

[csurfer]

>Where does myvalue come from?
Well that was the reason I said its a starter.myValue is a variable in the class you would define which is defined in such a way that it points to next class object,in kind of linked list fashion.Some what similar to your "next" variable. Here's another thread which might help.