Results 1 to 3 of 3
  1. #1
    pifrely is offline Member
    Join Date
    Jan 2013
    Posts
    10
    Rep Power
    0

    Default Implementation of ArrayList

    I took a class in data structures some time back. In it, I learned that the ArrayList is an array that is just copied into a bigger array when space runs out. But instead of copying everything, even though it happens in amortized constant time, wouldn't it be better to represent it as a doubly linked list of arrays? When it exceeds the current capacity, you can add a new array that's twice as big as the previous one. Or better yet, an ArrayList of arrays, since you can access individual elements with just 2 []/get() operations, and you need to resize the ArrayList much less frequently (and copying comparably fewer elements each time). Of course, it'll make the code for a great deal of operations a bit more complicated, but would the performance benefit be worth it? Are there any reasons not to implement an ArrayList in this way?
    Last edited by pifrely; 02-10-2013 at 08:11 PM.

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,525
    Blog Entries
    7
    Rep Power
    20

    Default Re: Implementation of ArrayList

    The current ArrayList implementation guarantees the random access is O(1); I don't think a doubly linked list of 'chunks' can do that ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    pifrely is offline Member
    Join Date
    Jan 2013
    Posts
    10
    Rep Power
    0

    Default Re: Implementation of ArrayList

    Well, no, probably not. But what of the ArrayList of chunks?

Similar Threads

  1. Replies: 12
    Last Post: 07-07-2011, 08:49 PM
  2. copying contents of an ArrayList to another ArrayList
    By ankit1801 in forum New To Java
    Replies: 8
    Last Post: 03-27-2011, 06:07 AM
  3. sorting arraylist based on another arraylist
    By busdude in forum New To Java
    Replies: 4
    Last Post: 02-07-2011, 11:48 AM
  4. Replies: 7
    Last Post: 11-22-2010, 01:26 PM
  5. Replies: 2
    Last Post: 04-21-2008, 11:43 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •