title: What's the best way to have a gigantic ArrayList in Java?
body: <p>I need an ArrayList in Java that can have up to a million entries (I don't make the rules, I just implement them). ArrayList will clearly die well before 1 million (it may get there, but it's going to take a looong time). LinkedList won't work because there are places where I need to access it with get(index).</p>
  
  <p>What's the best approach for this? The best I've thought of is a 2-step array where the main array's elements point to a subset of the array. So each array holds 1,000 objects and the main array can point to 1,000 of these sub-arrays.</p>
  
  <p>The array is not sparse and is built up in order. And mostly then accessed in order.</p>
  
  <p>Update for some of the questions below:</p>
  
  <ol>
  <li>I do need ArrayList (or an equivalent) for the functionality I need.</li>
  <li>I do need it all in memory at once.</li>
  <li>I don't know how large it will be in advance. Normally it will be 4 - 20 elements. But at rare times it can be a million.</li>
  <li>I'm finding that once the array gets over 120K entries, it pauses about every 30 or so adds to it. So I'm assuming growing an ArrayList takes time as it gets large.</li>
  </ol>
  
  <p><strong>Update 2:</strong></p>
  
  <p>With some of the responses to this saying ArrayList should be fast enough, I wrote a small test routine to create a million row array one add() at a time. And it is (gotta dig into my code to see why that looks like the problem as it isn't).</p>
  
  <p>LinkedList seconds = 0.136</p>
  
  <p>ArrayList seconds = 0.087</p>