ADT Lecture 7 - 25 September 2014

There is no universal implementation of data structures that would fit every use case and fast.

Lists

List is the simplest data structure of all.

In some programming languages like Python, list can be a collection of mixed objects. In Java, list must contain elements of the same type.

Operations done on list:

• Create list
• Accessing and searching
• Insert item into list
• Remove item out of list

Ways to implement list:

• Arrays
• Fast random access (can access any position in O(1) time)
• Array have constant size, so inserting, deleting is difficult as it need compacting and expanding operation
• Linked list
• Must go to each element one by one until you reach the target element (worst case access time is O(n))
• Can be grow and shrink dynamically

List interface:

public interface List<T> {
    public void insert(T element);
    public void delete(T element);
    public boolean contains(T element);
    public int size();
}

Java provides some list implementations in the standard library.

Linked list

Linked list have cells that has a value and a link to the next cell.

class ListCell<T> {
    // datum is singular form of data
    private T datum;
    // note that it is referencing current class
    // if it is null, this cell is the last element of the list
    private ListCell<T> next;

    public ListCell(T datum, ListCell<T> next) {
        this.datum = datum;
        this.next = next;
    }

    public T getDatum() {
        return datum;
    }
    public ListCell<T> getNext() {
        return next;
    }
    public void setDatum(T obj) {
        datum = obj;
    }
    public void setNext(ListCell<T> c){
        next = c;
    }
}

To create a list of one element,

// note: Integer class, not primitive
ListCell<Integer> c = new ListCell<Integer>(new Integer(24), null);

To create a linked list of 3 elements,

Integer t = new Integer(24);
Integer s = new Integer(-7);
Integer e = new Integer(87);

ListCell<Integer> p = new ListCell<Integer>(t,
    new ListCell<Integer>(s,
        new ListCell<Integer>(e, null)
    )
);

To search in the list

public static boolean search(T x, ListCell c){
    // keep looking until the next element is null
    for(ListCell lc = c; lc != null; lc = lc.getNext()){
        if(lc.getDatum().equals(x)){
            return true;
        }
    }
}

or recursive version:

public static boolean search(T x, ListCell c){
    return c != null && (c.getDatum().equals(x) || search(x, c.getNext()));
}
// or
public static boolean search(T x, ListCell c){
    if(c == null){
        return false;
    }
    if(c.getDatum().equals(x)){
        return true;
    }
    return search(x, c.getNext());
}

To reverse:

public static ListCell reverse(ListCell c){
    return reverse(c, null);
}

// overloading
private static ListCell reverse(ListCell c, ListCell r){
    if(c == null){
        return r;
    }else{
        return reverse(c.getNext(), new ListCell(c.getDatum(), r));
    }
}

To delete one x out of the list:

• If list is empty, return null
• If head datum is x, return the next element
• Otherwise, return a list of
• Head element and
• List that contains result of deleting x from the tail elements

Doubly-linked list

If the ListCell has a link to its predecessor and successor, it is called doubly-linked list.

ArrayList

• Java provide an ArrayList implementation that can be dynamically resized similar to the LinkedList implementation.