CSC 212 Implementing and Using Lists

The goal of this assignment is to implement and use the ADT List. The assignment is divided into two parts. In the first part, you will implement the ADT List with an augmented set of operations using linked and array representations. In the second part, you will write methods that use these implementations:

1. Given the following specification of the ADT List, implement this data structure us- ing both array and linked representations. You should write two classes ArrayList and LinkedList that both implement the interface List . You may use code from the lecture notes for the methods discussed in class.

Specification of ADT List

• empty (boolean flag): requires: none. input: none. results: if the number of elements in L is zero, then flag is set to true otherwise false. output: flag.
• full (boolean flag): requires: none. input: none. results: if the number of elements in L has reached the maximum then flag is set to true otherwise false. output: flag.
• findFirst ( ): requires: list L is not empty. input: none. results: first element set as the current element. output: none.
• findNext ( ): requires: list L is not empty. Current is not last. input: none. results: element following the current element is made current. output: none.
• last (boolean flag): requires: L is not empty. input: none. results: if the last element is the current element then flag is set to true otherwise false. output: flag.
• retrieve (Type e): requires: list L is not empty. input: none. results: current element is copied into e. output: element e.
• update (Type e): requires: list L is not empty. input: e. results: the element e is copied into the current node. output: none.
• insert (Type e): requires: list L is not full. input: e. results: a new node containing element e is created and inserted after the current element in the list. The new element e is made the current element. If the list is empty e is also made the head element. output: none.
• remove ( ): requires: list L is not empty. input: none. results: the current element is removed. If L is empty, current will point to null. If the next element exists, it is made current, else the first element is made current. output: none.

New methods:

• insertBefore(T e): requires: list L is not full. input: e. results: a new node containing element e is created and inserted before the current element in the list. The new element e is made the current element. If the list is empty e is inserted at the beginning and also made the head element. output: none

2. Write a class called ListUtils having the following static methods:

(a) public static List< Integer> insertInOrder(List< Integer> l, Integer a) : A static method that inserts an Integer a into the list of integers l . The input list l is assumed to be in increasing order and must remain that way after inserting a .

public static List< Integer> readValues(String fileName) : A static method that reads integer values from a file fileName and inserts them into a list in increasing order. The method should return the created list. You may choose ArrayList or LinkedList to build your List.

(c) public static List< Integer> merge(List< Integer> l1, List< Integer> l2) : A static method that merges the two lists l1 and l2 , which are given in increasing order, and returns the newly created list which must also be in increasing order.