I currently work in the capacity of Software Engineer at a reputed company in Sri Lanka. I'm most keen in J2EE Technologies and love working with open source libraries which fit my project needs. Very interested in the NoSQL concept and experimenting with various products to find a good blend for our projects within the company. Part time freelancer. Avid contributor in the stackoverflow arena. Android is another area which I am looking at with very keen interest as I believe mobile development is the way forward. Dinuka is a DZone MVB and is not an employee of DZone and has posted 24 posts at DZone. You can read more from them at their website. View Full User Profile

The story of the ArrayList imposter

07.28.2011
| 4342 views |
  • submit to reddit

Each and everyone of us, undoubtedly has had used Array lists in our lives as programmers. This story is about an imposter who lives among us, unnoticed, undetected until WHAM you are presented with a bug that makes no sense. Let me give you an example to reveal this imposter :). I have a hypothetical system that stores information on games and their ratings. A glimpse of the DTO i would use is as follow;

/**
 * A class to hold basic data about game titles
 * @author dinuka
 *
 */
public class Game  {

	/**
	 * The name of the game
	 */
	private String title;
	/**
	 * The rating users have given the game
	 */
	private int rating;
	
	public Game(String title,int rating){
		this.title = title;
		this.rating = rating;
	}

	public String getTitle() {
		return title;
	}

	public void setTitle(String title) {
		this.title = title;
	}

	public int getRating() {
		return rating;
	}

	public void setRating(int rating) {
		this.rating = rating;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + rating;
		result = prime * result + ((title == null) ? 0 : title.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Game other = (Game) obj;
		if (rating != other.rating)
			return false;
		if (title == null) {
			if (other.title != null)
				return false;
		} else if (!title.equals(other.title))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Game [title=" + title + ", rating=" + rating + "]";
	}
	
	
}

Nothing fancy. Just a plain old data holder value object with customary getter/setter methods. I have overriden equals,hashcode and tostring methods because i usually do that as a principal :). Ok moving on to reveal the culprit i will present you with a sample code and run the code and show you the problem at hand;

import java.util.Arrays;
import java.util.List;


public class Test {

	
	public static void main(String[] args) {

		Game[]gameArr = new Game[3];
		
		gameArr[0] = new Game("Metal gear solid 4",8);
		
		gameArr[1] = new Game("Unchartered 2",6);
		
		gameArr[2] = new Game("NFS Underground",2);
		
		Game[]newGameList = manipulateGames(gameArr);
		
		
	}
	
	/**
	 * Here we delete low rating games
	 * and add new game titles in place of those games
	 * @param gameArr
	 */
	private static Game[] manipulateGames(Game[]gameArr){
		List<Game>gameList = Arrays.asList(gameArr);
		
		for(int i=0;i<gameList.size();i++){
			Game game = gameList.get(i);
			if(game.getRating()<5){
				gameList.remove(game);
				Game newGame = new Game("NFS Hot pursuit 2",7);
				gameList.add(newGame);
			}
		}
		Game[]newArr = new Game[gameList.size()];
		return gameList.toArray(newArr);
	}
}

Ok these are my personal ratings i have given for the few of the games i love. Hopefully no one will take them personally because i do not want you to get off the topic here ;). So what we are doing here is, we have an array of games which we pass into a method which looks at the games with ratings lower than 5 and removes them and adds new games as substitutes. Do not consider implementation details as that is not my intention. My intention is to show you the problem at hand. So lets run this code and see what we get.

Ok what just happened? We get this really awkward error saying Unsupported exception. When i first got this i was thinking that maybe a previous version of java did not support removing from list given the object because i was at work using JDK 1.4 for work related things. But jdeclipse came to my help. If anyone has not used it, i can guarantee that it is one of the most useful plugins and a faithful companion in my eclipse workbench. Its a java decompiler which can decompile class files. Its much easier than downloading the JDK source and linking it.

I wanted to see the implementation of the Arrays.asList() method. This is where i found our little ArrayList imposter.....
 

    public static <T> List<T> asList(T[] paramArrayOfT)  
      {  
        return new ArrayList(paramArrayOfT);  
      }  

 

By the looks of it, there is nothing implicitly wrong with this implementation. So most probably it should be a problem with the ArrayList. Lets see whats happening there;

private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, Serializable
  {
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;

    ArrayList(E[] paramArrayOfE)
    {
      if (paramArrayOfE == null)
        throw new NullPointerException();
      this.a = paramArrayOfE;
    }

    public int size()
    {
      return this.a.length;
    }

    public Object[] toArray()
    {
      return ((Object[])this.a.clone());
    }

    public <T> T[] toArray(T[] paramArrayOfT)
    {
      int i = size();
      if (paramArrayOfT.length < i)
        return Arrays.copyOf(this.a, i, paramArrayOfT.getClass());
      System.arraycopy(this.a, 0, paramArrayOfT, 0, i);
      if (paramArrayOfT.length > i)
        paramArrayOfT[i] = null;
      return paramArrayOfT;
    }

    public E get(int paramInt)
    {
      return this.a[paramInt];
    }

    public E set(int paramInt, E paramE)
    {
      Object localObject = this.a[paramInt];
      this.a[paramInt] = paramE;
      return localObject;
    }

    public int indexOf(Object paramObject)
    {
      int i;
      if (paramObject == null)
        for (i = 0; i < this.a.length; ++i)
          if (this.a[i] == null)
            return i;
      else
        for (i = 0; i < this.a.length; ++i)
          if (paramObject.equals(this.a[i]))
            return i;
      return -1;
    }

    public boolean contains(Object paramObject)
    {
      return (indexOf(paramObject) != -1);
    }
  }

 

Huh what is that?? Its an inner class extending the AbtractList class,residing within the Arrays class baring the name ArrayList. The problem here is that it does not override all methods available within AbtractList thus throwing the UnsupportedException as defined within the class AbtractList .

Why they have done this im not really sure. It maybe because they are syncing the Array you passed initially and what ever update you do, is done to the original Array you passed in. But why chose such an implementation is a question mark for me.

So if you ever want to remove elements when using an ArrayList composed using Arrays.asList make sure to wrap it with a call such as newArrayList(Array.asList(myArr)); This will guarantee that you will use the concrete ArrayList implementation and not our imposter we just discovered.


So that ends the story of the ArrayList imposter that bothered me last week at work :)

Thank you for reading and hope you guys have a peaceful day of coding!!!

From http://dinukaroshan.blogspot.com/2011/07/story-of-arraylist-imposter.html

Published at DZone with permission of Dinuka Arseculeratne, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Jordan Slott replied on Fri, 2011/07/29 - 12:45am

Naturally, the specification for Arrays.asList() reads "Returns a fixed-size list backed by the specified array." This suggests that remove() is inappropriate on such lists.

It seems the choice of ArrayList for the name of the class is unfortunate, but it is private (and therefore can be changed in the future without breaking compatibility) I'd imagine. It certainly can be the source of a future bug (e.g. a new, confused Oracle software developer comes in and changes the implementation of asList() to fully qualify java.util.ArrayList). One would hope that a test case would catch it!

 Fun anecdote though, thanks for sharing ;-)

Shriniwas Kulkarni replied on Fri, 2011/07/29 - 1:45am

Check out core Java volume 1 (8th edition), under 'Collections' chapter. It will answer your question.

Matthieu Brouillard replied on Fri, 2011/07/29 - 4:20am

Nothing very surprising here, if you need to manipulate safelly a List object that some API returned to you you have to copy it into an implementation that ensures the actions you will do are supported.

Perhaps the Arrays.asList method should have been even less permissive by specifying that it returns an unmodifiable list so that it would have been clear that no modifications were allowed.

 

Ramasubramanian... replied on Fri, 2011/07/29 - 5:44am

The documentation clearly says
/** * Returns a fixed-size list backed by the specified array. (Changes to
* the returned list "write through" to the array.) This method acts
* as bridge between array-based and collection-based APIs, in
* combination with Collection.toArray. The returned list is
* serializable and implements {@link RandomAccess}.

The fixed-size means that the array elements can be replaced but not added or removed. The only reason i could think of is performance. Since removing or adding new elements to arrays is costly i.e. System.arrayCopy . Also it would seem irrational since arrays in Java are fixed size and an array is used as a base to create this list, hence the size is fixed i suppose

-Ram

Mladen Girazovski replied on Fri, 2011/07/29 - 9:50am

IMHO the reason is clear: asXXX vs. toXXX

Arrays.asList just shows an List representation of the array, and arrays are of fixed size, it doesn't state anywhere that a ArrayList ist being returned btw.

If there was an Arrays.toList Method, you could expect it to behave like an List where you can add & remove items, and the original array wouldn't be affected at all.

Dinuka Arseculeratne replied on Sat, 2011/07/30 - 1:27am

Thx guys for all your responses and comments. Greatly value them all.  Learnt alot from it.Cheers.

Viktor Cvetkovic replied on Sat, 2011/07/30 - 7:52am

I order to remove elements from ArrayList (any java.util.List) use java.util.Iterator. If you also want to add, repalce elements you should use the java.util.ListIterator.

Laurent Cohen replied on Sun, 2011/07/31 - 7:05am

Hi,

Looks like a typo, but in Test.main(...) you have the following:

gameArr[1] = new Game("Unchartered 2",6);
gameArr[1] = new Game("NFS Underground",2);

 Didn't instead mean "gameArr[2] = new Game("NFS Underground",2);" ?

Dinuka Arseculeratne replied on Sun, 2011/07/31 - 7:28pm in response to: Laurent Cohen

Thx a bunchh Laurent. Fixed it :)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.