Thread: Another Linked List

Though condition performance impact is not something new, I opened a new thread for it as it not relevant to list.

Nice usage of the Node constructor!

I consider the function PopBack and the [] operator for this class fundamentally wrong.
If the purpose of this class is speed, as evidenced by not wanting a branch statement, providing O(n) operations is far worse than a single if statement.
These two things conflict and contradict in a major way. There's a reason that the standard C++ library doesn't provide an [] operator for a list container.
Furthurmore, where a [] operator is supplied (and it shouldn't be here), it really needs to have a const and non-const version.

You could say that insertion and deletion from the middle are perhaps a necessary O(n) evil, when it comes to a singly-linked list. But I would perhaps still discourage the user of your class from doing such things by forcing them to have to implement these themselves if they so insist.

Conditional statements don't impact performance in the way you seem to think they do.

They have notable performance impact. I think 4 byte of memory costs less than their impact.

Firstly, it's not 4 bytes, it's the size of a node which is the size of a pointer plus the size of an int. 8 bytes on a standard PC.
Secondly, this is not a straight out "trade and in statement for 8 bytes" here because using an if-statement prevents users from screwing up the list via one too many pops, but the extra node does not.
Thirdly, in a number of circumstances, the lack of this saftey 'if statment' will cause the code using the class to need to implement this 'if statement' instead. At the very least that's a little unnecessary code bloat for something that should be only in one place.

I know you're having fun with this and are learning a lot, but be careful not to make the mistake many people make in assuming that they can design and write a better linked-list than a committee of experts can.

This list is only for practice. It may not be used anywhere. We consider that code using the class is carefully written and will not Pop more than its Push or at least has checks where it is needed. So it is not a important case for me. Of course for a practical program I would use standard library. But that 8 byte of dummy Node (4 of it is completely wasted) is the thing that bothers me.

I consider the function PopBack and the [] operator for this class fundamentally wrong.

When user needs random access she/he should not use linked list. OK. But I am not sure if I should implement the code for it or not. If I do user can decide whether to use them or not. We can note the O(n) in header file.