CSC236 Data Structures - Problem Set: Lists Part Two

Problem Set: Lists Part Two

What will be printed by the following?

   ABList<String> mylist = new ABList<>();
   mylist.add("tree");
   mylist.add("leaf");
   mylist.add("level");
   mylist.add("child");
   mylist.add(2, "parent");
   mylist.set(1, "height");
   mylist.add("balanced");
   mylist.remove(4);
   for (String str: mylist)
      System.out.println(str);

What will be printed by the following?

   LBList<String> mylist = new LBList<>();
   mylist.add("tree");
   mylist.add("leaf");
   mylist.add("level");
   mylist.add("child");
   mylist.add(2, "parent");
   mylist.set(1, "height");
   mylist.add("balanced");
   mylist.remove(4);
   Iterator myiter = mylist.iterator();
   while (myiter.hasNext())
      System.out.println(myiter.next());

What will be printed by the following?

   SortedABList<String> mylist = new SortedABList<>();
   mylist.add("tree");
   mylist.add("leaf");
   mylist.add("level");
   mylist.add("child");
   mylist.add("balanced");
   mylist.remove("child");
   mylist.add("parent");
   for (String str: mylist)
      System.out.println(str);

Show the fields elements and numElements in the Collection after the following:

   ArrayCollection<String> mylist = new ArrayCollection<>(8);
   mylist.add("tree");
   mylist.add("leaf");
   mylist.add("level");
   mylist.add("child");
   mylist.add("balanced");
   mylist.remove("leaf");
   mylist.add("parent");

Show numElements, head, and the nodes in the Collection after the following:

   LinkedCollection<String> mylist = new LinkedCollection<>();
   mylist.add("tree");
   mylist.add("leaf");
   mylist.add("level");
   mylist.add("child");
   mylist.add("balanced");
   mylist.remove("leaf");
   mylist.add("parent");

Show the fields elements and numElements in the list after the following:

   ABList<String> mylist = new ABList<>(10);
   mylist.add("tree");
   mylist.add("leaf");
   mylist.add("level");
   mylist.add(1, "child");
   mylist.add("balanced");
   mylist.set(2, "empty");
   mylist.remove("tree");
   mylist.add("parent");
   mylist.add(0, "root");
   mylist.remove(3);

Show numElements, front, rear, and the nodes in the list after the following:

   LBList<String> mylist = new LBList<>();
   mylist.add("tree");
   mylist.add("leaf");
   mylist.add("level");
   mylist.add(1, "child");
   mylist.add("balanced");
   mylist.set(2, "empty");
   mylist.remove("tree");
   mylist.add("parent");
   mylist.add(0, "root");
   mylist.remove(3);

Write a method in the LBList class called print which has no parms and returns void. The print method will print every element in the list. Do not use any of the other list methods in your code.
Add a method to the LBList class called addFront, which adds the given element at the beginning of the list:
```
     public void addFront(T element)
```
Do not use any of the other list methods in your code.
Suppose we change the way we define the SortedABList class so that duplicates are not allowed. Write a new add method that does not allow duplicates. If the method is called to add an element that is already in the list, the method should throw DuplicateElementException. You can assume that there is room for the new element in the array. Write your method without calling the find method.
Write a method public T smallest() for the ABList class that returns the smallest item in the list. Assume that T is Comparable. Do not use any of the other list methods in your code.
Write a method public T smallest() for the LBList class that returns the smallest item in the list. Assume that T is Comparable. Do not use any of the other list methods in your code.
Write a function (client code) public static ClassA smallest(ListInterface<ClassA>) that returns the smallest item in the list. Assume that T is Comparable.
Rewrite the function (client code) from the previous problem so that it uses a Comparator. Assume that ClassA has a method public static Comparator comp() that returns a Comparator. Use the Comparator to compare the items from the list.
Write a method public void removeAll(T target) for the ArrayCollection class that removes all occurences of target from the Collection. Do not use any of the other Collection methods in your code.
Write a function (client code) public static removeAll(ArrayCollection<String> collect, String target) that removes all occurences of the String target from the Collection.
1. Write a class Visit to keep track of a trip to a country. The fields include the name of the country, the continent, and the month and year of the visit. Make the class Comparable; the compareTo method should order the Visits by country name. Include a toString method, and an initializing constructor in your class.
2. Include an equals method that checks whether the continent and country name are the same.
3. Create a sorted list of Visits that uses the CompareTo written in the previous question, add four Visits to the list, and then write a loop to print all Visits.
4. Write a method to return a Comparator that orders Visits by year, by month within year, and by country within year. In what class do you include this method?
5. Create a sorted list of Visits that uses the Comparator written in the previous question, add four Visits to the list, and then write a loop to print all Visits.
6. Write a method to return a Comparator that orders Visits by continent, by country within continent, by year within continent, and by month within year. In what class do you include this method?
7. Create a sorted list of Visits that uses the Comparator written in the previous question, add four Visits to the list, and then write a loop to print all Visits.
1. Make the ArrayCollection class Iterable, create the Iterator using an inner class, and write the method to create the Iterator. What class will contain this code?
2. Using your Visit class from the previous problem, create an ArrayCollection of Visits, add four Visits to the Collection and use your iterator to print all the Visits. Don't use an enhanced for loop.
3. Rewrite your code from part 2 above to use an enhanced for.
4. Change the ArrayCollection so that it uses an anonymous inner class for the Iterator.
5. Does this require any change to your code in parts 2 and 3 above?
Repeat the previous problem using a LinkedCollection.
What is the best case and worst case complexity of each of the following methods from the ABList class? Assume that the list contains N elements Give the big O for each and explain what condition results in the best and worst case.
1. add(int index)
2. add(T element)
3. remove(int index)
4. remove(T element)
5. get(int index)
6. get(T element)
What is the best case and worst case complexity of each of the following methods from the LBList class? Assume that the list contains N elements Give the big O for each and explain what condition results in the best and worst case.
1. add(int index)
2. add(T element)
3. remove(int index)
4. remove(T element)
5. get(int index)
6. get(T element)