ADT ordered list

Recall that when we think about an ADT, we think about both the external and internal views. The external view includes the "conceptual picture" and the set of "conceptual operations". The conceptual picture of a List is something like this:

      item 0
      item 1
      item 2
      . . .
      item n

and one reasonable set of operations is:

Many other operations are possible; when designing an ADT, you should try to provide enough operations to make the ADT useful in many contexts, but not so many that it gets confusing. It is not always easy to achieve this goal; it will sometimes be necessary to add operations in order for a new application to use an existing ADT.

Question 1: What other operations on Lists might be useful? Define them by writing descriptions like those in the

Question 2: Note that the second add method (the one that adds an item at a given position) can be called with a position that is equal to size(), but for the get and remove methods, the position has to be less than size(). Why?

Question 3: Another useful abstract data type is called a Map. A Map stores unique "key" values with associated information. For example, you can think of a dictionary as a Map, where the keys are the words, and the associated information is the definitions.

What are some other examples of Maps that you use?

What are the useful operations on Maps? Define them by writing descriptions like those in the table above.

Java Interfaces

The List ADT operations given in the table above describe the public interface of the List ADT, that is, the information the someone would need to know in order to be able to use a List (and keep in mind that the user of a List does not - and should not - need to know any details about the private implementation).

Now let's consider how we can create an ADT using Java. Java provides a mechanism for separating public interface from private implementation: interfaces. A Java interface (i.e., an interface as defined by the Java language) is very closely tied to the concept of a public interface. A Java interface is a reference type (like a class) that contains only (public) method signatures and class constants. Java interfaces are defined very similarly to the way classes are defined. A ListADT interface with the List ADT operations we've described would be defined as follows:

public interface ListADT<E> {
    void add(E item);
    void add(int pos, E item);
    boolean contains(E item);
    int size();
    boolean isEmpty();
    E get(int pos);
    E remove(int pos);
}

Everything contained in a Java interface is public so you do not need to include the public keyword in the method signatures (although you can if you want). Notice that, unlike a class, an interface does not contain any method implementations (i.e., the bodies of the methods). The method implementations are provided by a Java class that implements the interface. To implement an interface named InterfaceName, a Java class must do two things:

1. include "implements InterfaceName" after the name of the class at the beginning of the class's declaration, and
2. for each method signature given in the interface InterfaceName, define a public method with the exact same signature

For example, the following class implements the ListADT interface (although it is a trivial implementation):

public class ListImplementation<E> implements ListADT<E> {
    private E myItem;
    
    public ListImplementation() {
        myItem = null;
    }
    
    public void add(E item) {
        myItem = item;
    }
    
    public void add(int pos, E item) {
        myItem = item;
    }
    
    public boolean contains(E item) {
        return false;
    }
    
    public int size() {
        return 0;
    }
    
    public boolean isEmpty() {
        return false;
    }
    
    public E get(int pos) {
        return null;
    }
    
    public E remove(int pos) {

        return null;
    }
}

Lists vs. Arrays

In some ways, a List is similar to an array: both Lists and arrays are ordered collections of objects and in both cases you can add or access items at a particular position (and in both cases we consider the first position to be position zero). You can also find out how many items are in a List (using its size method), and how large an array is (using its length field).

The main advantage of a List compared to an array is that, whereas the size of an array is fixed when it is created (e.g., int[] A = new int[10] creates an array of integers of size 10 and you cannot store more than 10 integers in that array), the size of a List can change: the size increases by one each time a new item is added (using either version of the add method) and the size decreases by one each time an item is removed (using the remove method).

For example, suppose we have an ArrayList class that implements the ListADT interface. Here's some code that reads strings from a file called data.txt and stores them in a ListADT named words, initialized to be an ArrayList of Strings:

ListADT<String> words = new ArrayList<String>();
File infile = new File("data.txt");
Scanner sc = new Scanner(infile);
while (sc.hasNext()) {
    String str = sc.next();
    words.add(str);
}

If we wanted to store the strings in an array, we'd have to know how many strings there were so that we could create an array large enough to hold all of them.

One disadvantage of a List compared to an array is that whereas you can create an array of any size and then you can fill in any element in that array, a new List always has size zero and you can never add an object at a position greater than the size. For example, the following code is fine:

String[] strList = new String[10];
strList[5] = "hello"; !

but this code will cause a runtime exception:

ListADT<String> strList = new ArrayList<String>();
strList.add(5, "hello");       // error! can only add at position 0

Another (small) disadvantage of a List compared to an array is that you can declare an array to hold any type of item, including primitive types (e.g., int, char), but a List only holds Objects. Thus the following causes a compile-time error:

List<int> numbers = new ArrayList<int>();

% javac Test.java
Test.java:9: unexpected type
found   : int
required: reference
        List<int> numbers = new ArrayList<int>();
             ^

Fortunately, for each primitive type, there is a corresponding "box" class (also sometimes called a wrapper class). For example, an Integer is an object that contains one int value. Java has a feature called auto-boxing that automatically converts between int and Integer as appropriate. For example,

ListADT<Integer> numbers = new ArrayList<Integer>();
 
// store 10 integer values in list numbers
for (int k = 0; k < 10; k++) {
    numbers.add(k); // short for numbers.add(new Integer(k));
}
 
// get the values back and put them in an array
int[] array = new int[10];
for (int k = 0; k < 10; k++) {
    array[k] = numbers.get(k); // short for array[k] = numbers.get(k).intValue();
}

(Older versions of Java required that your code do the boxing up of a primitive value into the corresponding wrapper class explicitly; for example, here's the code that does the same thing as the example above using explicit boxing and unboxing:

ListADT<Integer> numbers = new ArrayList<Integer>();
 
// store 10 integer values in list numbers
for (int k = 0; k < 10; k++) {
    numbers.add(new Integer(k)); 
}
 
// get the values back and put them in an array
int[] array = new int[10];
for (int k = 0; k < 10; k++) {
    array[k] = numbers.get(k).intValue();
}

(sumber) http://pages.cs.wisc.edu/