Chapter 21: Collections

Question 1

What is the collections API?

Answer 1

A group of classes and interfaces designed to store collections in various different ways. Allows elements to be added without worrying about memory allocation

Question 2

What is the collection interface

Answer 2

Specifies the instance methods needed to support a collection: Size, Add, Remove, addAll, removeAll, retainAll, contains, containsAll, iterator

Question 3

What constructor methods must a class implementing the collection interface provide?

Answer 3

One with no method argument builds empty collection.

One that takes existing collection and builds a new one containing the same elements

Question 4

What is a list? What interface supports it?

Answer 4

A type of collection that allows duplicate elements, store in an ordering, each has a list index

List interface specifies instance methods to support list collection: size, add, get, set. Generic interface with type parameter of object to be stored

Question 5

What is the iterator method specified in the list interface?

Answer 5

Returns an object that implements Iterator, supporting iteration of the elements in the list in ascending order of their index

Question 6

What is an Array List?

Answer 6

Part of the collections framework. Implements the list interface. ArrayList implements List

Question 7

What is a linked list?

Answer 7

Another implementation of the list interface using a doubly linked list. A generic class

Question 8

What is a map? What is its interface?

Answer 8

Type of collection. Connects a key of any type to an element. Two keys can map to the same value.

Map interface specifies instance methods to support a map. Generic with types for keys and elements.
Put: takes key and element and adds to map. Old value replaced my new
Get: takes key and returns a value
Values: returns a collection of values. Iterator can support iterating through values depending on type
Keyset: returns set of keys in map

Question 9

What is a Tree Map?

Answer 9

An implementation of map, uses ordered binary trees.

Values() gives collection, Iterator() of this gives iterator that supports iteration over values of map in key order.

Question 10

What is a HashMap?

Answer 10

Part of collections framework. Implements map using a hash table. Each key must have appropriate implementation of haschode. Values() gives collection of values. Iteration in no particular order.

Question 11

When do we use HashMap instead of TreeMap?

Answer 11

Don’t desire values in key order

Little or no hash code clashing. HashMap= constant time. TreeMap= logarithmic time.

Question 12

Describe Sets and set interface

Answer 12

Kind of collection. Adding an already present element has no effect. Order added isn’t preserved.

Set interface specifies instance methods needed to support a set collection: size, add, contains

Iterator iterates over elements depending on the kind of set. May be an arbitrary order.

Question 13

What is an iterator?

Answer 13

The instance method Iterator() returns an object that implements Iterator.

Question 14

What is a TreeSet?

Answer 14

Part of collections framework. Implements set collection and interface. Uses an ordered binary tree so elements are ordered.

Iterator supports the iterator of elements in the order they appear in the tree, from left to right. We get the natural ordering of the elements.

Question 15

When would we use HashSet instead of TreeSet?

Answer 15

When we don’t desire values in a specific order

Question 16

What is a hashset?

Answer 16

A generic class that implements set interface. Uses a hash table with hash codes obtained from hashcode()

Question 17

What class methods are provided by collections?

Answer 17

Ones that perform manipulations of collections e.g. sort

Question 18

What is the iterator interface?

Answer 18

Specifies instance methods for accessing elements in a collection one by one:
hasNext
Next

Question 19

What is tree sort

Answer 19

Algorithm for sorting. Items from a list are inserted into ordered binary tree. Tree scanned from left to right. Can be achieved using an instance of TreeSet if data has no duplicates

Question 20

What is a hash table?

Answer 20

A method for storing data so that it can be retrieved quickly.
Places refrences to items in an array where the index is based on the has code provided by each item. Equivalent items have the same code.

Take hash code, Mod by size of array. Place item at that index.