Overloading << and [] operators for Linked List class.

[packetpirate]

I'm trying to overload the [] operator for my linked list class so that you can access an index with it, rather than having to use the get() function in the class. I'm pretty sure I overloaded this right:

template< typename T >
T LinkedList<T>::operator[](int pos) {
    node<T> *current = new node<T>;
    int i = 0;

    for(current = first;current != NULL;current = current->link) {
        if(i == pos) {
            return current->data;
        }
        i++;
    }
}

However, I know I'll also have to overload other operators, such as <<, if I want to, for example, use cout to output the data returned by that index. How can I overload the << operator and = operator this way?

[Athar]

This is an error and causes a memory leak:
node<T> *current = new node<T>;

However, I know I'll also have to overload other operators, such as <<, if I want to, for example, use cout to output the data returned by that index. How can I overload the << operator and = operator this way?

No, why do you think that? operator[] returns an object of type T, so as long as these operators exist for that type, everything's fine.

[packetpirate]

Funny, because Visual Studio seems to think otherwise.

cout << myList[3] << endl;

Error:

Error 1 error C2679: binary '<<' : no operator found which takes a right-hand operand of type 'linklist::LinkedList<T>' (or there is no acceptable conversion) c:\users\packetpirate\documents\visual studio 10\projects\linkedlist_header\linkedlist_header\main.cpp 39 1 LinkedList_Header
2 IntelliSense: no operator "<<" matches these operands c:\users\packetpirate\documents\visual studio 10\projects\linkedlist_header\linkedlist_header\main.cpp 39 7 LinkedList_Header

Also, how does:

node<T> *current = new node<T>;

...cause a memory leak? It works fine...

[Disch]

Error 1 error C2679: binary '<<' : no operator found which takes a right-hand operand of type 'linklist::LinkedList<T>' (or there is no acceptable conversion)

What is myList?

Either it's a list of a list, or your [] operator is returning a list instead of an individual element.

Also, how does:

node<T> *current = new node<T>;

...cause a memory leak? It works fine...

If you create something with new, you have to delete it. Otherwise whatever you created never goes away. So every time you call the [] operator, it's newing a node, which sucks up memory that never gets release. So with every call, your program uses more and more memory.

Hence, memory leak.

You don't even need to use new there. What's the point of creating a new node in that operator? All you do is point to existing nodes. Just change that line to this:

node<T>* current;  // no need for new 

[helios]

The hell? There's no way that's happening. The offset operator has a higher precedence than the shift operators. Either you're not showing us all the relevant code, or that errors points to a different line.

It works fine...

"Working" and "working right now" are two very different conditions. Your code works until the operator is used enough times. After spending an indeterminate amount of time allocating memory and never freeing it, something very bad will happen to the program.
You don't need to allocate an object at that point, evidenced by the fact that you almost immediately overwrite the pointer with a pointer to the head node. Just initialize current to zero.

[packetpirate]

I didn't want to post the full program because it's rather large. Here's the header file:

/**
* This header file was designed to make creation and modification of linked lists easier.
* Author - packetpirate
* Last Update - 05/18/2011  11:19 PM
**/

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
using std::cout;
using std::endl;

// Begin linklist namespace.
namespace linklist
{
	// Begin node structure.
	template< typename T >
	struct node {
		T data; // Contains data of specified type.
		node<T> *link; // Contains link to next node. NULL if this node is last in the list.
	};
	// End node structure.

	// Begin LinkedList class declaration.
	template< typename T >
	class LinkedList {
		public:
			LinkedList(); // Creates a new blank list.
			LinkedList(node<T> *start); // Creates a new list with a specified first node.
			~LinkedList();

			// Delete functions.
			void destroy();
			void remove(int pos);

			// Functions for appending the list.
			void add(node<T> *next); // Adds a node to the list.
			void add(T nextData); // Adds a new node to the list.

			// Get and Set functions for the list.
			T get(int pos);
			void set(int pos, T newData);

			// Size-based functions.
			int length();
			bool isEmpty();

			// Position-based functions.
			T begin(); // Returns the data of the first node in the list.
			T end(); // Returns the data of the last node in the list.
			T operator[](int pos);

			// Sort function/s.
			void sort(bool asc);
			void swap(node<T> *i, node<T> *j);

			// Print functions.
			void printList();
			void printElem(int pos);
		private:
			node<T> *first; // The first node in the list.
			node<T> *last; // The last node in the list.
			int size; // Size of the list.
	};
	// End LinkedList class declaration.

	// Begin LinkedList class definitions.
	// Begin Constructors & Destructors
	template< typename T >
	LinkedList<T>::LinkedList() {
		first = NULL;
		last = NULL;
		size = 0;
	}
	template< typename T >
	LinkedList<T>::LinkedList(node<T> *start) {
		if(start->link != NULL) {
			first = start;
			node<T> *current = start;
			int count = 0;

			for(current = start;current != NULL;current = current->link) {
				count++;
				if(current->link == NULL) {
					last = current;
					size = count;
				}
			}
		} else {
			first = start;
			last = start;
			size = 1;
		}
	}
	template< typename T >
	LinkedList<T>::~LinkedList() {
		destroy();
	}
	// End Constructors & Destructors

	// Begin delete functions.
	template< typename T >
	void LinkedList<T>::destroy() {
		node<T> *current = new node<T>;

		while(first != NULL) {
			current = first;
			first = first->link;
			delete current;
		}
		
		last = NULL;

		size = 0;
	}
	template< typename T >
	void LinkedList<T>::remove(int pos) {
		if(pos > (size - 1)) {
			cout << "That position is out of bounds.";
		} else {
			node<T> *current = new node<T>;
			int i = 0;

			for(current = first;current != NULL;current = current->link) {
				if(i == (pos - 1)) {
					node<T> *temp = current->link;
					current->link = current->link->link;
					delete temp;
					size--;
					break;
				}
				i++;
			}
		}
	}
	// End delete functions.

	// Begin list modifying functions.
	template< typename T >
	void LinkedList<T>::add(node<T> *next) {
		if(first == NULL) {
			first = next;
			last = next;
			last->link = NULL;
			size++;
		} else {
			last->link = next;
			last = next;
			last->link = NULL;
			size++;
		}
	}
	template< typename T >
	void LinkedList<T>::add(T nextData) {
		node<T> *next = new node<T>;
		next->data = nextData;
		next->link = NULL;
		
		if(first == NULL) {
			first = next;
			last = next;
			last->link = NULL;
			size++;
		} else {
			last->link = next;
			last = next;
			last->link = NULL;
			size++;
		}
	}
	// End list modifying functions.

	// Begin get/set functions.
	template< typename T >
	T LinkedList<T>::get(int pos) {
		if(pos > (size - 1)) {
			cout << "That position is out of bounds." << endl;
		} else {
			int i = 0;
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				if(i == pos) {
					return current->data;
				}
				i++;
			}
		}
		return 0;
	}
	template< typename T >
	void LinkedList<T>::set(int pos, T newData) {
		if(pos > (size - 1)) {
			cout << "That position is out of bounds." << endl;
		} else {
			int i = 0;
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				if(i == pos) {
					current->data = newData;
				}
				i++;
			}
		}
	}
	// End get/set functions.

	// Begin size-based functions.
	template< typename T >
	int LinkedList<T>::length() {
		return size;
	}
	template< typename T >
	bool LinkedList<T>::isEmpty() {
		return (first == NULL);
	}
	// End size-based functions.

	// Begin position-based functions.
	template< typename T >
	T LinkedList<T>::begin() {
		if(!isEmpty()) {
			return first->data;
		} else {
			return NULL;
		}
	}
	template< typename T >
	T LinkedList<T>::end() {
		if(!isEmpty()) {
			return last->data;
		} else {
			return NULL;
		}
	}
	template< typename T >
	T LinkedList<T>::operator[](int pos) {
		node<T> *current = new node<T>;
		int i = 0;

		for(current = first;current != NULL;current = current->link) {
			if(i == pos) {
				return current->data;
			}
			i++;
		}
	}
	// End position-based functions.

	// Begin sort function/s.
	template< typename T >
	void LinkedList<T>::sort(bool asc) {
		if(!isEmpty()) {
			node<T> *i;
			node<T> *j;

			for(i = first;i != NULL;i = i->link) {
				for(j = i->link;j != NULL;j = j->link) {
					if(asc) {
						if(j->data < i->data) {
							swap(i, j);
						}
					} else {
						if(j->data > i->data) {
							swap(i,j);
						}
					}
				}
			}
		}
	}
	template< typename T >
	void LinkedList<T>::swap(node<T> *i, node<T> *j) {
		T tempData = i->data;
		i->data = j->data;
		j->data = tempData;
	}
	// End sort function/s.

	// Begin print functions.
	template< typename T >
	void LinkedList<T>::printList() {
		if(!isEmpty()) {
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				cout << current->data << " ";
			}
			cout << endl;
		} else {
			cout << "The list is empty." << endl;
		}
	}
	template< typename T >
	void LinkedList<T>::printElem(int pos) {
		if(pos > (size - 1)) {
			cout << "That position is out of bounds." << endl;
		} else {
			int i = 0;
			node<T> *current;

			for(current = first;current != NULL;current = current->link) {
				if(i == pos) {
					cout << current->data << endl;
					break;
				}
				i++;
			}
		}
	}
	// End print functions.
	// End LinkedList class definitions.
}
// End linklist namespace.

#endif 

And here's the main.cpp:

/**
* This file is to test the LinkedList header file.
* Author - packetpirate
* Last Update - 05/18/2011  11:19 PM
**/

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <ctime>
using std::rand;
using std::srand;
#include "LinkedList.h"
using linklist::LinkedList;
using linklist::node;

int main(int argc, char** argv) {
	srand((unsigned)time(0));

	LinkedList<int> *myList = new LinkedList<int>();
	
	int num = 0;

	for(int i = 0;i < 10;i++) {
		num = rand()%10 + 1;
		myList->add(num);
	}
	myList->printList();

	myList->sort(true);
	myList->printList();
	cout << "List Length: " << myList->length() << endl;

	myList->remove(4);
	myList->printList();
	cout << "List Length: " << myList->length() << endl;

	cout << myList[3] << endl;

	myList->destroy();
	myList->printList();
	cout << "List Length: " << myList->length() << endl;

	cin.sync();
	cout << "Press any key to continue...";
	cin.get();
	return 0;
}

Everything except the line:

cout << myList[3] << endl;

...works.

[D80DSL3A]

That's because myList is a pointer to a list. Try this:
cout << (*myList)[3] << endl;
This dereferences the pointer before applying the operator.

Also, you should delete the memory for myList which you allocated with new. Add
delete myList; before line 48 (program exit).

[Disch]

That's because myList isn't a list, it's a pointer to a list.

[] is not calling your [] operator, it's dereferencing your pointer.

You need to do this:

cout << (*myList)[3] << endl;

Or you could change myList so it's not a pointer.

Also you still have the memory leak in your [] operator.

[helios]

Here's the problem: myList is a pointer, not an object. When you do myList[x], you're not calling the operator[] overload and passing it myList as this and x as the index; you're trying to access the LinkedList<int> object that's x elements past the start of the array myList points to. In other words, *(myList+x). This evaluates to a LinkedList<int>.

[packetpirate]

EDIT: Stupid question... those parentheses should only be there if I'm calling a specific constructor... not the default one.

[packetpirate]

Just one more question... if I wanted to still make it a pointer to an object, how could I called the [] operator on the object without the parentheses and * sign? Like: myList[3]?

[m4ster r0shi]

I think the only other option is myList->operator[](3) or something like this.

[Disch]

+1 @ master roshi.

Also I don't know what parenthesis you're referring to.

[packetpirate]

@Disch, I was referring to this piece of code I edited out:

LinkedList<int> myList();

I was wondering why it was giving me an error. The reason is that unless I'm calling an overloaded constructor, and I'm just calling the default constructor, the parentheses shouldn't be there.

[m4ster r0shi]

This -> LinkedList<int> myList(); is a function declaration.

Check this out -> http://www.gotw.ca/gotw/001.htm

[packetpirate]

But if I was to call it with, say...

LinkedList<int> myList(myNode);

...assuming myNode is a node pointer, then wouldn't it call the constructor that takes a node as a parameter?

[m4ster r0shi]

Yes. But if you want the default constructor you should write -> LinkedList<int> myList;