Good or bad idea for Linked List class?

[packetpirate]

I've been working on a Linked List class and I've made it doubly linked now. I'm wondering if this would be a good idea for overloading the [] operator. Instead of making it circular, where the last node links to the first and vice versa, what if I did something like this:

template< typename T >
T LinkedList<T>::operator[](int pos) {
    getPos(pos);
}
template< typename T >
T LinkedList<T>::getPos(int pos) {
    if(pos > size) {
        return getPos((pos - size));
    } else {
        node<T> *current;
        int i = 0;

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

That's not the full idea, but the gist of it is, instead of causing an error if you try to access a position larger than the size of the list, it will subtract the size of the list from the position, then access the position. It will keep subtracting from position as long as it is bigger than the size of the list. So for example, if I had a list of size 20 and I try to access position 36, rather than giving me a error, it would subtract 20 (the size of the list) from 36, giving me 16, and then it would access position 16. So it's LIKE a circular list, but a bit better. Would this have any practical use?

[hamsterman]

Operator [] for a list isn't very useful. If you intend to use it in a for loop it would be much much slower than a normal iterator.
Your method is recursive and thus wastes memory. You could easily do this in a loop. Also this doesn't take care of negative pos values.
Another thing to notice is that code while(pos >= n) pos -= n; is equivalent to pos %= n; for positive pos. The problem with % is that -5 % 3 = -2 while the answer you need here is 1.
I really have no idea which one is faster..

while( pos <= size ) pos -= size;
while( pos >= 0 ) pos += size;

or
pos = (pos%size+size)%size;.
I do know that the second one is quite ugly though...

[Abramus]

I strongly advice you not to make a random access operator for a list. If you need one, it means that you shouldn't be using a list in the first place.

[webJose]

Well, a consumer of the list class should be the judge of that, I would think. Surely it does sound like a no-match (the random access + list), but the consumer of the class is the one that ultimately calls it or not, so it really is not a bad thing to add, I would say.

BTW, I would support it differently (for performance reasons):

1. I would prepare an index in a C-styled array.
2. I would use the index for quick access.

The index would contain pointers to the corresponding nodes. Index preparation would be O(n) (correct me if not, please), and after that is just a matter of memory offsets (really fast).

If the list changes (insertion/deletion), then I would invalidate the index (destroy it) so it is rebuilt the next time operator[] is called.

[hamsterman]

@webJose
So basically you want to have a vector in the list and instead of changing the relevant part of that vector you want to change it all?
As Abramus said, if you want a [], list is not what you should write.

[webJose]

Say you have a linked list, right? That is scattered all over the place.

Sure is not very efficient to access the elements like an array, but if someone wanted, I would provide like this:

class MyList
{
private:
    node **_raIndex;
    void BuildIndex()
    {
        if (_raIndex) return;
        _raIndex = new node*[m_count];
        //Traverse the list with forward-only iterator.
        for (MyForwardOnlyIteratorType it = begin(), int i = 0; it < end(); it++, i++) _raIndex[i] = &(*it);
    }

    //Now operator[] can request the index and be fast after the first call.
    T& operator[](int index)
    {
        BuildIndex();
        return _raIndex[index]->data;
    }
};

NOTE: Above written but not tested.

That would be the basic idea.

[packetpirate]

I never said I NEEDED the [] operator, but this entire header file is just a learning tool. I'm trying to learn about Linked Lists by implementing my own class. Also, I haven't had much experience overloading operators, so I thought the [] operator might be useful for the list.

But I don't think anyone has yet answered my original question, on whether or not a pseudo-circular list using the [] operator would have any practical use.

[hamsterman]

@webJose, as I said, this is a vector+list. There is no aspect in which this would be better than a plain vector.

@packetpirate, operator [] that wraps around might be useful, however any kind of operator [] for a list is not.

[webJose]

I am not contradicting your post, hamsterman, except maybe in the fact that I believe there is value in operator[] for random access in a list. As seen, it does have some overhead, but it is ultimately the caller's responsibility if it is used or not.

As for this:

There is no aspect in which this would be better than a plain vector.

It is not true. A linked list outperforms a vector in insertion and deletion. Such a list with my operator[] would inherit the insertion/deletion performance of the linked list, plus fast random access to the elements paying a one-time cost of O(n) + 4 bytes per element. Therefore, it's better than a plain vector in several aspects. Or am I not understanding what you are saying?

[packetpirate]

Guys, I've already said this, but let me make this clear... I'm not trying to outperform a vector or even make anything incredibly useful. I'm using this as a LEARNING TOOL. I eventually might try to make it as efficient as possible. I merely wanted to know if there was any practical use to making a pseduo-circular list with the [] operator.

[webJose]

We know, packetpirate. Sometimes the threads branch a bit into related topics.

I haven't replied because I don't know of any practical use for a circular operator[]. The closest I can think of is the problem I had to code for a final in a code contest: An element of the problem was that you had to predict the position of buses in several bus stops at any given time. The buses had routes assigned and they would continually visit the bus stops in a loop.

So I had a function that would return the bus' position at any given time in the simulation. The entire route for a bus would require T minutes. If I wanted to know the position in time t where t > T, that would be kind of a circular look up. But then again, the math is really simple: t = t % T. You can use this formula instead of lines 7 and 8 in your code above and avoid recursion altogether.

[hamsterman]

@webJose, sorry, I ignored the fact that you only intend to reconstruct the vector when [] is called. (Though, of course, unless you have a flag showing whether reconstruction is needed, the performance will be similar or worse to that in original post).

@packetpirate, we kind of drifted away from your problem there. We're not saying you shouldn't have written this. There is never too much practice.

[webJose]

Yes, I just want the index constructed once in the first call of operator[]. The flag is the index pointer itself. The constructor of the class needs to set it to NULL for this to work, though. :D I did not show that. I also didn't show the destructor that needs to delete the index if one was ever created, and I don't show the explicit destruction (or modification) of the index in case of insertion or deletion. I just showed the very basic idea of the internal index.

[packetpirate]

Isn't the vector class a linked list? I'm just confused as to exactly how it works. It seems like one, considering you can add as many elements as you want, which is possible with a linked list.

[webJose]

It is not. The vector class uses an allocator object that provides full vector reallocation whenever needed. The vector class can become inefficient with very large number of items because it:

-Allocates new memory for the current elements plus a chunk large enough to contain the new element plus some more.
-Uses the copy constructor of the item and the placement new operator to copy the item from the old memory chunk to the new one.
-Deletes the old memory chunk.
-Now the array has some memory unused that will be used by several new items, until this memory is consumed and the copy process starts over from the top of this list.

At least this is my understanding of the vector class, and it is how I would have coded it.

[Abramus]

It is not true. A linked list outperforms a vector in insertion and deletion. Such a list with my operator[] would inherit the insertion/deletion performance of the linked list, plus fast random access to the elements paying a one-time cost of O(n) + 4 bytes per element. Therefore, it's better than a plain vector in several aspects. Or am I not understanding what you are saying?

Not on topic again, but I don't understand this. You need to reconstruct the array of pointers practically each time an element is inserted or removed from the list (assuming [] will be used quite frequently). How this is any faster than a vector?

[hamsterman]

Well, you're likely to have one part of the code that does multiple insertion and then another part that uses [] many times.
I still don't think this would be a useful feature for a list, but I guess it might perform well in some cases.

[m4ster r0shi]

Useful links -> [ http://en.wikipedia.org/wiki/Skip_list | http://stackoverflow.com/questions/256511/skip-list-vs-binary-tree ]

[moorecm]

I strongly advice you not to make a random access operator for a list. If you need one, it means that you shouldn't be using a list in the first place.

This. Plus, providing a confusing interface for users is a horrible idea. Save users from misuse a class any way you can.