Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-6368844

(coll) Provide scalable double-ended lists

    XMLWordPrintable

Details

    • Enhancement
    • Resolution: Unresolved
    • P3
    • None
    • 6
    • core-libs

    Description

      We should provide a generalization of ArrayDeque that also implements List.
      (Also, perhaps ArrayDeque should be retrofitted to implement List)

      It is known that one can implement resizable arrays with these performance characteristics:
      - O(1) insert and remove from head
      - O(1) insert and remove from tail
      - O(1) random access to read or write element i
      - O(sqrt(N)) wasted space
      - O(sqrt(N)) insert and remove from the middle

      The basic idea is to use ArrayDeques as the fundamental unit of storage, but if the
      size grows too large, expand to an array of ArrayDeques, and perhaps recursively
      to a tree of such arrays.

      Such a data structure won't have the best performance for any particular operation,
      but it won't have pathologically bad performance for any of the targeted operations
      when the size is large, a disease which afflicts all current collections.

      This data structure is *not* designed for multi-threaded use; it must be
      wrapped in a synchronizedFoo

      References:

      http://en.wikipedia.org/wiki/Dynamic_array
      http://www.cs.jhu.edu/~goodrich/cgc/pubs/index.html # Tiered vectors
      http://www.cs.brown.edu/cgc/jdsl/papers/tiered-vector.pdf
      http://jhu.edu/~goodrich/cgc/pubs/wads99.ps
      http://www.eecs.umich.edu/~bchandra/publications/oopsla01.pdf # Race free collections
      http://lampwww.epfl.ch/papers/techlists.pdf # Vlists
      http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf # RAOTS
      http://www.cphstl.dk/Report/Deque/cphstl-report-2001-7.ps # space-efficient deques
      http://www.cphstl.dk/Report/Deque-first-attempt/cphstl-report-2001-4.pdf

      Attachments

        Issue Links

          Activity

            People

              Unassigned Unassigned
              martin Martin Buchholz
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

                Created:
                Updated:
                Imported:
                Indexed: