5 Replies - 5796 Views - Last Post: 16 October 2010 - 02:43 AM Rate Topic: -----

#1 SavantStrike  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 02-October 10

Need Help overloading [] operator for linked list class

Posted 12 October 2010 - 11:02 AM

I've been trying to solve this problem for several days now, and I'm just not getting anywhere. My professor wants me to create a linked list, and then to implement array style subscripting to change nodes in the linked list.

Here is the header file he provided (note that the overloaded [] operator was not included, nor was the size variable).
using namespace std;
#define TRUE 1
#define FALSE 0

struct NodeType{
int value;
NodeType *next;
};

class IntList{

friend ostream &operator<<( ostream&, const IntList & );
friend istream &operator>>( istream&, IntList & );

public:
IntList(); //default constructor
~IntList();//default destructor

const IntList &operator=( const IntList & );
const IntList &operator+( const int );
const IntList &operator+(const IntList &);

//what I think might be the solution
IntList &operator[](const int );


private:
NodeType *ptr;
int size; //not needed, but useful for keeping track of the number of nodes in the list

};



Here is the main he wants us to run:
int main ()
{

IntList a;
cout << a;
a= a+5;
a=a+10;
IntList b;
b=b+20; 
b=b+15;
a=a+b;//this was not explicitly stated as a requirement, but I know from other discussions he wants this 
a[0]=a[1];
cout << a;

return 0;
}



And here is the code I have so far for the implementation file. I know I'm not supposed to print inside an overloaded input function, but that is what the prof wants based upon the main he has provided (there is no printing in main). I've been lost as to how to implement [] in any kind of meaningful way, and beyond that I will most likely have to modify my overloaded = operator to accommodate the [] operator.

I'm really stuck here as this needs to be a member function, so there is no way to pass it two integer values, and I just can't seem to wrap my head around what it is I'm supposed to do to make this work. Any help would be appreciated

#include "linkedList2.h"

ostream &operator<<(ostream &output, const IntList &ls ){

    if (ls.ptr == NULL ){//check to make sure list to print is populated
        }
    else{
        NodeType *currTemp = ls.ptr; //set currTemp to address of first node in ls


        //list was populated from the tail, so values should be printed from the head
        while(currTemp != NULL  ){
            output << (currTemp->value) << " ";
            currTemp = (currTemp->next);
        }

        }
        output << endl;
        return output;
}

IntList::IntList(){
    ptr = NULL;
    size = 0;
}

IntList::~IntList(){

    if (ptr == NULL ){//check to make sure list to deallocate is populated
        //list is unpopulated, there are no nodes to delete, and already pointing to null
    }

    else{
        NodeType *tmp1 = ptr; //set tmp1 to address of first node in list to delete
        NodeType *tmp2 = ptr; //set tmp2 to address of first node in list to delete

        //go to last node in list
        while(tmp1->next != NULL){
            tmp2 = tmp2->next;
            delete tmp1;
            tmp1 = tmp2;
        }
        tmp1 = NULL;
        tmp2 = NULL;
        size = 0;
    }
}

const IntList &IntList::operator+(const int right){

        //create a new node
        NodeType *newNode = new NodeType;

        //init values in new node
        newNode->value = right;
        newNode->next = NULL;

        NodeType *tmp1= this->ptr; //temporary node for addition at tail when elements are in list
        NodeType *tmp2= this->ptr; //temporary node for addition at tail when elements are in list


        if (this->ptr == NULL){//then linked list is empty
                this->ptr = newNode;
                }
        else{
                while(tmp2 != NULL ){
                        tmp1 = tmp2;
                        //cout<< tmp->value << " ";
                        tmp2 = (tmp2->next);
                    }//at end of list
                tmp1->next = newNode;
            }

        this->size++;

        return *this;
}

const IntList &IntList::operator+(const IntList &right){

    int rSize = right.size;
    NodeType *lPoint= this->ptr;
    NodeType *rPoint= right.ptr;

    if (this->ptr != NULL){//linked list not empty
        //run to last element in this
        for(int i=this->size; i>1; i--){
            lPoint = lPoint->next;
        }
        //copy values in right into this
        for(int i=rSize; i>1;i--){
            lPoint->next = rPoint;
            this->size++;
            rPoint = rPoint->next;
        }
    }
    else{//linked list on left is empty
        int i=rSize;
        lPoint = rPoint;
        rPoint = rPoint->next;
        i--;
        if(rSize > 0){//more nodes to copy
            while(i>1){
                lPoint->next = rPoint;
                this->size++;
                rPoint = rPoint->next;
                i--;
            }
        }
        //implicit else, do nothing as there are no more nodes to copy
    }

    return *this;
}


const IntList &IntList::operator=(const IntList &right){

    NodeType *lTemp = this->ptr;
    NodeType *rTemp = right.ptr;
    NodeType *Last;


    if(&right != this){//check for self assignment

        //values were inserted at tail of list, so the copy should go from head to tail;
        if (this->size < right.size ){ //then the rvalue is larger than the lvalue
            Last = right.ptr;

            while(rTemp->next != NULL){
                Last = rTemp; //Last is one node before rTemp
                lTemp->value = Last->value;
                lTemp->next = Last->next;
                rTemp = rTemp->next;
            }
                lTemp->next = NULL;

        }
    }

    return *this;
}



Is This A Good Question/Topic? 0
  • +

Replies To: Need Help overloading [] operator for linked list class

#2 eker676  Icon User is offline

  • Software Engineer
  • member icon

Reputation: 378
  • View blog
  • Posts: 1,833
  • Joined: 18-April 09

Re: Need Help overloading [] operator for linked list class

Posted 12 October 2010 - 12:38 PM

Overloading the subscript operator should not be a chore.

Just think about it, all you need to do is return a reference to the node.
So start off by changing the return type to a node. Then create a variable 'count' and traverse the list 'count' nodes. If the list ends before you reach count nodes then throw an error.

This page has a great explanation: (You will have to navigate to 'Overloading Operators')
http://publib.boulde...e/ref/overl.htm

This post has been edited by eker676: 12 October 2010 - 12:39 PM

Was This Post Helpful? 2
  • +
  • -

#3 Bench  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 857
  • View blog
  • Posts: 2,343
  • Joined: 20-August 07

Re: Need Help overloading [] operator for linked list class

Posted 12 October 2010 - 02:18 PM

View Posteker676, on 12 October 2010 - 07:38 PM, said:

Just think about it, all you need to do is return a reference to the node.
Actually, if you think about what the subscript operator does on, say, std::vector or std::deque then it should return a reference to the stored data. i.e.
Intlist my_list;
//TODO: fill the list

my_list[5] = 0; 

the semantics of which would imply the signature is
int& Intlist::operator [] (size_t const); 


The problem with returning a reference to a node is that you're breaking encapsulation by leaking the internals of the Intlist - users of a linked list class should ideally not have to know anything about a 'node' whatsoever. (again, think about how the STL containers work - the std::list has no concept of a node as far as its user is concerned)

This post has been edited by Bench: 12 October 2010 - 02:20 PM

Was This Post Helpful? 1
  • +
  • -

#4 SavantStrike  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 02-October 10

Re: Need Help overloading [] operator for linked list class

Posted 14 October 2010 - 02:29 PM

View PostBench, on 12 October 2010 - 01:18 PM, said:

View Posteker676, on 12 October 2010 - 07:38 PM, said:

Just think about it, all you need to do is return a reference to the node.
Actually, if you think about what the subscript operator does on, say, std::vector or std::deque then it should return a reference to the stored data. i.e.
Intlist my_list;
//TODO: fill the list

my_list[5] = 0; 

the semantics of which would imply the signature is
int& Intlist::operator [] (size_t const); 


The problem with returning a reference to a node is that you're breaking encapsulation by leaking the internals of the Intlist - users of a linked list class should ideally not have to know anything about a 'node' whatsoever. (again, think about how the STL containers work - the std::list has no concept of a node as far as its user is concerned)


Wow, it's been entirely too long since I've gotten to this, but thank you all for the help! Between other classes and the more complicated problems on this assignment (polynomials in doubly linked lists, stacks, big integer addition with linked lists), I let this issue sit on back burner for a few days.

It's neither here nor there, but I'm a bit nervous as to what I'll do for all of this on the test (word is that the prof makes us write these types of programs with pen and paper on the tests, and the tests are worth 1.5x as much as the assignments are). I still had to scratch my head for an embarrassingly long period of time to understand what I was doing here :whistling:. It will be fun when we start on binary trees next week, and then later when we get to shortest path algorithims :bigsmile:.

At any rate, I was only able to get this to work when I tried using plain integers for both the return type and the parameter instead of a NodeType for a return type. I know the NodeType way should work as I talked to a classmate that got it to work, but I have no idea how I was screwing it up. It was pretty impressively messed up though. All that really happened was that one of the values in the linked list went away, or I would get an endless loop where the value to be changed was printed to the terminal (which was impressive as I didn't have any kind of print statement). Which behavior occurred was directly related to which index was larger, the right or the left side.

Valiant attempt at failure (any pointers as to how I could get this to work if I needed to do it this way)?
NodeType &IntList::operator[](int right){

	NodeType *tmp1 = this->ptr;


	for(int i = 0; i< right; i++){
		cout << "its " << i << endl;
		tmp1 = tmp1->next;
	}

	//cout << "tmp1 value " << tmp1->value << endl;

	tmp1->next = tmp1;

return *tmp1;
}



Working solution - sans the size_t designation. I know size_t is the difference between two pointers, but I could use some clarification as to how it would help in this case, and how to apply it in general. More knowledge is always better :).
int &IntList::operator[](const int right){

	NodeType *rPtr = this->ptr;

	for(int i=0; i<right; i++){
		rPtr = rPtr->next;
	}

	return rPtr->value;
}


Was This Post Helpful? 0
  • +
  • -

#5 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 356
  • View blog
  • Posts: 783
  • Joined: 27-June 09

Re: Need Help overloading [] operator for linked list class

Posted 14 October 2010 - 03:28 PM

View PostSavantStrike, on 14 October 2010 - 01:29 PM, said:

NodeType &IntList::operator[](int right){

	NodeType *tmp1 = this->ptr;


	for(int i = 0; i< right; i++){
		cout << "its " << i << endl;
		tmp1 = tmp1->next;
	}

	//cout << "tmp1 value " << tmp1->value << endl;

	tmp1->next = tmp1;

return *tmp1;
}



tmp1->next = tmp1; breaks your list. if you have 10 ints, and you call a[0], that line will make the head node point to itself and you will not be able to access the rest of the list.
Was This Post Helpful? 1
  • +
  • -

#6 Bench  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 857
  • View blog
  • Posts: 2,343
  • Joined: 20-August 07

Re: Need Help overloading [] operator for linked list class

Posted 16 October 2010 - 02:43 AM

View PostSavantStrike, on 14 October 2010 - 09:29 PM, said:

Working solution - sans the size_t designation. I know size_t is the difference between two pointers,
The difference between two pointers is ptrdiff_t, whereas size_t is usually for the size of something (e.g. an array or STL container).
The distinction is that ptrdiff_t is signed (a difference may be negative) whereas size_t is unsigned (there's no such thing as a negative size)

both size_t and ptrdiff_t should be represented by the same number of bits in memory, although the number of bits depends on the maximum number of addressable memory locations the system supports. On a 16-bit IBM Compatible PC, they are probably going to be 16 bits in size, on a modern 32-bit desktop they are probably 32 bits, and on a modern 64-bit Desktop/server it'll probably be 64-bits.

(Note, if all you're doing is developing desktop apps then your world is probably a 32-bit or 64-bit one. If you start playing around with other devices, then you might find hardware where a 'byte' is not 8 bits, and maximum address space follows some completely different rules)


View PostSavantStrike, on 14 October 2010 - 09:29 PM, said:

but I could use some clarification as to how it would help in this case, and how to apply it in general. More knowledge is always better :).
int &IntList::operator[](const int right){

	NodeType *rPtr = this->ptr;

	for(int i=0; i<right; i++){
		rPtr = rPtr->next;
	}

	return rPtr->value;
}

if you change your 'size' argument types to size_t, then that ought to work without any warnings.
i.e.
int &IntList::operator[](const size_t right){
for(size_t i=0; i<right; i++){

size_t is a typedef for an unsigned integral type (typically unsigned int or unsigned long), but what you've done is fine aswell. the difference would only be significantly noticable if you had, for example, a linked list whose size is greater than 2^(sizeof(int)-2), and you decided to try to access an element position beyond that which a signed int can represent.

also, using int can potentially bring about portability issues (e.g. between a 32-bit and a 64-bit system).

I'm guessing you probably don't care about any of those issues right now, so int is just fine, but its good to be aware of these things.

This post has been edited by Bench: 16 October 2010 - 02:47 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1