Just over 5 years ago I had an interview at APT and after a mammoth interview (the longest I’ve ever experienced) the interviewer told me he thought I’d done well but he was a little disappointed that I didn’t know how the TList class in Delphi was implemented (an internal array as it happens, as opposed to a linked list). Fast forward to now and I was having a telephone interview today where the discussion turned to data structures and the difference between an array and a linked list. We discussed how a list like this could be improved to provide faster random access. I probably didn’t do too well on this, since the internals of collection classes are generally not something I’ve needed to worry about too much but I probably should think about them some more since they do seem to turn up in interviews a lot.
But after all this talk of linked lists, how is the List<T> class (or the ArrayList class for that matter) actually implemented? Well, after firing up Reflector I discovered that, just like in Delphi, these classes actually use an array internally. I can only presume the overhead of having to resize the array when more items are added is outweighed by the memory fragmentation and slow random access of a linked list. Of course if you really want a linked list, there is a LinkedList<T> class available.
No comments:
Post a Comment