# Data structure and algorithm analysis

## Table, stack, queue

### List interface, ArrayList class and LinkedList class

#### 1.1 list interface inherits Collection interface

```public interface List<E> extends Collection<E>{
E get(int index);
E set(int index,E newval);
void remove(int index);
ListIterator<E> listInterator(int pos);
//......
}
```

There are two popular implementations of List ADT

• The ArrayList class is a scalable array implementation.
• Advantage: the call to get and set takes a constant time
• Disadvantage: expensive deletion of inserts and existing items
• Advantage: the cost of inserting new items and deleting existing items is small
• Disadvantages: it's not easy to index, and get calls are expensive

Example
Delete all items in the table with even values

``` public static void removeEvensVer(List<Integer> list) {
Iterator<Integer> itr = list.iterator();
while (itr.hasNext()) {
if (itr.next() % 2 == 0) {
itr.remove();
}
}
}
```

If the efficiency of passing a LinkedList < integer > is high, for an ArrayList, even if the iterator is located on the node to be deleted, because its data needs to be moved, its remove() method is expensive.

#### 1.2 ListIterator interface

List Iterator is the function of Iterator that extends list.

#### 1.3 implementation of ArrayList class

```public class MyArrayList<E> implements Iterable<E> {
private static final int DEFAULT_CAPACITY = 10;
private int size;
private E[] items;

public MyArrayList() {
doClear();
}

private void doClear() {
this.size = 0;
ensureCapacity(DEFAULT_CAPACITY);
}

public int size() {
return size;
}

public boolean isEmpty() {
return size() == 0;
}

public void trimToSize() {
ensureCapacity(size());
}

public E get(int index) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
return items[index];
}

public E set(int index, E newVal) {
if (index < 0 || index > size) {
throw new ArrayIndexOutOfBoundsException();
}
E old = items[index];
items[index] = newVal;
return old;
}

private void ensureCapacity(int newCapacity) {
if (newCapacity < size) {
return;
}
E[] old = items;
items = (E[]) new Object[newCapacity];
for (int i = 0; i < size(); i++) {
items[i] = old[i];
}
}

return true;
}

public void add(int index, E x) {
if (items.length == size()) {
ensureCapacity(size() * 2 + 1);
}
for (int i = size; i > index; i--) {
items[i] = items[i - 1];
}
items[index] = x;
size++;
}

public E remove(int index) {
E removeItem = items[index];
for (int i = index; i < size() - 1; i--) {
items[i] = items[i + 1];
}
size--;
return removeItem;
}

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

private class ArrayListIterator implements Iterator<E> {

private int current = 0;

@Override
public boolean hasNext() {
return current < size();
}

@Override
public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return items[current++];
}

public void remove() {
MyArrayList.this.remove(--current);
}
}
}
```

To expand the capacity of ensurcapacity, first store a reference of the original array, then allocate memory for the new array, and then copy the old content to the new array.

##### 1.4 implementation of LinkedList class
```public class MyLinkedList<E> implements Iterable<E> {

private Node<E> beginMarker;
private Node<E> endMarker;
private int size;
private int modCount = 0;

private static class Node<E> {
public Node(E d, Node<E> p, Node<E> n) {
data = d;
prev = p;
next = n;
}

public E data;
public Node<E> prev;
public Node<E> next;
}

doClear();
}

private void doClear() {
beginMarker = new Node<>(null, null, null);
endMarker = new Node<>(null, beginMarker, null);
this.size = 0;
this.modCount++;
}

public int size() {
return size;
}

public boolean isEmpty() {
return size() == 0;
}

return true;
}

public void add(int index, E x) {
}

public E get(int index) {
return getNode(index).data;
}

public E set(int index, E newVal) {
Node<E> p = getNode(index);
E oldVal = p.data;
p.data = newVal;
return oldVal;
}

public E remove(int index) {
return remove(getNode(index));
}

private void addBefore(Node<E> p, E x) {
Node<E> newNode = new Node<>(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
size++;
modCount++;
}

private E remove(Node<E> p) {
p.next.prev = p.prev;
p.prev.next = p.next;
size--;
modCount++;
return p.data;
}

private Node<E> getNode(int index) {
return getNode(index, 0, size() - 1);
}

private Node<E> getNode(int index, int lower, int upper) {
Node<E> p;
if (index < lower || index > upper) {
throw new IndexOutOfBoundsException();
}
if (index < size() / 2) {
p = beginMarker;
for (int i = 0; i < index; i++) {
p = p.next;
}
} else {
p = endMarker;
for (int i = size(); i > index; i--) {
p = p.prev;
}
}
return p;
}

@Override
public Iterator<E> iterator() {
}

private class LinkedListIterator implements Iterator<E> {
private Node<E> current = beginMarker.next;
private int expectedModCount = modCount;                  // ①
private boolean okToRemove = false;// ②
@Override
public boolean hasNext() {
return current != endMarker;
}

@Override
public E next() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (!hasNext()) {
throw new NoSuchElementException();
}
E nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}

public void remove() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (!okToRemove) {
throw new IllegalStateException();
}