CSC/ECE 517 Fall 2012/ch1 1w30 rp

2012-09-15T02:06:26Z

Psingha: Created page with "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 th..."

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: ==

[http://en.wikipedia.org/wiki/Collection_(abstract_data_type)#Collection Wikipedia]<br\>
[http://en.wikipedia.org/wiki/Abstract_data_type #Abstract Data Type Wikipedia]<br\>
[http://docs.oracle.com/javase/6/docs/api/java/util/Collection.html#Java Collections Oracle]<br\>
[http://www.digilife.be/quickreferences/PT/Java%20Collections%20Framework.pdf#Java Collection Digilife]<br\>
[http://www.javapassion.com/javase/javacollections.pdf#Java Collections Java Passion]

CSC/ECE 517 Fall 2012

2012-09-15T01:19:57Z

Psingha:

*[[CSC/ECE 517 Fall 2012/ch1 n xx]]
*[[CSC/ECE 517 Fall 2012/ch1 1w1 rk]]
*[[CSC/ECE 517 Fall 2012/ch1 1w20 pp]]
*[[CSC/ECE 517 Fall 2012/ch1 1w5 su]]
*[[CSC/ECE 517 Fall 2012/ch1 1w6 pp]]
*[[CSC/ECE 517 Fall 2012/ch1 1w4 aj]]
*[[CSC/ECE 517 Fall 2012/ch1 1w7 am]]
*[[CSC/ECE 517 Fall 2012/ch1 1w8 aa]]
*[[CSC/ECE 517 Fall 2012/ch1 1w9 av]]
*[[CSC/ECE 517 Fall 2012/ch1 1w10 pk]]
*[[CSC/ECE 517 Fall 2012/ch1 1w11 ap]]
*[[CSC/ECE 517 Fall 2012/ch1a 1w12 mv]]
*[[CSC/ECE 517 Fall 2012/ch1 1w14 gv]]
*[[CSC/ECE 517 Fall 2012/ch1 1w17 ir]]
*[[CSC/ECE 517 Fall 2012/ch1 1w18 as]]
*[[CSC/ECE 517 Fall 2012/ch1 1w22 an]]
*[[CSC/ECE 517 Fall 2012/ch1 1w21 aa]]
*[[CSC/ECE 517 Fall 2012/ch1 1w21 wi]]
*[[CSC/ECE 517 Fall 2012/ch1 1w31 sa]]
*[[CSC/ECE 517 Fall 2012/ch1a 1w16 br]]
*[[CSC/ECE 517 Fall 2012/ch1a 1w23 as]]
*[[CSC/ECE 517 Fall 2012/ch1 1w24 nr]]
*[[CSC/ECE 517 Fall 2012/ch1 1w15 rt]]
*[[CSC/ECE 517 Fall 2012/ch1 1w3 pl]]
*[[CSC/ECE 517 Fall 2012/ch1 1w32 cm]]
*[[CSC/ECE 517 Fall 2012/ch1 1w27 ms]]
*[[CSC/ECE 517 Fall 2012/ch1 1w29 sa]]
*[[CSC/ECE 517 Fall 2012/ch1 1w33 op]]
*[[CSC/ECE 517 Fall 2012/ch1 1w19 sa]]
*[[CSC/ECE 517 Fall 2012/ch1 1w34 vd]]
*[[CSC/ECE 517 Fall 2012/ch1 1w35 sa]]
*[[CSC/ECE 517 Fall 2012/ch1 1w30 rp]]

Expertiza_Wiki - User contributions [en]

CSC/ECE 517 Fall 2012/ch1 1w30 rp

CSC/ECE 517 Fall 2012