Which of the items listed below, if any, are not assumptions DJW make about List

Question

Which of the items listed below, if any, are not assumptions DJW make about List ADTs:

1) lists are unbounded

2) duplicate elements on a given list are allowed

3) null elements are not allowed

4) lists of Strings are immutable

If a list object, based on one of the DJW's array-based List ADT classes, is instantiated with an original capacity of 12 and is subsequently populated with the names of the 30 highest-grossing films of all time, what is the minimum number of times the enlarge( ) method has been executed for this list?

In the preceding problem, if there have been no removals, what is the total capacity of the underlying array when the list includes the names of all 30 movies?

What value is returned by the size( ) method for a list object instantiated from one of the DJW List ADT classes, if just after instantiation, the following operations were performed immediately prior to calling size( )?

list.add(17)
list.add(23)
list.add(29)
list.add(37)
list.add(23)
list.get(29)
list.add(17)
list.add(19)
list.remove(23)

When inserting a new item into a linked list at the end, or tail, how many of the nodes already on the linked list will have their next pointer updated? Note that DJW use the instance variable link as the next pointer in their linked list node object.

When inserting a new item into a linked list at the beginning, or head, how many of the nodes already on the linked list will have their next pointer updated?

Explanation / Answer

NOTE : From next time onwards, don't forget to post the referenced book and chapters. Not everyone has the same book as yours.

a.
The assumptions that DJW make are
1. Lists are unbounded.
2. Duplicate elements are allowed in the list
3. List doesn't allow null elements. As a general precondition for all list methods, null elements cannot be used as arguments.
So, clearly, 4th one, "List of Strings are immutable" is not an assumption DJW made about List ADTs

b. Everytime the list is full and a element is to be inserted, the size of the underlying array is increased by "original size" amount. If we go by this procedure, we will have to make 2 calls to enlarge(). If the original capacity is 12, then on insertion of 13th element, we enlarge the size to 24, then on insertion of 25th element, we increment the size of the array to 36.

c. So, from above, we can clearly see that total capacity of the underlying array is 36 when there are no removals.

d. Since you are adding 7 elements and removing one, the final size will be 23. Although, 23 has more than one copy. The remove method removes only one of them.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.