4

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:

  1. 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.
  2. 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?

Improve this question
6
  • Check the formal definitions, as far as I understand ArrayList doesn't violate them. Commented Apr 26, 2013 at 10:28
  • Can you point me to some formal definition? Commented Apr 26, 2013 at 10:29
  • Check the wikipedia link. It's already there... Commented Apr 26, 2013 at 10:38
  • Please read post properly!! I have pasted deficinition from wikipedia only Commented Apr 26, 2013 at 10:41
  • I'm not referring to the definition that people may misinterpret... See the section Abstract Definition Commented Apr 26, 2013 at 10:44

6 Answers 6

Reset to default
2

  1. 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.

  2. 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.

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

3 Comments

When you say " order of elements doesn't change "suddenly". How do we measure sudden change ?
@loki: You can define that as: after an operation, the relative ordering of the elements which still stay in the list are the same.
Adding an element to a set can change the order of all elements. It might look as if someone had shuffled them. In a list, only elements after the insertion point changes and the relative order is always preserved: when I insert an element at position 2, element #2 is moved to position 3 but it's still after the first and before the old #3.
1

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.

Improve this answer

2 Comments

If i go by that defintion, then i should be allowed by ArrayList to insert elements at contiguos locations. So even if location 1 and 2 are empty, i should be allowed to insert at 3,4,5 as losg as it is contiguos. Isn't it?
Other languages (or even Java libraries implementing custom lists) may of course allow both lists with a non-contiguous index range or contiguous index ranges starting with an arbitrary index instead of 0. The API documentation for java.util.List does however imply that lists have a contiguous index range, which is numbered from 0 to length-1.
1

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.

Improve this answer

Comments

1

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.

Improve this answer

Comments

0

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.

Improve this answer

3 Comments

Don't you mean put in case of a position?
I agree with hole concept you talked about. How will you explain ordering?
put() is used by Maps and not by Collections. You order by implementing the Interface Compareable<T> and defining a ordering value algorithm. Then you could order the list with Collections.sort(list)
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.