• Post Reply Bookmark Topic Watch Topic
  • New Topic

Deleting range (fromIndex, toIndex) from ArrayList.  RSS feed

 
Aleksey Movchan
Ranch Hand
Posts: 49
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello.

Can someone tell me please the best way of deleting range (fromIndex, toIndex) from ArrayList?
I know that I can use delete(index) in cycle, but it costs a lot. I'm sure there is a better way.
Let's say I want to delete elements in my ArrayList from 10 index to 20.

Thank you.
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
it costs a lot

Why do you say that?
Have you run any tests to measure the cost?

What about creating a new list and doing two copies for the items outside of the range?
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Have you looked at the api of ArrayList? There might be a handy method present.
 
Aleksey Movchan
Ranch Hand
Posts: 49
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Norm Radder wrote:
it costs a lot

Why do you say that?
Have you run any tests to measure the cost?


Considering it shifts all remaining elements from the right to the left every time I use delete(index), if I decide to delete all elements from index 100 to 200 in 1000 size array, it will take huge amount of time. I don't think that I need to run tests to measure the cost in this situation. I think there obviously is something like System.arraycopy for arrays.
I tried to use subList(firstIndex,lastIndex) operation, but it's not working this way:

I think i need to use addAll operation, but don't know how
Or may be someone just know the better way.
 
Norm Radder
Rancher
Posts: 2240
28
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Did you see Piet's post?  Look at the class's API doc: http://docs.oracle.com/javase/8/docs/api/index.html
 
Campbell Ritchie
Marshal
Posts: 56546
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I went through the List interface and couldn't find a method to do that sort of thing. I did however find something promising in ArrayList. What is going on when there are methods in the implementations which aren't in the interface?
 
Dave Tolls
Ranch Foreman
Posts: 3061
37
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It comes from AbstractList and is protected.
Reading the description on that, it seems to be used on the clear operation?
 
Tobias Bachert
Ranch Hand
Posts: 86
18
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The objective is to delete (=clear) a range (=sublist) from a list -> the initial approach should be to use list.subList(fromIndex, toIndex).clear().

We expect O(n) performance (as the basic approach would be to shift elements from toIndex to fromIndex and delete the excessive trailing elements, starting with the last one) - a peek into java.util.AbstractList shows that #clear is implemented aswhereas ArrayList and ArrayList$SubList override #removeRange to use an approach similar to the one described above.
 
Campbell Ritchie
Marshal
Posts: 56546
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tobias Bachert wrote:. . . shift elements from toIndex to fromIndex and delete the excessive trailing elements . . .
Maybe there is a way to use System#arraycopy or similar to copy nulls into the trailing elements which doesn't run in linear time.

Ordinarily I wouldn't expect a method called sublist to allow clearing like that, but I see its documentation says you can clear it like that.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!