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

(coll) Provide scalable double-ended lists

    Details

    • Type: Enhancement
    • Status: Open
    • Priority: P3
    • Resolution: Unresolved
    • Affects Version/s: 6
    • Fix Version/s: None
    • Component/s: core-libs
    • Labels:

      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

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

                Dates

                • Created:
                  Updated:
                  Imported:
                  Indexed: