Remove objects from ArrayList

Question

I have two classes, Image and Channel.Image has an imageId and Channel has a channelId which uniquely identify an Image and Channel object.Some other attributes are also present.

Image class also has a channelId, using which I determine to which channel the image has been assigned to. I have a two ArrayLists of Image and Channel respectively.

    List<Image> imageList = getItemist("image");
    List<Image> channelList = getItemList("channel");

Now, I would like to remove all those image objects from the image list which contain channelId which are present in the channel objects of the channelList.

As of now, I am iterating the two lists and then comparing the channelId, putting the Image objects in a TreeSet and finally returning a list.Can you please help me with a solution that is simpler or more efficient ?

drew moore · Accepted Answer · 2014-07-29 02:15:54Z

2

This sounds like a good use-case for a ListIterator:

ListIterator iter = imageList.listIterator(); 
Image curr = null;
while (iter.hasNext){
    curr = iter.next();
    for (Image img : chanelList){
        if (img.chanelId == curr.chanelId){ //assuming chanelId is a primitive 
            iter.remove(curr); //remove curr 
            break; //break from the for loop to go on to the next image in imageList
        }
       //implicit: else continue; (i.e. go on to check the next image in chanelList)
    }
}

Note that this is an O(n^2) algorithm that won't scale well for large list sizes. There are ways to optimize it further (see @dasblinkenlight's comment, for one), but for purposes of conceptual clarity, I'll limit the scope of this answer to this.

edited Jul 29, 2014 at 2:15

answered Jul 29, 2014 at 2:10

drew moore

32.8k17 gold badges79 silver badges113 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Sergey Kalinichenko Over a year ago

Put chanelList into a hash set to make it O(img+chn) rather than O(img*chn)

drew moore Over a year ago

@dasblinkenlight - yeah, I know. one step at a time, though. see edit.

fabian Over a year ago

@dasblinkenlight: As far as I know removing a element from a ArrayList is in O(n), which would make this algorithm O(img² * chn) instead of O(img*chn).

Sergey Kalinichenko Over a year ago

@fabian You're right, it's n^2 for array lists. The code says simply List, but the title does talk about array lists.

Sergey Kalinichenko Over a year ago

@fabian That is what I said in my comment above, no?

|

fabian · Accepted Answer · 2014-07-29 02:34:55Z

2

Inserting n elements to a TreeSet requires O(n*log(n)) time. However you don't need the Set to be ordered. A HashSet should be faster in the average case (of course you can still be unlucky with the hash codes).

You can then modify the list based on the set:

HashSet<Integer> channelIds = new HashSet<>();
for (Image channel : channelList) {
    channelIds.add(channel.channelId);
}

// following removal code is specialized for lists that
// allow random access, like ArrayList
final int size = imageList.size();
int j = 0;
for (int i = 0; i < size; i++) {
    Image image = imageList.get(i);
    if (!channelIds.contains(image.channelId)) {
        imageList.set(j++, image);
    }
}
if (j < size) {
    imageList.subList(j, size).clear();
}

edited Jul 29, 2014 at 2:34

answered Jul 29, 2014 at 2:19

fabian

82.9k12 gold badges99 silver badges124 bronze badges

Collectives™ on Stack Overflow

Remove objects from ArrayList

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related