Re: your edit regarding ADTs: it's not that they are expensive to implement, it's that they give you no control over the physical structure of the data, which is the really, really important thing when it comes to how expensive it is to perform operations on that data. That's the point Rob was making in #5.

BTW, if you want to gain an understanding of this stuff, the difference it can make and why, I'd recommend reading basically anything by Michael Abrash.