介于 LinkedList 和 ArrayList 之间

Question

在下面的一段代码中，我有一个查询的结果，但我不知道记录的总数。我必须把它储存在一个容器里。当我读取容器的每条记录时，它将是一个简单的循环，因此不会使用基于索引的访问。

  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很差，因为它创建了许多带有指向下一个对象的指针的小对象。它使用更多的内存，使内存更加碎片化并有更多的缓存未命中。

ArrayList很差，因为我不知道要插入的记录数。每当我插入一个新项目并且内部数组已满时，它将分配更大的内存块并将所有内容复制到新块中。

我在 java.util 中没有找到任何解决方案。所以我考虑写一个自定义列表。它将类似于 LinkedList，但每个单元格都是一个数组。换句话说，第一个节点将类似于一个 ArrayList，但是当它已满并且我插入一个新对象时，它将创建另一个带有数组的节点以插入新项目而不是复制所有内容。但是，我可能会以某种方式重新发明轮子。

Answer 1

一些谷歌搜索揭开了布朗尼系列的 GapList。它以块的形式组织其内容，并通过将它们排列在树中来管理它们。它还会阻止合并，以防元素删除后它们变得稀疏。