2

I tried to find an appropriate data structure for my data array. I prefer the one that supports insertion operation (insert in the middle of the list).

If there is no such Java built-in data structure, what is a good way to implement?

E.g. If I use ArrayList<String>, which seems not support insertion in the middle of the list, how to implement the insert(int pos, String str) in a good way?

JackWM
  • 10,085
  • 22
  • 65
  • 92

3 Answers3

5

Check out the ArrayList.add method (which is declared in the List interface that the ArrayList implements)

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Mark Peters
  • 80,126
  • 17
  • 159
  • 190
Bhesh Gurung
  • 50,430
  • 22
  • 93
  • 142
  • 1
    Note: _add_ is **NOT** specific to ArrayList. Every class that implements _List_ supports this operation. – jahroy Oct 16 '12 at 02:42
  • @jahroy: Yes I added that. Also the problem actually is that the docs also mentions that it's an optional operation. – Bhesh Gurung Oct 16 '12 at 02:44
  • @BheshGurung - I don't understand how a method in an interface can be optional (just re-read the documentation). I'm tempted to ask that in another question! – jahroy Oct 16 '12 at 02:48
  • 1
    @jahroy: Typically this should be interpreted as "this method may optionally always throw an `UnsupportedOperationException`". The language requires you to implement it, but gives you the option of an always-fail implementation that should never be called. (In the case of [`List`](http://docs.oracle.com/javase/6/docs/api/java/util/List.html#add%28int,%20E%29), this is explicitly documented: "*throws: `UnsupportedOperationException` - if the add operation is not supported by this list*") – Mark Peters Oct 16 '12 at 02:49
  • @jahroy: I guess that's because they had foreseen the situations where for certain implementations it would impossible to support that operation. – Bhesh Gurung Oct 16 '12 at 02:51
  • 3
    The method will always be there, but in some cases its implementation will throw a standard exception at runtime. In this case, it is to support things such as List wrappers for arrays, that do not (cannot) insert extra elements into the wrapped array. – Stephen C Oct 16 '12 at 02:53
2

Any class that implements List can do what you want.

Take a look at List.add(), which inserts an object at a given index.

If you want to replace the existing item, check out List.set().

The add() method is part of the List interface...

However, as the comments under Bhesh Gurung's answer suggest, not all Lists support it.

Therefore, I would go with Bhesh Gurung's answer (as you already have).

jahroy
  • 22,322
  • 9
  • 59
  • 108
  • What does `Set` have to do with `List`? – jahroy Oct 16 '12 at 02:39
  • the method set not the data structure set. duh – Herupkhart Oct 16 '12 at 02:40
  • Oh... Well, _set_ and _add_ are two different operations. One replaces the existing element, the other inserts before. – jahroy Oct 16 '12 at 02:41
  • Set() replaces an object at the specified index. I believe the OP wants to insert (add at a specified location and shift all other indices to the right). Even worse, if the specified index does not exist, set() throws an IndexOutOfBoundsException – Mike Oct 16 '12 at 02:43
  • @Mike - Ok, I changed switched the order in which I recommended the two methods: _add_ is now recommended before _set_. – jahroy Oct 16 '12 at 02:45
0

I think you should take a look at LinkedList add(int, E) method which provide better performance for insertion in the middle of the list compared to ArrayList.

tanyehzheng
  • 2,201
  • 1
  • 20
  • 33
  • 1
    ... and worse performance for all other operations, especially removing from the middle. – Mike Oct 16 '12 at 02:46
  • Don't use LinkedList naively. Refer [here](http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist) for when to use it. Both data structure have their strength and weaknesses. – tanyehzheng Oct 16 '12 at 02:52
  • Inserting elements at a given index is possible for every implementation of the List interface. As long as you don't know the OP's requirements, recommending one implementation over another for performance reasons seems doubtful. – Clayton Louden Oct 16 '12 at 02:54
  • @Richard I'm recommending it because the question was asking regarding insertion in the middle of the list. But anyway, I do see your point. Thanks for your comment. – tanyehzheng Oct 16 '12 at 03:00