• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Arraylist insert at specific index performance query

 
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Given an arraylist of objects with size 10. I need to insert two elements, one at index 2 and other at index 9. Which of the two insertions would be faster?
 
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
ArrayList is nothing other than a LIST itself so whether you insert at 2 or 9 doesn't make a difference as far as insertion time is concerned. However note that the situation would have been different had it been a LinkedList since it involves an insertion order. The insertion has to take place though HEAD and ends at TAIL. So in such a situation insertion at 2 will definitely be faster than insertion at 9.
Please correct me if I am wrong.
 
Sheriff
Posts: 22789
131
Eclipse IDE Spring Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
ArrayList uses an array as its backing storage. When you add something at index 9, it has to shift the element at position 9 up by one. That's one element. When you add something at index 2, it has to shift the elements at positions 2 and higher up by one. That's 8 elements initially.

LinkedList will not shift anything but instead just puts a new link in between. That is equally fast regardless of the position. However, it first must find the position, and that will take (just a bit) longer for index 2. That might surprise you, but LinkedList knows that 9 is nearer to its end than to its start so it will go backwards from the end.
 
Bartender
Posts: 11497
19
Android Google Web Toolkit Mac Eclipse IDE Ubuntu Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"Maya Dolas"
Please check your private messages for an important administrative matter.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic