I have been trying to compare definition of list and its implementation in Java as I feel there is a mismatch. Definition Of List DataStructure : a list or sequence is an abstract data type that implements an ordered collection of values, where the same value may occur more than once. [Taken from : http://en.wikipedia.org/wiki/List_(abstract_data_type) ] Now an ordered collection maintains the order of insertion of elements. Java Implementation of List -> ArrayList : As per this implementation, I have following points: If I initialize an ArrayList of say size 5, then I cannot directly insert element at 5th position without inserting elements at position 1,2,3,4 because it will go against ordering principle. So Java gives exception here which I completely agree with. ArrayList provides methods like "set(int index, E element)" and "add(int index, E element)" using which we can replace elements in middle of list and can also insert new elements in middle of list. I do not understand this. It is going against principle of ordering as insertion order is not maintained. I feel 1st and 2nd point are in conflict with each other and 2nd point is against principle of ordering or may be I am missing something. Can somebody please explain where I am going wrong in my understanding of List here?

The definition doesn't say anything about the size of the list or what happens when you add elements by index. It just says that the order of elements doesn't change "suddenly". This is the contrast to "set" types where the order of elements can change by adding new elements. If you insert an element at the 2nd position of a 5 element list, then the third element doesn't suddenly jump to the head of the list. The definition also doesn't say which operations must have, only what it might have. For efficient operations on lists, it's useful to have a method to insert an element anywhere (withing the legal boundaries, of course) and to be able to replace an element without changing the indexes of existing elements. If the second operation was missing, replacing elements would take add() plus remove() which are both expensive operations, depending on the implementation. Also both operations clearly explain how they influence the ordering of the other element when they are applied. set() doesn't change the ordering of the other elements while add() increments the index of all elements after the insertion point.

javalistdata-structures

Lokesh

Reputation: 7940

Java ArrayList implementation

I have been trying to compare definition of list and its implementation in Java as I feel there is a mismatch.

Definition Of List DataStructure: a list or sequence is an abstract data type that implements an ordered collection of values, where the same value may occur more than once. [Taken from : http://en.wikipedia.org/wiki/List_(abstract_data_type) ]

Now an ordered collection maintains the order of insertion of elements.

Java Implementation of List -> ArrayList : As per this implementation, I have following points:

If I initialize an ArrayList of say size 5, then I cannot directly insert element at 5th position without inserting elements at position 1,2,3,4 because it will go against ordering principle. So Java gives exception here which I completely agree with.
ArrayList provides methods like "set(int index, E element)" and "add(int index, E element)" using which we can replace elements in middle of list and can also insert new elements in middle of list. I do not understand this. It is going against principle of ordering as insertion order is not maintained.

I feel 1st and 2nd point are in conflict with each other and 2nd point is against principle of ordering or may be I am missing something.

Can somebody please explain where I am going wrong in my understanding of List here?

Upvotes: 4

Answers (6)

A4L

Reputation: 17595

As you have found out, ArrayList does not keep the order and has random get/set methods. This is correct.

I would say the wiki definition is just wrong, not completely correct, or does not apply to what Java understands under List, which is obviously a little less than Ordered List

If you want to have ordering on insert, Java SE API provides TreeSet to which you have to provide a Comparator at creation time or have the element inserted implement the interface Comparable. Otherwise, the elements are ordered using their natural ordering.

In my opinion Java's ArrayList is just a managed array, which is handy and fits for most use cases.

Upvotes: 0

Tadas S

Reputation: 1962

An ArrayList, just like any java.util.List, maintains the element insertion order.

Let's say we have an empty ArrayList. We add A, then B, then C. The list will look as follows: [A, B, C]. Not [C, A, B] nor [A, C, B]. Now, if we insert D at index 1, the list will look as follows: [A, D, B, C]. Not [A, B, C, D] or anything else, which may be perfectly possible for other types of Collections.

Java's List does not imply neither artificial element ordering, like Sorted collections do, nor random element ordering, like certain collections, such as HashSet and the like.

Upvotes: 1

Oliver Watkins

Reputation: 13509

An Arraylist has an order, thats all it means. If you insert a value somewhere it still has AN order, even if it seems silly. If you want to have a MEANINGFUL order, then you have to look at comparable interfaces.

Upvotes: 1

stan0

Reputation: 11807

ordered collection of values does not mean insertion-order. It means that there is a bunch of items placed somewhere one after another and you can access them in a sequence.

Having the ability to insert an item at a particular index gives you control over the order.

Upvotes: 1

Aaron Digulla

Reputation: 328594

The definition doesn't say anything about the size of the list or what happens when you add elements by index. It just says that the order of elements doesn't change "suddenly".

This is the contrast to "set" types where the order of elements can change by adding new elements. If you insert an element at the 2nd position of a 5 element list, then the third element doesn't suddenly jump to the head of the list.
The definition also doesn't say which operations must have, only what it might have. For efficient operations on lists, it's useful to have a method to insert an element anywhere (withing the legal boundaries, of course) and to be able to replace an element without changing the indexes of existing elements.

If the second operation was missing, replacing elements would take add() plus remove() which are both expensive operations, depending on the implementation.

Also both operations clearly explain how they influence the ordering of the other element when they are applied. set() doesn't change the ordering of the other elements while add() increments the index of all elements after the insertion point.

Upvotes: 2

Lukas Eichler

Reputation: 5903

You can add elements O to a list like XXXXXXX. With the added element you have XXXXXXO.

If you tried to add elements on a position that is greater than the size of the list you would have holes like XXXXXX O.

The add(position, element) is used to add elements inside the list like add(2, O) -> XXXOXX

A List isn't a field of possible position like an array but a collection.

Upvotes: 0

Java ArrayList implementation

Answers (6)

Related Questions