Sample Question:

sdfsdfsf

JSR Notes:

Collection as a general term

Recall that a "data structure" is a group of a particular data type (or even a mix of data types). So all things such as arrays and linked lists and trees are, in general, data structures. And a sub-set of data structures is "collections". What will distinguish collections from arrays is that collections are able to grow and shrink in size, within the memory of the IT device.

Characteristics of Collections

A collection is any programming structure which holds a group of similar elements, *and* can dynamically change its size. In terms of this general definition, note that Java has a particular Collections framework available to us, made up of a variety of collection-type classes.

With the definition of collection being a grouping of similar things, which can grow or shrink in size, it means we do not include arrays, since they cannot change in size.

Kinds of Collections

There are a few general kinds of collections, but for our purposes there are two main kinds, lists and trees. (And in fact, trees is an HL only subject.) A list is just as you would think of it: a series of items, which follow one after the other. Which may seem to you not that dissimilar to an array. The big difference is that the list can grow and shrink; you can add to the list, or scratch things off of the list.

The Collections classes of Java

In Java, there is a framework/library of collection-like classes called the Collections Framework. Later on, in HL, we will look at two of those classes in detail:
- ArrayList which is an array which actually works dynamically like a list, and
- LinkedList which is a full implementation of a linked list.

The usefulness of Collections - i.e. the application of collections

Collections are used to conveniently work with groups, often very large groups, of data, and without wasting memory space.

Recall that computers are mainly good at two things: complex decision structures, and working with lots of things very quickly. The later needs some way to group these "lots of things"; collections (along with arrays), allow this.

So we find collections used everywhere in IT, whether it be collections of serial numbers, or collections of letters on a page, or collections of Student objects in a school database.

 

 

The Teaching Note above points to the key operations needed for work with collections:

Collections can have data added to them or taken away

With our "OurList class", the five methods we use all center around adding and retrieving of data from our lists. For starters, we use addItem( ) to add to our list, getNext( ) to get data from our list, one item after another. And the other three methods basically assure we are doing these things properly, by starting from the front of the list, with resetNext( ), by not working with an empty list, with isEmpty( ), and by only trying to get a next item if there is one, with hasNext( ).

Remember that the adding and removal from these collections is what distinguishes them from arrays. Yes, you can "add" values to existing elements of an array, but you can't add elements in memory to an array. Arrays are static in length; their size cannot change. Whereas Collection class objects are dynamic, in that they can grow and shrink. Much more on this later in HL Topic 5. But for now, the point is that Collection class objects can indeed, standardly, have data added or removed from them.

And when we get into using the HL Java Collections classes of ArrayList and LinkedList, we'll see that they actually have a variety of methods called things like "addFirst( )", and "removeLast( )", "push( )", and "pop( )", and so on.

        LinkedList<Integer> list = new LinkedList<Integer>();
        list.addFirst(3); //adds 3 to the list
        list.addFirst(234);
        list.addFirst(997);
        System.out.println(list.getLast( )); //prints 3
        System.out.println(list.removeLast( )); //prints and removes 3

 

Traversal of Collections

Adding and taking away from a list is good. But for a whole collection to be truly useful, one key features is its abiilty to be traversed.

Collections will offer a way to "traverse" through the data efficiently one way or the other. In the case of particular Java Collection classes ArrayList and LinkedList, it is by using some sort of an iterator, which operates by some sort of "getNext( )" pointer mechanism (an HL topic). Alternatively, often, we can simply use a while or for loop to iterate through the entire list collection.

Here are a couple of examples of adding to lists, and then traversing through them in a compact way: while or for loop.

Using our "pure" OurList class:

        OurList<String> list = new OurList<String>();
        list.addItem(new String("hello"));
        list.addItem(new String("world"));
        list.addItem(new String("how are you?"));
        //a couple of more lines here ,we'll add soon.
        while (list.hasNext()) {
            System.out.println(list.getNext());
        }
        

Using the Java Collections ArrayList class:

        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(3);
        list.add(234);
        list.add(997);
        for(int i = 0; i < list.size(); i++){
            System.out.println(list.get(i));
        }

Note that Collections are OOP objects
Collections are actually, themselves, objects which point to the data they represent. That is to say, just like an array, a list variable is technically the address of where the list's content starts, in memory. A distinct advantage of having this kind of implemented is that the object/address itself can be passed as a parameter. This saves on doubling up the memory required whenever working with a collection in another method.

    public static void main(String[] args) {
        OurList<String> myList = new OurList<String>();
        method1(list);
        System.out.println(list.getNext()); //prints Hello
        System.out.println(list.getNext()); //prints World
    }
    
    public static void method1(OurList<String> list){
        list.add("Hello");
        list.add("World");
    }

One final reminder to keep in mind that Java arrays are not an implementation of the Collection framework. Arrays are a fundamental structure of Java. Yes, they generally can be seen as collections, but they are not implementation of the Collection class.

(The Java util package contains an abstract class called Collection from which specific implementations of it have been made, for example, ArrayList, and LinkedList and TreeSet. And if you really want to see ArrayList and/or LinkedList in operation at this point, you could look ahead to the HL topic D.4.11.)