1

In the following piece of code, I have the result of a query, but I have no clue about the total number of records. I have to store it into a container. When I read each record of the container, it will be a simple loop so that index-based access will not be used.

  List<MyObject> list;

  while ( source.hasNext() ) {
      MyObject ob = new MyObject();
      convertObject(ob, source.next());
      list.add(ob);
  }

  ...

  //Another method

  for (MyObject ob : objects){
    showThings(ob);
  }

LinkedList is poor because it creates many small objects with pointers to the next one. It uses more memory, makes the memory more fragmented and has more cache miss.

ArrayList is poor because I don't know the number of records that I will insert. Whenever I insert a new item and the inner array is full, it will allocate a bigger block of memory and copy everything to the new block.

I didn't find any solution in java.util. So I consider writing a custom list. It will be like a LinkedList, but each cell is an array. In other words, the first node will be like an ArrayList, but when it is full and I insert a new object, it will create another node with an array to insert the new items instead of copying everything. However, I may be reinventing the wheel somehow.

Squall
  • 4,344
  • 7
  • 37
  • 46
  • 3
    https://stackoverflow.com/questions/33737669/when-to-use-gluelist-over-arraylist-or-linkedlist – Sotirios Delimanolis Aug 22 '18 at 00:24
  • 2
    What specifically is your problem with ArrayList? Performance? Memory? – shmosel Aug 22 '18 at 00:51
  • ArrayList has the overhead of moving the records when it runs out of space. – Squall Aug 22 '18 at 01:12
  • GlueList, which I didn't know that exist, is the solution. Thanks, that is the answer. – Squall Aug 22 '18 at 01:14
  • Solution for what? What's wrong with ArrayList? – shmosel Aug 22 '18 at 16:56
  • why not instance `ArrayList list;` and then call method `.size()` ?? – Martin Zeitler Aug 23 '18 at 07:18
  • @MartinZeitler You mean `trimToSize()`? – shmosel Aug 23 '18 at 07:56
  • @shmosel it reads "I have no clue about the total number of records" while `.size()` would return the count of (top-most) items; when being required to get count of nested items, one can still let those `` in the `ArrayList` make return their own size and add up that value in a loop. – Martin Zeitler Aug 23 '18 at 08:22
  • Sorry, I said "I have no clue about the total number of records", but I mean "I have no clue about the total number of records that I will insert". I can set the capacity of ArrayList, but it is not useful when the future number of records is unknown. – Squall Nov 01 '18 at 05:32

2 Answers2

0

Whenever I insert a new item and the inner array is full, it will allocate a bigger block of memory and copy everything to the new block

This is not true, you can preallocate a hash array of any size you want, and it only increments when it runs out of space, increasing by 50% each time, so if you have a reasonable guess of the expected size, or even guess a large number, the reallocation cost will be zero or minimal.

Jim Garrison
  • 85,615
  • 20
  • 155
  • 190
  • Is it correct to say _doubling each time_? I saw earlier implementations where the increase size isn't multiply by two... Just asking for my better understanding. Ty. – zlakad Aug 22 '18 at 00:41
  • 1
    @zlakad you are correct. Its usually 1.5x the size. – Obicere Aug 22 '18 at 00:59
  • It used to be double but it changed since the last time I looked at the source. – Jim Garrison Aug 22 '18 at 01:17
  • @JimGarrison Thx. (BTW, I didn't down vote). Right now I'm looking at source code for `ArrayList`. And, there are somethings I don't like... – zlakad Aug 22 '18 at 01:22
0

Some googling unveils the Brownies Collections' GapList. It is organizing its contents in blocks and manages them by arranging them in a tree. It also does block merging in case after element removal they become sparse.

Hero Wanders
  • 3,237
  • 1
  • 10
  • 14
  • I have added information to show the relevance of this particular implementation. Further aspects I should improve in my answer? – Hero Wanders Aug 22 '18 at 01:24