1

I am new to Collections and I am sorry in advance for the trivial question but I have been pondering on a one sentence I have read in Java tutorial that

A List is an ordered Collection (sometimes called a sequence).

What I have understood from it is that as I put elements in a list, it does automatic ordering for me and since I ran a simple code, it proved I was wrong:

List <String> list = new ArrayList<String>();

list.add("Chris");
list.add("Brian");
list.add("Matt");
list.add("Greg");

for (Iterator<String> it = list.iterator();it.hasNext();) {
    System.out.print(it.next()+"\n");
}

which resulted in this not being ordered in any way:

Chris
Brian
Matt
Greg

So my question is What is meant by "A list is an ordered collection" ?

Thanks

Adrian L
  • 443
  • 1
  • 8
  • 19
  • 6
    It is very ordered. You are confusing `ordered` with `sorted`. – Keppil Jun 04 '13 at 19:11
  • 1
    It is ordered, in the sense that the order that you get the items when you iterate it is the same order that you inserted items into it. – Robert Harvey Jun 04 '13 at 19:12
  • @Keppil "ordered" generally could mean ordered by anything - insertion order, lexicographic order, random order, or something else. It's only in this context that "ordered" stands for "ordered by insertion order". –  Jun 04 '13 at 19:13
  • @delnan: I didn't say anything about insertion order. – Keppil Jun 04 '13 at 19:14
  • @Keppil You better had been thinking about it though ;-) What I'm saying is, "sorted [by X]" is also an order. A sorted collection is ordered (by X) in the usual sense of the word, just not "ordered" in the data structure sense. –  Jun 04 '13 at 19:17
  • @delnan: Not sure why you are directing this at me. Nothing I wrote contradicts anything you are saying. – Keppil Jun 04 '13 at 19:19
  • @delnan You can specify the index as you add. So insertion order is sort of a misnomer. – Lee Meador Jun 04 '13 at 19:19
  • @Keppil If you say so, great; I interpreted your comment as implying (among other things) that what OP is looking for isn't "ordered" but "sorted". LeeMeador Ah, right, I keep forgetting. It's a misnomer, unfortunately a common one. –  Jun 04 '13 at 19:22

5 Answers5

6

Ordered doesn't mean sorted, it means that the items will show up in the order you put them in.

This is in contrast to, say, a SortedSet where the items will not be ordered in the order you put them in, they will be sorted according to whatever sort criteria you put, or a HashMap, where they might show up in any order at all, depending on the hash function.

Joel
  • 5,618
  • 1
  • 20
  • 19
  • Only a sorted Set will give you items in a sorted order. A `HashSet`, for instance, doesn't specify any ordering. – yshavit Jun 04 '13 at 19:49
4

A List is an ordered Collection (sometimes called a sequence).

This means that a List maintains the order of the elements. In other words, the first element you add remains at index 0. The second element you add remains at index 1. And so forth.

If you remove an element, the rest of the elements remain in the same order, although the elements after the removed element change their index positions.

Gilbert Le Blanc
  • 50,182
  • 6
  • 67
  • 111
  • You can add them by specifying the order. `add(a); add(0,b); add(1,c); add(0,d);` They end up d, b, c, a (I think). – Lee Meador Jun 04 '13 at 19:16
  • @Lee Meador: Not on an initial insert. You get an IndexOutOfBoundsException if the index is out of range (index < 0 || index > size()). The add with a position is the equivalent of an insert. You changed your comment as I was typing mine. Your changes make the sequence correct. – Gilbert Le Blanc Jun 04 '13 at 19:20
  • Caught me, eh. I though I fixed it fast enough. I forgot you can't add past the end for just one moment. – Lee Meador Jun 04 '13 at 19:25
2

By ordered, it means that each element is assigned an index and can be referenced by that index. In a Set, things don't have an index.

waldol1
  • 1,841
  • 2
  • 18
  • 22
  • Only an ArrayList provides an index. A LinkedList, for instance, has to iterate through the list to get at the nth element, making their "index" operation very slow. – Joel Jun 04 '13 at 20:53
  • The operation may be slow, but it is defined. The notion of an index for unordered collections is undefined. – waldol1 Jun 04 '13 at 21:08
0

They are ordered in the order you put them in. Not sorted as in alphabetically or numerically. An unordered list (collection) would be like grabbing marbles out of a bag.

eidsonator
  • 1,319
  • 2
  • 11
  • 25
0

It simpy means if you put objects in in a certain order they will remain in that order. Note how your names come out in the same order as you put them in.

Compare this to a set (annother type of collection) in which they come out in a random order (because internally the set has no order). This can give performance advantages and if order is unimportant its usual to use a set, if it is important use a list.

Richard Tingle
  • 16,906
  • 5
  • 52
  • 77