二、动态数组

一、什么是数据结构？

数据结构是计算机存储、组织数据的方式。

在实际应用中，根据使用场景来选择最合适的数据结构

二、线性表

线性表是具有n个相同类型元素的有限序列(n >= 0)

• 是首节点(首元素)，是尾结点(尾元素)
• 是的前驱，是的后继

常见的线性表有：

1. 数组
2. 链表
3. 栈
4. 队列
5. 哈希表（散列表）

三、数组

数组是一种顺序存储的线性表，所有元素的内存地址是连续的

四、动态数组（Dynamic Array）

1、接口设计

int size(); // 元素的数量

boolean isEmpty(); // 是否为空

boolean contains(E element); // 是否包含某个元素

void add(E element); // 添加元素到最后面

E get(int index); // 返回index位置对应的元素

E set(int index, E element); // 设置index位置的元素

void add(int index, E element); // 往index位置添加元素

E remove(int index); // 删除index位置对应的元素

int indexOf(E element); // 查看元素的位置

void clear(); // 清除所有元素

2、成员变量和构造方法

动态数组应该有2个主要的成员变量size和elements：

/**
 * 元素的数量
 */
private int size;
/**
 * 所有的元素
 */
private E[] elements;

private static final int DEFAULT_CAPACITY = 10;
private static final int ELEMENT_NOT_FOUND = -1;

public ArrayList(int capaticy) {
    capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
    elements = (E[]) new Object[capaticy];
}

public ArrayList() {
    this(DEFAULT_CAPACITY);
}

3、size、clear和isEmpty的实现

/**
 * 元素的数量
 * @return
 */
public int size() {
    return size;
}

/**
 * 是否为空
 * @return
 */
public boolean isEmpty() {
     return size == 0;
}

/**
 * 清除所有元素
 */
public void clear() {
    for (int i = 0; i < size; i++) {
        elements[i] = null;
    }
    size = 0;
}

4、容错方法实现

private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        outOfBounds(index);
    }
}

private void outOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}

5、get方法实现

/**
 * 获取index位置的元素
 * @param index
 * @return
 */
public E get(int index) {
    rangeCheck(index);
    return elements[index];
}

6、set方法实现

/**
 * 设置index位置的元素
 * @param index
 * @param element
 * @return 原来的元素ֵ
 */
public E set(int index, E element) {
    rangeCheck(index);
    
    E old = elements[index];
    elements[index] = element;
    return old;
}

7、查看元素的索引

private static final int ELEMENT_NOT_FOUND = -1;
/**
 * 查看元素的索引
 * @param element
 * @return
 */
public int indexOf(E element) {
    if (element == null) {  // 1
        for (int i = 0; i < size; i++) {
            if (elements[i] == null) return i; 
        }
    } else {
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) return i; // n
        }
    }
    return ELEMENT_NOT_FOUND;
}

8、是否包含某个元素

/**
 * 是否包含某个元素
 * @param element
 * @return
 */
public boolean contains(E element) {
    return indexOf(element) != ELEMENT_NOT_FOUND;
}

9、打印数组

@Override
public String toString() {
    // size=3, [99, 88, 77]
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(", [");
    for (int i = 0; i < size; i++) {
        if (i != 0) {//只要不是第0个元素，就在元素前面添加一个逗号
            string.append(", ");
        }
        
        string.append(elements[i]);
        
//      if (i != size - 1) {
//          string.append(", ");
//      }
    }
    string.append("]");
    return string.toString();
}

10、remove方法实现

/**
 * 删除index位置的元素
 * @param index
 * @return
 */
public E remove(int index) {
    rangeCheck(index);
    
    E old = elements[index];
    for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
    }
    elements[--size] = null;
    return old;
}

11、添加元素

/**
 * 添加元素到尾部
 * @param element
 */
public void add(E element) {
    add(size, element);
}

/**
 * 在index位置插入一个元素
 * @param index
 * @param element
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);
    
    ensureCapacity(size + 1);
    
    for (int i = size; i > index; i--) {
        elements[i] = elements[i - 1];
    }
    elements[index] = element;
    size++;
}

容错处理

private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size) {
        outOfBounds(index);
    }
}

private void outOfBounds(int index) {
    throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}

12、扩容

/**
 * 保证要有capacity的容量
 * @param capacity
 */
private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
    
    // 新容量为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
    
    System.out.println(oldCapacity + "扩容为" + newCapacity);
}

代码链接