Unit 11 Sorted and Ordered Collectiions

Question 1

Lists:-

Fixed size versus dynamic:

Lists are _____ sized.

Answer 1

Lists are dynamically sized.

A list will grow and shrink as elements are added or removed.

Question 2

Lists:-

True or False

Ordering: Lists are unordered.

Answer 2

False

Lists are ordered. A list can be grown simply by tagging items on the end, in which case the elements will be in the order they were added. Alternatively an item can be inserted at a specified position

Question 3

Lists:

True or False

Indexing: Every element in a list has an integer index 0, 1, 2, 3, … to indicate its position.

Answer 3

True

The index provides a way of directly accessing the element. If an item is inserted in the middle of a list then all the elements beyond it will be moved up to make space for it, so their indexes will increase by 1. If an item is removed from a list, all the elements beyond it will have their indexes decreased by 1, so the gap closes up

Question 4

Lists:-

True or False

Duplicates: Like sets, which do not allow duplicates, a list can not contain any number of repeated elements.

Answer 4

False

Unlike sets, which do not allow duplicates, a list can contain any number of repeated elements.

Question 5

Lists:-

Is List a sub interface of Collection or Map?

Answer 5

Collection

So Lists already inherit the Collection protocol such as add(), addAll(), remove(), clear(), size(), contains() and isEmpty()

Question 6

Lists:-

Best practice is to use a variable declared as being of the interface type because that gives us flexibility to change our mind later about what implementation class we will use. What is a good general-purpose choice for a class that implements the List interface unless we know of a particular reason for using another list class?

Answer 6

an ArrayList

Question 7

Lists:-

Using the same style declaration as Set and Map, declare a list, with variable “hoverFrogList” to hold instances of class HoverFrog.

Answer 7

List < HoverFrog > hoverFrogList = new ArrayList < > ( );

Question 8

Lists:-

As with other collections you have seen, one of the simplest things you can do with a list is to get its size. The size of a list is simply the number of elements it contains. (Note that the elements of a list may include the value null and that any occurrences of null will be counted in the size.) Declare a list, with variable herbList to hold instances of String. You can create a local variable size, which holds primitive int values and print out “Size of newly created list is: “ followed by the size of the list.

Answer 8

List < String > herbList = new ArrayList < > ( );

int size =herbList.size();

System.out.println(“Size of newly created list is: “+size);

Question 9

Lists:-

Given

List < String > herbList = new ArrayList < > ( );

Add three string elements, Parsley, Sage and Rosemary to an initially empty set, making the size 3. The elements are stored in the order they are added, beginning with index 0.

Answer 9

herbList.add(“Parsley”);

herbList.add(“Sage”);

herbList.add(“Rosemary”);

• Size after adding elements:*
• 3*
• Parsley*
• Sage*
• Rosemary*

Question 10

Lists:-

If we run the following code, what is the size of the List?

List < String > herbList = new ArrayList < > ( );

herbList.add(“Parsley”);

herbList.add(“Sage”);

herbList.add(“Rosemary”);

herbList.add(“Rosemary”);

herbList.add(“Rosemary”);

int size =herbList.size();

System.out.println(“Size of this list is: “ +size);

Answer 10

• Size of this list is: 5*
• Parsley*
• Sage*
• Rosemary*
• Rosemary*
• Rosemary*

Unlike a set, a list can contain duplicate elements, as the code demonstrates. Five elements are added to the list, but three of those elements are duplicates. The size of the list is nevertheless 5.

Question 11

Lists:-

An element can be inserted at any index by using an add() message that takes two arguments(the first being the index in the list, the second being the object to add at that index).

Given;

List < String > sandwich = new ArrayList < > ( );

(a) Add the following elements “Bottom slice” and “Top slice”
(b) Now add the element “Filling” so it will appear in the list as the middle element

Answer 11

(a)

sandwich. add(“Bottom slice”);
sandwich. add(“Top slice”);
(b) sandwich.add(1, “Filling”);

The key point here is that when “Filling” is placed at index 1, “Top slice” (which was at index 1) is moved up to position 2. Bottom slice Filling Top slice Note that when we iterate through a list we start from index 0, which we would consider to be at the bottom of the list, and so, when printed out, the sandwich seems to be upside down.

Question 12

Lists:-

If a List has a size 3 “Bottom Slice”, “Filling” and “Top slice” and an element is added at index 4, what happens?

Also,what about trying to add at index -1 ?

Answer 12

An attempt to add this element beyond the end of the current list, will fail. An exception occurs: java.lang.IndexOutOfBoundsException

Attempting to add an element at-1 also generates an exception; A negative index is illegal.

Question 13

Lists:-

The intention is that the method will store six string elements in an instance of ArrayList and then print them out to produce the well-known phrase ‘To be or not to be’. The code that inserts the elements is missing at present and you are invited to supply it. Of course, you cannot perform the task simply by adding elements in this order to the end of the list. To get the strings into the necessary order, some elements will have to be inserted at specific indices.

List < String > phrase = new ArrayList < > ( );

phrase. add (“be”);
(a) continue to add the strings to the list in sequence “To”, “or”, “be”, “not” and finally “to”.
(b) now, using a for-each statement, print elements all on one line, separated by spaces.

Answer 13

List < String > phrase = new ArrayList < > ( );

phrase. add (“be”);
phrase. add(0,“To”);
phrase. add(“or”);
phrase. add(“be”);
phrase. add(3, “not”);
phrase. add(4, “to”);

for ( String eachElement : phrase)

{

System.out.print(eachElement +” “);

}

Question 14

Lists:-

Accessing the element at a specified position in a list is straightforward.

Using the code below, write more code to return “Parsley”

List < String > herbList = new ArrayList < > ( );

herbList.add(“Sorrel”);

herbList.add(“Tansy”);

herbList.add(“Parsley”);

herbList.add(“Rosemary”);

String selected = ____________________

Answer 14

herbList.get(2);

Question 15

Lists:-

Removing a specified element from a list is a little different from removing a specified element from a set because a list can have duplicate elements. So it is possible to remove an element from a list, reducing the size of the list by one, while other instances of the element remain. Does removing an element leave an empty space with a value “null” or instead will the elements beyond the one removed move down one position to close the gap?

Answer 15

The elements beyond the one removed, move down one position to close the gap.

Question 16

Lists:-

In the following uncompleted code, remove the third element, “Rosemary” and state the elements the System.out.print would read

List < String > herbList = new ArrayList ( );

herbList.add(“Sorrel”);

herbList.add(“Tansy”);

herbList.add(“Parsley”);

herbList.add(“Rosemary”);

herbList.add(“Rosemary”);

herbList.add(“Sage”);

String removed =_______________;

System.out.println(“The herbList contains the following elements in the following order: “);

for (String eachElement : herbList)

{

System.out.print(eachElement +” “);

}

Answer 16

herbList.remove(3);

would remove “Rosemary” from the list at index 3, and the list would then contain the following elements, in the following order: “Sorrel”, “Tansy”, “Parsley”, “Rosemary”, “Sage”

Question 17

Lists:-

Given;

List < String> herbList = new ArrayList ( );

herbList.add(“Oregano”);

herbList.add(“Oregano”);

herbList.add(“Basil”);

herbList.add(“Rosemary”);

herbList.add(“Rosemary”);

herbList.add(“Rosemary”);

This question is to understand and practice the methods indexOf() and lastIndexOf()

The completed code will return an int value for the variables position1, position2, position3 and position4.

Using the methods indexOf() or lastIndexOf() complete the code:-

int position1 = herbList._____(“Oregano”); //position1 needs to assign the value 0,

int position2 = herbList._____(“Sorrel”); //position2 to assign the value -1

int position3 = herbList._____(“Rosemary”); //position3 to assign the value 5

int position4 = herbList._____(“Parsley”); //position4 to assign the value -1

Answer 17

int position1 =herbList.indexOf(“Oregano”);

int position2 =herbList.indexOf(“Sorrel”);

int position3 = herbList.lastIndexOf(“Rosemary”);

int position4 =herbList.lastIndexOf(“Parsley”);

position2 and position4 can use indexOf() or lastIndexOf() message as both return -1 as Sorrel and Parsley are not in the herbList

Question 18

Lists:-

The element at a given position can be replaced by a new one. This is not the same as inserting an element, which increases the size of the list. When replacing an element the size stays the same and one of the original elements is overwritten by the new one.

Given;

List < String > herbList = new ArrayList < > ( );

herbList.add(“Parsley”);

herbList.add(“Sage”);

herbList.add(“Rosemary”);

herbList.add(“and”);

herbList.add(“Thyme”);

change the above code, herbList so it ends up holding the following elements, in the following order: “Are”, “you”, “going”, “to”, “Scarborough Fair”

Answer 18

herbList.set(0, “Are”);

herbList.set(1, “you”);

herbList.set(2, “going”);

herbList.set(3, “to”);

herbList.set(4, “ScarboroughFair”);

Question 19

Lists:-

Will this code compile and run?

for (int herbIndex =0; herbIndex < herbList.size( ); herbIndex++)

{

System.out.println(herbList.get(herbIndex) +” is at index “ +herbIndex);

}

Answer 19

A for-each loop will iterate through a list, in index order. This gives access to the elements but not to the index. If there was a reason to access the index, we could use an ordinary for loop and iterate using the index and the message get() This second type of iteration is possible only because lists have an integer index; it cannot be used with sets and maps.

Question 20

Lists:-

FROG to TOAD Riddle:

Print out the following, by completing the code:

FROG

FOG

LOG

LAG

LAD

LOAD

TOAD.

List < String > word = new ArrayList < > ( );

word. add(“F”);
word. add(“R”);
word. add(“O”);
word. add(“G”);

System.out.println(word);

//continue to change word from FROG to FOG, etc

Answer 20

word.remove(1);

System.out.println(word); //FOG word.set(0,”L”) System.out.println(word); //LOG word.set(1,”A”); System.out.println(word); //LAG word.set(2,”D”); System.out.println(word); //LAD word.add(1, “O”); System.out.println(word); //LOAD word.set(0,”T”); System.out.println(word);

Question 21

Arrays vs ArrayList:-

It is possible to start with a list and create an equivalent array – containing the same elements in the same order – by sending it the message toArray() .Is it also possible to start with an array and produce a list, using a static method of the utility class Arrays. (You met the utility class Arrays in Unit 9.)

Answer 21

Yes, and here is how it is done:

String [] sArray = {“The”, “cat”, “sat”, “on”, “the”, “mat”};

List < String > stringList = Arrays.asList(sArray);

Question 22

Array vs Collection:-

try to decide what sort of structure might be best to model the following practical problems. Would it be best to use a collection class? If so what interface would that class implement? Or would an array be all that is required?

In each case try to give the element or component type (using Java library classes) as well as a description.

(a) A programmer wants to store the names of the days of the week as strings and access them by day number, starting with Sunday as day zero.
(b) A secretary wants to store the telephone numbers of the members of a focus group and retrieve a person’s number given their name.
(c) A doctor wants to keep a record of the names of patients visited out of hours.
(d) A geographer wants to record the heights of mountains in metres and find the height of a mountain given its name.
(e) A classical scholar wants to record all the distinct Latin words that occur in the surviving works of Horace.
(f) A restaurant manager wants to store a menu of the currently available dishes. The list is to be numbered for the convenience of customers ordering food for home delivery. The particular offerings on the menu may alter from time to time as the restaurant tries out new dishes or discontinues ones that have not proved popular enough.
(g) A travel agent wants to be able to record the names of winter holiday resorts and the names of the hotels at each resort, and look up the hotels at a given resort.

Remember to say array or collection type and element type i.e., String, integer…

Answer 22

(a) Programmer (days of week) - This is a cast-iron case for an array. The requirements are very simple. The size is known in advance to be 7 and will never change. The contents, once set, will never need to be altered. All we will ever need to do is access the items by day number, handily starting from 0, so the obvious thing to do is make the day number the array index. The component type would be String. In fact,there is a better option in this case, an enum. These are not covered in M250, but if interested, read Oracle’s Java tutorials.
(b) Secretary (focus group) - We must be able to find the number given the name, so a collection class that implements the Map interface is needed here, with the name as the key and the number as the value. The element type would be < String, String >, i.e. both the keys and the values would be strings. (Telephone numbers cannot conveniently be stored as integers, because a leading zero is significant.)
(c) Doctor (patient visits) - This looks like a list of names without a fixed size and allowing duplicates, since a particular patient may have been visited several times and we want to record all the visits, so some names will be repeated. A collection class that implements the List interface is needed here. The element type would be String.
(d) Geographer (height of mountains) - Again it looks as though we need a collection class that implements the Map interface, with the name of the mountain as the key and the height as the value. A suitable element type would be < String, Integer >, i.e. the keys would be strings and the values would be integers.
(e) Scholar (Horace) - The scholar does not want to know how many times each word appears or anything like that; but simply to list the vocabulary used, and each word should appear only once. So a collection class that implements the Set interface would be suitable, because it does not allow duplicates. In fact, since the word list will need to be sorted, we could use the TreeSet class that we met briefly in Unit 10. The element type would be String.
(f) Restaurant (current dishes) - The menu items are numbered. Dishes may be added or taken off, so the size of the menu can vary. New dishes will probably get inserted amongst existing ones, and when dishes are removed that section of the menu will contract. From the description it sounds as though a collection class that implements the List interface would be best, with the type of the elements being String.
(g) Travel Agent (winter resorts) - This is more complex. To record the names of the hotels at any particular resort a set would be suitable. The number of hotels at that resort can vary from year to year, they are probably not recorded in any special order, and no hotel ought to appear more than once – if it did, that would be a mistake. All these considerations suggest using a class that implements the Set interface. We also note that the travel agent needs to be able to find the names of the hotels given the name of a resort. This suggests we also need a collection class that implements the Map interface, with the resort names as keys and the values being the sets of hotel names. So the element type would be < String, Set < String > >

Question 23

Element Types:-

Instead of using String or integer as the element type, a programmer might design classes such as TelephoneNumber, Patient, Mountain, Dish, Resort or Hotel to represent the objects in the collections.

• It allows the programmer to provide methods that are more suited to the class concerned - overridding;
• methods that are useful for the class of objects can be written;
• stricter type checking will be enforced when the code is compiled.

Give examples using the above bullet points of why writing a bespoke class is a better strategy

This question is more of a reminder than to test your knowledge.

Answer 23

• It allows the programmer to provide methods such as equals() and toString() that are suitable for the class concerned;
• methods that are useful for the class of objects can be provided (for example, a TelephoneNumber class might have a method getAreaCode( ));
• stricter type checking will be enforced when the code is compiled (eg, the compiler would not allow a String to be added to a collection whose element type is TelephoneNumber).

Question 24

Lists:-

Can a list be sorted?
As you have seen, lists are ordered collections. The elements are stored in the order given by their indexes, and if we iterate through a list, this is the order that is followed. However, the order does not have to reflect anything to do with the elements themselves. It is simply determined by where each element has been placed in the list. There is no general reason to expect that the elements in a list will automatically be in alphabetical or numerical order. For example, the elements in a list of herbs might have been added just in the order they occurred to us;

parsley, basil, thyme, camomile, fennel, …

This leads to the question: can lists be sorted?

Eg, can we put our list of herbs into alphabetical order?
basil, camomile, fennel, parsley, thyme, …

Answer 24

Yes

The class Arrays does not have a sort() method for lists, but, the utility class Collections also has many static methods for working with collections.

Reverse, swap, sort, shuffle, sublists, max and min…

Question 25

Lists:-

Reversing

To reverse a list, pass it as an argument.

Write the one line code to reverse the order of the elements in herbList from the variable Collections.

Answer 25

Collections.reverse(herbList);

Note this and several other methods are destructive – they modify the original collection. If you do not want this to happen you will need to create a copy of the collection and work with that instead.

Question 26

Lists:-

Sorting

If the elements in a list have a natural ordering (e.g. alphabetical order for strings or numerical order for numbers) they can be sorted according to this
ordering by passing the list as an argument.

Write the one line code to sort our herbList using the variable Collections.

Answer 26

Collections.sort(herbList);

will sort the contents of herbList alphabetically. If we sort a list of numbers, they will be put into ascending numerical order.

This method is destructive.

Question 27

Lists:-

Swapping

Two elements can be swapped by passing the list and the positions of the items concerned.

Write the one line code to exchange the third herbList element with the fifth element from the variable collections

Answer 27

Collections.swap(herbList, 2, 4);

remembering it is zero-based indexing so the first element is 0, second is 1… the above code will exchange the third element of herbList at index 2 with the fifth element at index 4.

If the method is called with either index out of range, an exception will be thrown.

This method is destructive.

Question 28

Lists:-

Shuffling

The elements in a list can be put into random order by passing the list as an argument

Write a one line code to shuffle the cardList in the variable Collections

Answer 28

Collections.shuffle(cardList);

would put a deck of cards into a random sequence.

This method is destructive.

Question 29

Lists:-

Locating sublists

Consider two lists named firstList and secondList. The list secondList may represent a sublist of firstList. That is, the elements in the second list may occur in the same order as some sequence of elements of the first list. To test if this is indeed the case there is a message which searches for occurrences of a given sublisst and returns the first stating position at which it is found, or -1 if it isn’t present.

firstList references [“chives”, “basil”, “thyme”, “chervil”, “sage”, “bay”, “thyme”, “chervil”, “coriander”]

and secondList [“thyme”, “chervil”]

Collections.indexOfSublist(firstList, secondList);
will return what index number?

Answer 29

Collections.indexOfSublist (firstList, secondList);
will return the index 2, the index at which the second list starts in the first list.

This method is non-destructive.

Question 30

Lists:-

Finding the maximum and minimum

The maximum or minimum element of a list can be found.

As with sorting, for this method to succeed, the elements must have a defined ordering, such as alphabetical or numerical.

Given scoreList references [20, 31, 32, 43, 54, 55, 66, 67, 98, 99]

executing the code;

String minScore = Collections.min(scoreList);

String maxScore = Collections.max(scoreList);

will min String and max String reference the smallest and largest actual values (20 and 99) in scoreList or their positions (0 and 9)

Answer 30

These methods return the actual maximum and minimum values

minScore is 20

maxScore 99

not their positions.

This method is non-destructive.

Question 31

Lists:-

Create empty List

declare a variable userData of type List of Integer and assign to it a suitable new instance of ArrayList

Answer 31

List < Integer > userData = new ArrayList < Integer > ( );

or

List < Integer > userData = new ArrayList < > ( );

Question 32

Lists:-

Given;

List < Integer > userData= new ArrayList < > ( );

write code so the user is repeatedly prompted, with request dialogue boxes, to enter a series of integers until the user signals the end of the series by pressing Cancel.

Note that anything typed into a dialogue box will be interpreted as a string. So each entry should be parsed to an integer and added to the list userData.

Answer 32

String stringDialog = “Input an integer. Press Cancel to end”;

String input = OUDialog.request(stringDialog);

while (input != null)

{

userData.add(Integer.parseInt(input));

input = OUDialog.request(stringDialog);

}

Question 33

Lists:-

Given;

List < Integer > userData = new ArrayList < > ( );

String prompt = “Input an integer. Press Cancel to end.”;

String input = OUDialog.request(prompt);

while (input != null)

{

userData.add(Integer.parseInt(input));

input = OUDialog.request(prompt);

}

Sort the list userData

Answer 33

Collections.sort(userData);

Question 34

Lists:-

Given an ArrayList userData which is sorted…

initialise an int variable total to 0.

Your code should then iterate through the userData list adding each element to total.

Once the numbers in the list have been totalled, the result should be cast to a float and divided by the size of the list to obtain an average, which should be assigned to a float variable avg.

We need to do the calculation this way because the average will not usually be a whole number. For example, if we want to cast x to a float, divide it by y and assign the result to z, it can be done like this:
float z = ( ( float ) x ) / y;

Answer 34

int total = 0;

for ( int eachElement : userData)

{

total = total + eachElement;

}

float avg = ( ( float ) total) / userData.size( );

Question 35

Lists:-

Given an ArrayList userData which is sorted, calculate the median, defined as follows:

If the number of elements is odd, the median is the middle one in the sorted list.

If the number of elements is even, the median is the average of the middle two elements.

For example;

The median of 1, 2, 2, 3, 5 is 2, the middle value.

The median of 1, 2, 2, 3, 4, 5 is 2.5, the average of the two middle values, 2 and 3.

Once you have calculated the median you should assign it to a float variable med.

The code for this calculation is somewhat tricky, and if you get stuck you can find out how it is done by looking in the file medianHint.txt - Unit 11

Answer 35

fload med;

int size = userData.size();

// if the list has a middle value - odd

if (userData.size() % 2 == 1)

{

int mid = (size -1) / 2;

med = userData.get(mid);

}

// if the list has no middle value - even - average of two middle items m1 and m2

else

{

int m1 =(size/2) -1;

int m2 = size /2;

med = ( (float) userData.get(m1) + userData.get(m2) ) /2;

}

Question 36

Lists:-

Given an ArrayList userData;

Find the maximum and minimum and assign them to int variables maxVal and minVal.

You can assume the list is sorted so the maximum and minimum will be the last and first elements of the list.

Answer 36

int maxVal = userData.get (size -1);

int minVal = userData.get (0);

Question 37

Lists:-

Classes that implement the Collection interface – including all classes that implement the Set and List interfaces – are expected to have two constructors: one that takes no argument, and one that takes any type of collection as an argument. Why?

The answer goes into depth, you are not expected to answer word for word, but get general understanding

Answer 37

The one that takes no argument, creates an empty collection; and one that takes any type of collection as an argument, creates a new collection with the same elements (a copy). This is to be used in bulk operations which destruct collections. There is another reason why we might use the second constructor: to create a collection of a different kind but with the same elements.
Why would we want to do this? Imagine we have a mailing list, stored as an instance of ArrayList perhaps, and we discover that it contains duplicates that should not be there. (This is a common problem in real-life mailing lists.) Do we have to go through and weed them out manually somehow?
There is a better way. We use the list to create a set. A set cannot contain duplicates, so they are all eliminated. Each name will now appear only once. But maybe there was a good reason why we used a list in the first place and a set is not what we want. No problem – we simply use the set to create a list. Now we are back where we started, but with all the duplicates automatically eliminated – and all with a single line of code. This is a good illustration of the extraordinary power and flexibility of the collection classes.

Question 38

Lists:-

Bulk Operations

Given lists with < Character >:

list1 = [a, b, r, a, c, a, d, a, b, r, a];

list2 = [d, a, b, c, h, i, c, k]

• make a copy of list1 and assign it to list3
• addAll characters from list2 to the new copied list3
• print out the resulting list.

Answer 38

List < Character > list3 = new ArrayList (list1);

list3.addAll(list2);

System.out.println(“This is list 3: “ +list3);

• This produces the following in the Display Pane:*
• This is list3: [a, b, r, a, c, a, d, a, b, r, a, d, a, b, c, h, i, c, k]*
• The effect of addAll() was to add the elements of list2 to the end of list1.*

Question 39

Lists:-

Bulk Operations

Given lists with < Character >:

list1 = [a, b, r, a, c, a, d, a, b, r, a];

list2 = [d, a, b, c, h, i, c, k]

Try out removeAll() - remove all the elements from list4 (which is a copy of list1) that are in list2. Print out the results stating “This is List 4: “

Answer 39

List < Character > list4 = new ArrayList < > (list1);

list4.removeAll(list2);

System.out.println(“This is list 4: “ +list4);

This would produce in the Display Pane:
This is list4: [r, r]
We can see that the effect of removeAll() is to remove from list4 any element that also appears in list2.

Question 40

Lists:-

Bulk Operations

Given lists with < Character >:

list1 = [a, b, r, a, c, a, d, a, b, r, a];

list2 = [d, a, b, c, h, i, c, k]

Using a copy of list1 called list5, retain all the items in list2. Print out the results “This is list 5:”

Answer 40

List < Character > list5 = new ArrayList < > (list1);

list5.retainAll(list2);

System.out.println(“This islist 5: “ =list5);

This would produce the following in the Display Pane:
This is list5: [a, b, a, c, a, d, a, b, a]

The effect of retainAll() is to retain in list5 only those elements that also appear in list2.

Question 41

Lists:-

Bulk Operations

Given lists with < Character >:

list1 = [a, b, r, a, c, a, d, a, b, r, a];

list2 = [d, a, b, c, h, i, c, k]

Create a new set which is list1 but without any duplicates, in alphabetical order. Print out the result.

Answer 41

Set < Character > set1 = new TreeSet < > (list1);

System.out.println (“This is set 1: “ +set1);

This would produce the following in the DisplayPane:
This is set 1: [a,b,c,d,r]

By creating a TreeSet with list1 as the argument to the TreeSet constructor we eliminate all duplicates and the elements are sorted alphabetically.

You might also have written:
System.out.println(new TreeSet < Character > (list1) );

Question 42

Comparable:-

The Comparable interface
Fortunately, it is easy to specify an ordering for a class. All we need to do is make the class implement the interface Comparable. Since this interface contains only a single method, compareTo(), this is not too hard.
The idea is that if Java wants to check the ordering of two objects x and y it uses the value of the message expression x.compareTo(y).
State if the result is possitive, negative or zero:

• _____ , Java will consider that x comes before y in the ordering;
• _____ , Java will consider that x comes after y in the ordering;
• _____ , Java will consider that x comes neither before nor after y – they occupy an equal position in the ordering.

Answer 42

negative

positive

zero

Question 43

Comparable:-

Give the answer as positive, negative or zero

• “chalk”.compareTo(“cheese”);
• “cheese”.compareTo(“cheek”);
• “101”.compareTo(“101”);

Answer 43

Negative - returns -4, showing “chalk” is before “cheese”, alphabetically speaking. (Do not worry about why we get -4 rather than any other negative number; -4 just happens to be the result of a particular calculation involving the characters making up the two strings.)

Positive - returns 4,showing “cheese” is after “cheek”.

Zero - returns 0,since “101” has an equal position to “101”.

Question 44

Comparable:-

Given:

public int compareTo (ComparableFrog anotherFrog)

{

return (this.getPosition() -anotherFrog.getPosition());

}

state positive, negative or zero if:

Frog one is yellow and on stone 4

Frog two is blue and on stone 4

Frog three is blue and on stone 2

frog2.compareTo(frog3);

Answer 44

Our Frog compareTo() is looking at position on stones and not colour. frog 2 is the x component and frog3 is the y component. The answer is positive when Java considers x (stone 4) comes after y (stone 2) in the ordering;

Question 45

Club Member Class:

• /***
• *Instances of ClubMember simulate members of a club*
• *and have the attributes firstName, lastName and age.*
• */*
• public class ClubMember*
• {*

With our new class called ClubMember. Declare two instance variables of type String called firstName and lastName respectively.

Then declare an instance variable of type int called age.

_________________________

Write a constructor for ClubMember that takes three arguments – two strings and an integer – and uses them to set firstName, lastName and age respectively.

public ClubMember(//write code here)

{

//write code here

}

_________________________

Write setter and getter methods:

public void setAge(int memberAge) {//write code here }

public int getAge() {//write code here }

public void setFirstName(String memberFirstName) { //write code here }

public String getFirstName() {//write code here }

public void setLastName(StringmemberLastName) {//write code here }

public String getLastName() {//write code here }

Answer 45

private String firstName;

private String lastName;

private int age;

__________________________

public ClubMember(String first, String last, int years)

{

firstName = first;

lastName = last;

age = years;

}

___________________________

public void setAge(int memberAge)

{

age = memberAge;

}

public int getAge()

{

return age;

}

public void setFirstName(String memberFirstName)

{

firstName = memberFirstName;

}

public String getFirstName()

{

return memberFirstName;

}

public void setLastName(StringmemberLastName)

{

lastName = memberLastName;

}

public String getLastName()

{

return lastName;

}

Question 46

Club Member Class:-

• /***
• *Instances of ClubMember simulate members of a club*
• *and have the attributes firstName, lastName and age.*
• */*

public class ClubMember

{

Alter ClubMember so that the class is declared as implementing Comparable<clubmember>.</clubmember>

Make sure you include the type <clubmember> that the comparison will involve.</clubmember>

Answer 46

public class ClubMember implements Comparable < ClubMember >

Question 47

Club Member Class:-

• remembering when Frogs inplement the Comparable interface*
• public int compareTo(ComparableFrog anotherFrog)*
• {*
• return (this.getPosition() -anotherFrog.getPosition());*
• }*

Write a compareTo() instance method for ClubMember that defines an ordering based on age.

public class ClubMember implements Comparable < ClubMember >

{

//write compareTo() header here

//write compareTo() method body here { }

}

If these statements were executed, write down the return statements from a display pane (values can easily be given since the results will be integers and not strings)

ClubMember x = new ClubMember (“Joe”,”Green”,27);

ClubMember y = new ClubMember (“Maria”, “Brown”, 21);

x. compareTo(y);
y. compareTo(x);
x. compareTo(x);

Answer 47

public int compareTo(ClubMember anotherMember)

{

return (this.getAge() - anotherMember.getAge());

}

The results in the DisplayPane would be:
6

• -6*
• 0*

Question 48

Club member Class:-

Comparing Strings

Luckily there is a method in the String class that will produce exactly the result we need to return. This method is called compareTo(). The expression
**aString.compareTo(bString)**
will evaluate to a negative, zero or positive result depending on whether aString is alphabetically before, the same as, or after bString. So all we need to do is compare the last names using this method and return the result.

Given the compareTo() method to compare age

public int compareTo(ClubMember anotherMember)

{

return (this.getAge() - anotherMember.getAge());

}

and the getter message for lastName is

public String getLastName()

{

return lastName;

}

write a compareTo() method to compare members last names

Answer 48

public int compareTo(ClubMember anotherMember)

{

return this.getLastName().compareTo(anotherMember.getLastName());

}

Question 49

Sorted and Unsorted Collections:-

Wouldn’t it be nice if we had a kind of collection that automatically kept all its elements sorted, and whenever we added a new element it was put in the right position according to its natural ordering without us having to do anything? Ready-sorted collections, you might say.

Do these exist? and if so, can you name two interfaces which are subinterfaces of collections?

Answer 49

As you will have guessed, such a kind of collection does exist. It is called a sorted collection. You have already met one kind of sorted collection briefly in Unit10: the TreeSet. You may recall that when we stored our herbs in a TreeSet rather than a HashSet they magically became sorted into alphabetical order.

Sorted collections implement one of two interfaces: SortedSet, which is a subinterface of Set; and SortedMap, which is a subinterface of Map.

TreeSet implements SortedSet and is like HashSet except that its elements are always arranged in their natural order. Similarly there is a collection class TreeMap, which implements SortedMap and is like a HashMap except that its entries are always arranged according to the natural order of the keys.

Question 50

Sorted Collections:-

Given the classes we have written so far, which of the following types of ordered set do you think are legal?

1. TreeSet < HoverFrog >
2. TreeSet < ComparableFrog >
3. TreeSet < Integer >
4. TreeSet < String >
5. TreeSet < int >

Answer 50

The contents of aTreeSet are kept sorted by natural order, so the elements must have a natural order defined on them. This rules out TreeSet < HowverFrog >, because HoverFrog (as it stands) does not implement Comparable and so instances of HoverFrog cannot be sorted.

TreeSet < ComparableFrog > is fine, since ComparableFrog implements Comparable.

Integer and String likewise have a natural order, so TreeSet < Integer > and TreeSet < String > are also fine.

TreeSet < int > is illegal because collections can only contain objects, not primitive data types. If we use a TreeSet of Integer, auto-boxing would nevertheless make it seem as though int values could be added to it.

Question 51

Sorted Collections:-

Why is there no interface SortedList?

Answer 51

A SortedList would be a contradiction in terms. A sorted collection will at all times arrange elements in their natural order, but a list is an indexed collection, and that implies an element can be stored at a chosen index.

These are contradictory requirements. If we tried to insert a new element at a particular index (12 say)in a sorted collection, the collection would have to ensure that the element should occupy its correct position according to the natural ordering (not necessarily index 12).

Question 52

Sorrted Collection:-

Sets cannot contain duplicate elements and maps cannot contain duplicate keys. What does duplicate mean precisely - Do these two methods confirm if an object has been duplicated?

if x.compareTo(y) returns zero – then x and y are considered duplicates (used with comparable interface - sorted collections) &

x.equals(y) returns true, then x and y are duplicates (sets and maps)

Answer 52

x.equals(y) categorically tells us if x is the same object as y. You might very reasonably imagine that the same would apply to sorted collections, but it does not.

In sorted collections, x and y might actually reference different objects. For example, recall that ComparableFrog implementsComparable<comparablefrog> using frog position. Therefore, if two distinct instances of ComparableFrog happen to be on the same stone, to a sorted collection they appear to be one and the same. </comparablefrog>

So sorted sets treat two objects as the same if the result of comparesTo() is zero.

Question 53

Sorted Collections:-

What is the difference between == and equals()?

Answer 53

For object references x and y, x == y is true only if they both reference exactly the same object, i.e. they both point to the same address in memory.

x.equals(y) may be testing a weaker condition – not whether they are the same object, but whatever the class defines equals to mean – assuming the class overrides the inherited equals() method. When the equals() method is overridden it will usually compare all or some of the compared objects state.

For example, aString.equals(bString) will be true if both strings contain the same characters in the same order, even if they are actually different objects.

It makes sense for the String class equals() method to work in this way. Imagine if we wanted to compare a password string with a stored password when a user logged in. The two strings would be different objects, but we would want them to be considered equal if the user had typed in the right sequence of characters. If the user had to supply the identical object they would be unable to log in.

unsorted collections, such as sets and maps, use equals() as the basis for deciding whether two elements duplicate one another. So if we try to add a new element to an instance of HashSet, or a new key–value pair to an instance of HashMap, it will be equals() that is used to detect whether the element or the key is already present. equals() is also used in testing methods, such as contains().

Question 54

Sorted Collections:-

Re-writing the equals() method

public boolean equals(Object obj)

{

return this.getLength() == obj.getLength();

}

This will not work. Can you see why?

Answer 54

The reason is that the argument obj is declared as Object obj in the method header. Therefore we can send it only messages from the protocol of Object, and this does not include any such message as getLength().

We can get round this with a cast.

Question 55

Sorted Collections:-

public boolean equals(Object obj)

{

//write your code here;

return this.getLength() == row.getLength();

}

Above we declare a RowOfStars variable, say row, and then cast the argument obj so that the compiler will allow its value to be held by a variable of typeRowOfStars. Write the line of code showing casting.

Answer 55

public boolean equals(Object obj)

{

RowOfStars row = (RowOfStars) obj;

return this.getLength() == row.getLength();

}

we have used casting because the code would have just been the return line stating:

return this.getLength() == obj.getLength();

with obj being a variable of Object class, it doesn’t have a method getLength().

The return now works fine, since getLength() is in the protocol of RowOfStars

Question 56

Sorted Collections:-

public boolean equals(Object obj)

{

RowOfStars row = (RowOfStars) obj;

return this.getLength() == row.getLength();

}

• RowOfStars rs1 = new RowOfStars(7);*
• RowOfStars rs2 = new RowOfStars(7);*
• RowOfStars rs3 = new RowOfStars(11);*

given the above code, answer true or false:

• rs1.equals(rs2);
• rs1.equals(rs3);

Answer 56

• rs1.equals(rs2) returns true (the states of the two objects are the same)
• but rs1.equals(rs3) returns false (the states are different).

Question 57

Sorted Collections:-

• Where is the method hashcode() inherited from?
• why is it necessary to override the hashcode method?

Answer 57

• the method hashCode() is inherited from Object.

The message replies with an int value called the hash code and this value determines which bucket the object should be put in.

• Two objects could be equal in terms of state but have different hash codes. Whenever two objects are equal they also need the same hash code so Java will look/add to the same bucket for both objects.

if x.equals(y) is true, then x.hashCode() should return the same number as y.hashCode() to ensure this you need to override hashcode() method in your subclass of Object.

Question 58

Sorted Collections:

Object identity:-

tested with _____. If x and y are references and _____ is true, this means both x and y reference exactly the same area in memory. This is always the case: we cannot redefine _____.

answer in the blanks

1. ==
2. x.equals(y)
3. x.compareTo(y)

Answer 58

Answer is:

1. ==

Question 59

Sorted Collections:-

Equality in a natural ordering:-

If _____ is zero, x and y will be treated as equal in sorted collections.

answer in the blanks

1. ==
2. x.equals(y)
3. x.compareTo(y)

Answer 59

Answer is:-

3. x.compareTo(y)

If we want, we can define compareTo() and equals() completely separately, but it is not a very good idea because then two objects could be treated as the same in one kind of collection yet different in another. So we ought to make sure that if we define a compareTo() method for a class it is consistent with ourequals() method.

Question 60

Sorted Collections:-

Equality of state or content:-

Usually, if _____ is true, this means a and b have the same state, although we have the freedom to make it mean whatever we like by an override. However, when we override this method, we should override hashcode() method too.

answer in the blanks

1. ==
2. x.equals(y)
3. x.compareTo(y)

Answer 60

2. x.equals(y)

The version of equals() inherited from Object is no different in its effect from ==. But class designers can override equals() to suit their own purposes.

However – as we have seen – whenever we override equals() we had better override hashCode() as well. Otherwise we will get the version of hashCode() from Object – that version will yield a different hash code for every object, and then our class will not work properly with some collections. If x.equals(y) is true, x and y should return the same hash-code value.

Question 61

Sorted and Ordered Collections:-

Only one word, either Set, Map or List complies to the following?

• A _____ is a variable-sized collection that is ordered, has an integer index, and permits duplicate elements.
• _____ is a subinterface of Collection and so it extends the protocol of Collection, adding additional abstract methods.
• The protocol of _____ includes methods for adding elements, inserting elements, accessing elements by index, removing elements, and overwriting elements already present. It also includes methods for testing the _____ and searching for a given object.
• If elements are inserted in or removed from a _____, other items are moved up or down to make room or close the gap as necessary.

Answer 61

Answer - list

A list is a variable-sized collection that is ordered, has an integer index, and permits duplicate elements.
List is a subinterface of Collection and so it extends the protocol of Collection, adding additional abstract methods.
The protocol of List includes methods for adding elements, inserting elements, accessing elements by index, removing elements, and overwriting elements already present. It also includes methods for testing the list and searching for a given object.
If elements are inserted in or removed from a list, other items are moved up or down to make room or close the gap as necessary.

Question 62

Sorted and Ordered Collections:-

_____ is a good general-purpose implementation of List.

Answer 62

ArrayList is a good general-purpose implementation of List.

Question 63

Sorted and Ordered Collections:-

1. We may iterate through a list using a _____ loop, which will access the elements in index order.
2. We can also iterate using a ___ loop to access each element in turn by its index.

when do we use a for loop and when to use a for-each loop

Answer 63

1. We may iterate through a list using a for-each loop, which will access the elements in index order.
2. We can also iterate using a for loop to access each element in turn by its index.

Question 64

Sorted and Ordered Collections:-

Can we define a natural order of our own for a class?

Answer 64

Yes, by implementing the Comparable interface.

Question 65

Sorted and Ordered Collections:-

Which utility class provides a wide range of static methods for working with collections, including ones to do tasks such as reversing, sorting and shuffling lists, swapping elements in a list, locating maximum and minimum elements, and searching for substrings. Many of these methods are destructive.

Answer 65

Collections

Question 66

Sorted and Ordered Collections:-

True or false

A collection may be passed as the argument for the constructor of a different type of collection. Creating a set from a list in this way is a useful idiom for eliminating duplicates.

Answer 66

True

Question 67

Sorted and Ordered Collections:-

True or False

Classes that implement the List interface (for example, ArrayList) support a number of bulk operations similar to those for sets.

Answer 67

True

Question 68

Sorted and Ordered Collections:-

There are sorted collections whose elements or entries are automatically kept sorted, so they are always in their natural order. Sorted collections implement the SortedSet and SortedMap interfaces. Sorted collections cannot contain two elements that have equal order.

True or False:- Only objects of classes that implement the Comparable interface may be stored in such collections.

Answer 68

True

Question 69

Sorted and Ordered Collections:-

Is it True?

Lists are not sorted collections, but they can be sorted by the sort() method of the Collections class, so long as the elements in the list implement the Comparable interface.

Answer 69

Yes, it is true

Question 70

Sorted and Ordered Collections

Fill in the blanks:

As well as object identity, tested with ==, there is another from of equality, which is tested using __1___. In Object the two forms have exactly the same effect. However a class designer can override the __2___ inherited from Object so that it tests for equal state, or some other similarity.

Answer 70

1. equals(Object) and
2. equals()

Question 71

Sorted and Ordered Collections:-

Fill in the blanks:

Whenever equals() is overridden, __1___ must also be overridden so that equal objects return the same __2___. Otherwise, objects will not be stored properly in collections that implement the Set and Map interfaces (or subinterfaces).

Answer 71

1. hashcode() and
2. hash code

Question 72

Sorted and Ordered Collections:-

Why, if a class implements Comparable, its equals(), hashCode() and compareTo() methods should be consistent with one another?

Answer 72

So that objects that have equal state also occupy the same point in the natural ordering. Objects of such a class can be stored in any kind of Java collection.