Array-based generic list (cont)

1
Inserting and removing
 the previous illustrations should make it clear that
inserting or removing an element in an array-based list
has worst-case complexity in because we have to move
up to elements

2
public class SArrayList<E> implements SList<E> {

private final int DEFAULT_CAPACITY = 16;

private Object[] arr;
private int size;

public SArrayList() {
this.arr = new Object[DEFAULT_CAPACITY];
this.size = 0;
}

@Override
public int size() {
return this.size;
}

3
 @Override
public void add(E elem) {
// do we need to resize the array?
if (this.size() == this.arr.length) {
this.arr = Arrays.copyOf(this.arr,
this.arr.length * 2);
}
this.arr[this.size] = elem;
this.size++;
}

4
 /**
* Throws an {@code IndexOutOfBoundsException} if index is
* less than 0 or greater than {@code this.size - 1}.
*
* @param index an index to validate
* @throws {@code IndexOutOfBoundsException} if index
* is less than 0 or greater than {@code this.size - 1}
*/
private void checkIndex(int index) {
if (index < 0) {
throw new IndexOutOfBoundsException(
"negative index: " + index);
}
else if (index >= this.size) {
throw new IndexOutOfBoundsException(
"index out of bounds: " + index + ", size: " +
this.size);
}
}
5
 @Override
public E get(int index) {
this.checkIndex(index);
return (E) this.arr[index];
}

@Override
public E set(int index, E elem) {
// get element at index, this also checks the index
E old = this.get(index);
this.arr[index] = elem;
return old;
}

6
 @Override
public void add(int index, E elem) {
// index can be equal to this.size
if (index == this.size) {
this.add(elem);
return;
}
this.checkIndex(index);

// move elements at indexes size-1, size-2, ..., index

// one position to right
// i is in the index of the element to move to the right
for (int i = this.size - 1; i >= index; i--) {
this.arr[i + 1] = this.arr[i]; // can this throw?
}
// insert elem and update size
this.arr[index] = elem;
this.size++;
} There is an error in this method; can you see what it is?
7
 @Override
public E remove(int index) {
// get element at index, this also checks the index
E removed = this.get(index);

// move elements at indexes index+1, index+2, ...,

// size-1 one position to left
// i is in the index of the element to move to the right
for (int i = index + 1; i < this.size; i++) {
this.arr[i - 1] = this.arr[i]; // can this throw?
}
// null out old last element and update size
this.arr[this.size - 1] = null;
this.size--;
return removed;
}

8
 @Override
public Iterator<E> iterator() {
return new ArrayIterator();
}

private class ArrayIterator implements Iterator<E> {

9
Iterators for array-based lists
 review Iterator interface from Lecture 20: Interfaces

10
The Iterator interface
 an Iterator is an object that knows how to iterate
over a collection of elements or a sequence of values
 using an Iterator object is the only guaranteed safe
way of iterating over a List or Set and removing
elements during the iteration
 see List and Set notebooks for details
 Java's for-each loop actually uses an Iterator object
 the language hides the object from the programmer by
having the compiler create the object and call the
appropriate methods

11
The Iterator interface
package java.util;

public interface Iterator<T> {

public boolean hasNext();

public T next();
public default void remove() {
throw new UnsupportedOperationException();
}

// one more default method not shown here

}

12
The remove method
 the remove method removes the element that was
most recently returned by next
 it can be called only once for each call to next
 an IllegalStateException is thrown if remove is called
without first calling next, or if remove has already been called
after the most recent call to next
 using an iterator is the only safe way to filter a
collection
 e.g., to remove all negative values from a list or set of
integers

13
// assume t refers to a List or Set
for (Iterator<Integer> iter = t.iterator(); iter.hasNext(); ) {
Integer val = iter.next();
if (val < 0) {
iter.remove(); // can call remove once for each call to next
}
}

14
An iterator is similar to a cursor
 in a text editor, a cursor sits between letters

15
Example of an iterator
 iterator between indexes 7 and 8

prev next

 calling next returns the element 6 and advances the

iterator
16
Iterator after calling next

17
Iterator at end of list
 hasNext return false
 next will throw an exception

18
Iterator at start of list
 at the start of the list, there is no previous element so
we set prev = -1

19
 private class ArrayIterator implements Iterator<E> {
/**
* Index of element returned by subsequent call to next.
*/
A nested, inner class (or
private int next; just inner class).

/**
* Index of element returned by most recent call
* to next. Reset to -1 if this element is deleted by a
* call to remove. An inner class object has
*/ access to the members of its
enclosing object, so
private int prev;
ArrayIterator has access
to the fields and methods of
ArrayIterator() { SArrayList.
this.next = 0;
this.prev = -1;
}
20
 @Override
public boolean hasNext() {
return this.next < SArrayList.this.size;
}

21
 @Override
public E next() {
if (!this.hasNext()) {
throw new NoSuchElementException();
}
E e = SArrayList.this.get(this.next);
// slightly more efficient would be
// E e = SArrayList.this.arr[this.next];
this.prev = this.next;
this.next++;
return e;
}

22
Iterator remove
 suppose that we have the following iterator

 the most recent element returned by next is the 6

 the element that should be returned by the next call to
next is the 10
23
Iterator remove
 calling remove removes the 6

prev next
 that is, we remove the element at index prev by calling
the SArrayList remove method

24
Iterator remove
 after removing the 6 we have the following situation

prev next
 notice that next is now the wrong index (it should be
the index of the element 10)
 easy to fix, just decrement next
25
Iterator remove
 next and prev now have the same value which does
not make sense

prev next
 we set prev = -1 to indicate that we cannot call
remove again without first calling next

26
 @Override
public void remove() {
if (this.prev == -1) {
throw new IllegalStateException();
}
SArrayList.this.remove(this.prev);
this.next--;
this.prev = -1;
}

} // end ArrayIterator

} // end SArrayList

27
 (Singly) Linked lists

28
Linked lists
 a linked list is an implementation of a list that uses
linked nodes to represent elements in a sequence
 the node at the front of the list is traditionally called
the head node and the node at the end of the list is
called the tail node
 in a singly-linked list, each node has a link to the next
node in the sequence
 in a doubly-linked list, each node has links to the next
and previous nodes in the sequence

29
Visualizing a linked list
 looks similar to a node-based stack or queue

30
The empty list

31
Linked lists have a recursive structure
 every node of a linked list can be thought of as being
the head node of some list

 this makes implementing subList very easy

32
Linked lists have a recursive structure
 the second node is the head node of a list of size 3

33
Linked lists have a recursive structure
 the third node is the head node of a list of size 2

34
Linked lists have a recursive structure
 the tail node is the head node of a list of size 1

35
Linked lists have a recursive structure
 because the structure of a linked list is recursive, most
linked-list algorithms can be implemented recursively
 for example, we can easily compute the size of linked list
recursively

36
public int size() {
return this.recSize(this.head);
}

private int recSize(Node<E> head) {

if (head == null) {
return 0;
}
// at least 1 node in this list (the head node)
// recursively compute size of the rest of the list
return 1 + this.recSize(head.next);
}

37