LinkedList facelift

Martin Buchholz martinrb at
Tue Nov 3 02:29:37 UTC 2009

I would like to contribute an improvement to LinkedList


Josh, Bill and I have discussed this offline,
and they have given their blessing.
(i.e. I am not asking for reviewers)

I apologize for this - there are so many more important things to work on,
and no one is really using LinkedList
in performance-sensitive production code, eh?

Chris, could you file a bug?

Synopsis:  LinkedList facelift

- A list of size N should create only N+1 objects, not N+2.
- Use of null as sentinel value instead of a sentinel (Null Object)
  is slightly less convenient, but is measurably faster, since hotspot
  has to insert null checks (with NPE throws) anyways.
- generify
- warning removal
- gratuitous tests added.
- cosmetic doc improvements
- the original motivation for this was to have a O(1) clear,
  but we eventually decided against that
  - but we documented our decision.

Below is a stupid microbenchmark demonstrating app. a factor of 2 improvement in
"throughput", and a 50% increase in memory footprint.

public class LinkedListBench {
   public static void main(String[] args) {
       LinkedList spine = new LinkedList();
       long i = 0;
       long t0 = System.nanoTime();
       try {
           for (i = 0; ; i++) {
               spine.add(new LinkedList());
       } catch (OutOfMemoryError e) {
           System.out.printf("allocated = %d%n", i);
           System.out.printf("ns/object = %d%n", (System.nanoTime()-t0)/i);



More information about the core-libs-dev mailing list