This chapter is the first in our coverage of collections.

Collections are used to organize and process a number of objects or values of the same type. In almost any real-life program, collections of objects or values play important roles.

Collections fit nicely in our agenda of object-oriented programming. A collection holds a number of objects (of the same type), but a concrete collection is also itself an object. The commonalities of a number of collections objects are described by the type of the collection objects. In the following chapters we will encounter a number of different interfaces and classes, which represent collection types. Not surprisingly, generic types as discussed in Chapter 42, play an important role when we wish to deal with collections that are constrained to contain only objects of a particular element type.

In the rest of this short introductory chapter we will briefly outline the historic development of collection programming. In the main part of the lecture, Chapter 45 and Chapter 46, we deal with two main categories of collections: Lists and Dictionaries.

44.1 A historic View on Collection Programming

 

44.1.  A historic View on Collection Programming
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We identify three stages or epochs related to the development of collections:

Native arrays and custom made lists Fixed sized arrays - limited set of operations Variable sized linked lists - direct pointer manipulation First generation collection classes Elements of type Object - Flexible sizing - Rich repertoire of operations Type unsafe - Casting - Inhomogeneous collections Second generation collection classes The flexibility of the first generation collections remains Type safe - Generic - Type parameterized - Homogeneous

Arrays are fundamental in imperative programming, for instance in C. In older programs - or old-fashioned programs - many collections are dealt with by means of arrays. Many modern programs still use arrays for collections, either due to old habits or because of the inherent efficiency of array processing. The efficiency of arrays stems from the fact that the memory needed for the elements is allocated as a single consecutive area of fixed size.

Another fundamental technique for dealing with collections is encountered in linked lists. In linked list one elements is connected to the next element by a pointer. The linking is done by use of pointers. In single-linked list, an element is linked to its successor. In double-linked list, an element is both linked to its successor and to its predecessor. Linked trees, such as binary trees, are also common. In some languages (such as C and Pascal) linked data structures require explicit pointer manipulation. Other languages (such as Lisp) hide the pointers behind the scene.

First generation collection classes deemphasize the concrete representation of collections. Instead, the capabilities and interfaces (such as insertion, deletion, searching, conversion, etc) of collections are brought into focus. This reflects good and solid object-oriented thinking. Typical first-generation collection classes blur the distinction between (consecutive) arrays and (linked) lists. The concept of an ArrayList is seen both in early versions of Java and C#. Collection concepts are organized in type hierarchies: A List is a Collection and a Set is a Collection (see Section 25.2). The element type of collections is the most general type in the system, namely Object. As a consequence of this, it is hard to avoid collection of "pears" and "bananas" (inhomogeneous collections). Thus, type safeness must be dealt with at run-time. This is against the trend of static type checking and type safety. We will briefly review the first generation collection classes of C# in Chapter 47.

The second (and current) generation of collections make use of generic types (type parameterized classes and interfaces), as discussed in Chapter 42. The weaknesses of the first generation collection classes have been the primary motivation for introduction all the complexity of genericity (see Chapter 41 where we motivated generic classes by a study of the class Set). With use of type parameterized classes we can statically express List<Banana> and List<Pear> and hereby eliminate the risk of type errors at run time. In the following chapters we will - with the exception of Chapter 47 - limit ourselves to study type parameterized collections.