However, it doesn't solve the question of memory usage. I know the 'classic' implementation of a bounded list is to have (in effect) a linked list within an array (or three arrays), but that was not what I actually intended. I actually intended the 'horrible' choice of an array where the first list item is stored in the first element of the array, the second in the second, etc. You might called this the 'na�ve' implementation. The reason why is because it is the most memory efficient, and I assume that some applications will require memory efficiency about speed concerns; especially considering that appends still can be done very fast. Possibly we need a different nomenclature, e.g. Bounded_List for the classic implementation, and maybe Bounded_Vector for the na�ve? Or Packed_List? -- Best wishes, Nick Roberts "Ted Dennison" wrote in message news:l%9I7.22965$xS6.35437@www.newsranger.com... > In article <3BF08501.50C83D22@acm.org>, Jeffrey Carter says... > > > >I'm not sure what you're saying here; perhaps that initial "O(N)" should > >be O(1)? Actually, for a bounded list you have 2 lists in the same > >array: the real list and a free list. Because of the free list, there is > >no searching for a hole. Insertions and deletions are O(1) for all > >positions. > > Ahhh. I'd fogotten that you can make a list of the free stuff. That's right, it > is O(1).