Outline
- List interface [review]
- Array lists
- linked lists
- nodes
- linked list implementation
- invariants
Lists
- From the book [p. 62]:
A list is an expandable collection of elements in which each element has a position or index.
- there are many lists, usually categorized by how they are implemented:
- ArrayLists are implemented using arrays [Vectors are similar]
- LinkedLists are implemented using links [references] to objects
- All lists are derived from the abstract class AbstractList, and implement the List interface [even AbstractList implements the List interface]
- unlike arrays, lists can grow and shrink
- most lists can also insert elements in-between existing elements, and likewise remove elements without leaving a gap
- lists also have operations to search for elements, and do something with every element of the list
Generic interface
- a list can store object of any one type:
- a list of strings: List
- a list of integers: List
- a list of objects: List
- the notation "List" indicates that the list interface is parametrized over the type E of objects it can store
- in this case, E is a type parameter -- logically, it provides a collection of interfaces, one for each possible class
- classes can use the same notation
- these are called generic interfaces or classes
- collection classes, which can store objects of any type, are often generic
- the Java compiler can check that the type parameter is the same for every use of a variable: for example, that all operations involving a List actually store and retrieve strings
List Interface
public interface list extends Collection {
E get[int index]; // returns object at given position
E set[int index, E element]; // sets object, returns old value
int indexOf[Object o]; // returns index of object in list
E remove[int index]; // removes object at the given position
int size[]; // returns number of elements in list
boolean add[E element]; // add element at the end of the list
void add[int index, E element]; // add element at given position
...
}
- AbstractList essentially provides the same methods as List
- the methods implemented by AbstractList provide very basic functionality for immutable lists
ArrayList Class
- an array list uses an array to store the objects in the list
- the object at position i in the list are found at array index i
- when the array needs to grow, a bigger array is allocated, and data is copied from the old array to the new array
- this is an expensive operation: it takes time proportional to the total size of the collection
- in general, the underlying array may have more elements than the collection [since the collection does not have to store a value on every element of the array]
- for example, the array may have 39 elements, but the collection may only have 22 elements
- so an array list always has a capacity [39] that is greater than or equal to its size [22]
ArrayList implementation
- must have an actual array of objects of type E
- must keep track of the size
- the capacity is the same as the array length
public class ArrayList {
protected E [] data;
protected int size;
@SuppressWarnings["unchecked"]
public ArrayList[] {
data = [E []] new Object [16];
}
- Java will not allocate an array with a type that is not know at compile time
- @SuppressWarnings["unchecked"] is used to suppress warnings about the type conversion not being checked
Adding at the end of an ArrayList
- if there is room, adding at the end is easy:
public boolean add[E value] {
data [size] = value;
size++;
return true;
}
- if there is no room, we will need to make room by reallocating the array:
public boolean add[E value] {
if [size == data.length] {
data = Arrays.copyOf[data, data.length * 2];
}
data [size] = value;
size++;
return true;
}
- In-class exercise: [with a friend], implement this method [below] to add a value somewhere in the middle of the array. Assume that the index is valid, i.e. index >= 0 and index < data.length.
- Your code must shift all the data that is at or after index, so there is room for one new element
- only use a for loop, not methods from other classes
public void add[int index, E value] {
In-class exercise: big O for
- Assignment 1
- Loops.java, which produced this output.
- ArrayList add and remove methods
Linked list vs. array list
- in an array list, the elements of the list are stored in the array
- if more elements are needed, the array can be replaced with a bigger array
- that means the elements are stored in a single object [an array] whose size may be different depending on the number of elements
- instead, consider storing the elements into a variable number of objects
- where each object can only store one element
- so there will be as many container objects as there are elements in the list
Linked list
- each object that stores an element is called a Node
- the only difficulty with having a variable number of nodes is keeping track of them, that is, finding them when needed
- this is easy if each of the nodes holds a reference to another one of the nodes
- then, to keep track of all the nodes, we only need a reference to the first one
- following the reference in the first nodes, we get to the second nodes
- the reference in the second nodes refers to the third nodes
- meanwhile, each of the nodes also refers to one of the elements of the collection
private class LinkedNode {
private T item;
private LinkedNode next;
private LinkedNode[T value] {
item = value;
next = null;
}
private LinkedNode[T value, LinkedNode reference] {
item = value;
next = reference;
}
}
Linked list nodes
- each node has two data fields: an element value, and a reference to the next node
- the element value has generic type T [or E -- it must match the type name in the class declaration]
- note that the reference to the next node is a pointer to the next node, and not the next node itself
- a private class is local to the enclosing [parent] class
- private data fields in the private class are accessible to the code in the parent class
Linked list implementation
- the linked list class only really needs one class variable: a reference to the start of the list, conventionally known as the head of the list
- the book also has a size class variable, which can be useful for error checking
- my implementation also keeps a reference to the last node in the linked list
Linked list performance
- in-class exercise: what is the run-time performance of add[E]?
- in-class exercise: what is the run-time performance of add[int, E]?
- in-class exercise: what is the run-time performance of remove[], which removes the head of the linked list?
- in-class exercise: what is the run-time performance of remove[int], which removes an arbitrary element?
Invariants
- There are some relations that must hold between the different class variables
- for example, size must always be the number of nodes in the linked list
- in a linked list of length 1, head == tail
- in a linked list of length 0, both head and tail should be null
- tail should be the node holding the last element of the list: a list traversal beginning at the head of the list should visit the tail node last of all
- these relations must always hold: they never change, that is, they are invariant [invariant is something that never changes]
Methods and Invariants
- every constructor must establish the invariants of the class
- every other method may expect that the invariants are true when the method is called, and
- every method must guarantee that the invariants are still true at the end of the method
Using Invariants
- invariants are useful for reasoning about the program
- some invariants can be checked by the program itself
- if an invariant is ever detected to not be true, the program should provide enough information to track down the bug [and should either crash, or re-establish the invariant]
- in ICS 211, if your classes have any invariants, your code should check them at the beginning and at the end of each public method
- this may help you improve your understanding of your code, and may also help you find bugs
- see also the linked list invariants
- if checking is slow, you may have to remove the invariant checking [e.g., add a return statement at the beginning of the check method] when doing performance testing
Video liên quan