CSC/ECE 517 Fall 2012/ch1 1w30 rp

A Collection is a data structure representing a group of data items sharing common properties (or state) and behaviour. Generally data items represents object of same type and their behaviour is governed by the set of operation that can be performed on them. An Array also represents a group of related objects but Array are not considered as collection because an array can only hold a fixed number of items however size of collection is variable, or dynamic. In sum, a collection can be viewed as a single object containing multiple numbers of elements. Few collection types include trees, sets, ArrayList, Dictionary etc.

In order to create, manage and manipulate collection, we have collection framework which depicts representation and manipulation of collection elements independent of their implementation details. It defines application programming interfaces (API’s) consisting of classes and interfaces for manipulating data in collection.

Advantages of collection framework

a) Performance Improvement: Framework includes highly efficient implementation of data structures and algorithms to manipulate them.<br\> b) Increase in programmer’s productivity: Framework provides ready to use data structures obviating coding of underlying data structure by programmer.<br\> c) Unrelated API interoperability: It provides a common language through which collection can be passed back and forth.<br\> d) Ease in designing, implementing and learning APIs by providing generic collections APIs. <br\>

Elements of collection framework

a) Collection Interfaces: These are the basis of the framework and represents different type of collection such as List, Set, Queue, and SortedSet. <br\> b) Implementations: Classes having implementation of Collection interface, partial implementation of a particular interface in order to facilitate custom behaviour like adding constraints on operations of a particular collection, synchronize data of collection on concurrent use of framework etc.<br\> c) Algorithms: These are static methods providing support of useful functions on collection like sorting, searching, checking equality, manipulating elements etc.<br\>

Collection Interfaces and Implementations

As mentioned earlier, collection framework has interfaces of collection. In Java programming language, there are two category of interfaces:<br\> a) Interfaces extending ‘Collection’ interface: The root interface in the collection framework hierarchy is ‘Interface Collection’ and there are several interfaces which extend this interface like: Set, List, Sorted Set, Queue, Deque etc.<br\> b) Interfaces supporting collection-view operations: These interfaces do not extend ‘Collection’ interface however they are used to viewing the group of elements instead of storing a collection. In other terms, we can say that these interfaces represent relation among elements instead of actual collection.<br\>

In the following section three major collection interfaces and there implementations are discussed in detail. Different languages provide support for different collections for instance in ruby arrays and hashes are termed as collections while java provide a larger base like maps and lists

1. Set Interface: It is a collection which extends the Collection interface and contains elements like the sets in mathematics but elements here are distinct, for example, pages of a book. There are several restrictions on the method like add() method cannot add similar objects, moreover equals() can compare 2 set interfaces even if they have separate implementations. However in order to achieve such comparison implementation of interfaces need to override the hashcode() method so that the hashes are well interspersed and minimal collision occurs. It is relevant to note that the value returned by hashcode() is same for 2 sets thus making them equal.

Implementations of Set Interface

a. Hash Set- It extends set interface and is implemented using a hash table. The result of the Hash Set is not guaranteed to be sorted. The runtime and space complexity of the same is linear and constant. There is an issue with the load factor and the bucket size of the hash set that is if the amount of load factor is very less the hash Set will iterate over the whole bucket unnecessarily.

b. Tree Set- It extends set interface and is implemented using a tree structure. The result of the Tree Set is sorted unlike Hashset. The runtime complexity is logarithmic due to its dynamic nature. The TreeSet resolves the problem of load factor and bucket size as the tree is always balanced. Though TreeSet seems more efficient but HashSet are more in use.

c. LinkedHashSet- It extends the HashSet implementation. The underlying data structure is a doubly link list. It allows viewing the elements in the order they were inserted that is, in an ordered fashion.

2. The List Interface: It is an ordered collection of elements which extends Collection interface where duplicate elements are allowed to enter. The idea here is to allow iteration over the collection in a position oriented manner. It allows search, add, delete on the collection from the index required.

Implementations of List Interface

The choice of implementation here depends on the need. <br\> a. ArrayList- It implements the List Interface and manages data in the form of a dynamic array. It offers constant time positional access. It works up to the mark, if you wish to randomly access the elements and only manipulate elements at the end.

b. LinkedList- It implements List Interface and manages data in the form of a linkedlist. It should be used if you wish to access elements sequentially and manipulate data from the middle of the list.

3. The Map Interface: The Map interface is different from other interfaces for it doesn’t extend the Collection Interface. It has its own hierarchy. It maintains data in the form of key-value pairs, where key has to be unique, though it does allow null key values. It is also called as associative array. The Map interface implementations also require to override the hashcode() and equals() method so that equality of 2 maps can be substantiated.

Implementations of Map Interface

a. HashMap- They are best to use if the problem at hand needs to insert, delete or locate elements in a map. The result of these maps is unsorted. The underlying data structure is a hash table.

b. TreeMap- Theyare best to use if the problem at hand needs to traverse the map in a sorted manner. It is required that a TreeMap implements the comparable interface and overrides the compareTo() method so that it returns an int stating the status of the compare operation.

Algorithm in Collection Framework

Collection Framework provides support for various algorithms to carry out basic operations with collections. Various collections described above have support for all the basic methods inherited from Collection class which are -add(), addall(), contains(), containsall(), hashcode(). Besides these they provide support for the following algorithms:

1. Sort: Collection Framework provide support for sorting a List using sort( ) methods in the Collections class. For sorting all items of a collection, its element must be comparable to each other.<br\> 2. Searching: Collection Framework provides support for searching a List as well as finding the minimum and maximum values within a Collection. Different ways to search a collection includes searching an unsorted list using contains ( ) method of List collection or searching a sorted list using binarySearch( ) method as that is more fast in comparison to contains( ) method.<br\>

Apart from searching a particular element within a List, min( ) and max( ) methods of Collections can be used to find minimum and maximum element in an unsorted collection. Note that if the object in the collection does not implement Comparable then you must provide a Comparator which will serve as comparison operator among the elements of a collection.<br\> 3. Reorganising: Methods like reverse and shuffle alter the index of elements in the collection.

References:

Wikipedia<br\> #Abstract Data Type Wikipedia<br\> Collections Oracle<br\> Collection Digilife<br\> Collections Java Passion