线性表

线性表是具有 n个相同类型元素的有限序列($n>=0$)
常见的线性表有
- 数组
- 链表
- 栈
- 队列
- 哈希表(散列表)

数组(Array)

数组是一种顺序存储的线性表，所有元素的内存地址是连续的
1
int[] array=new int[]{11,22,33};
在Java中，array是变量存储在栈空间内的，new是在堆空间上开辟一段连续的内存，然后把引用返回给array保存使用。
在很多编程语言中，数组都有一个致命的缺点：
- 无法动态修改容量

动态数组(Dynamic Array)接口设计

public interface List <E>{
    //indexOf查找不到返回的值
    static final int ELEMENT_NOT_FOUND = -1;
    //可以供外界使用
    int size();                     //元素的数量
    boolean isEmpty()；             //是否为空
    boolean contains(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();                   //清楚所有的元素  
}

AbstractList 存放一些公共的方法。只要子类继承它，就可以拥有这些方法，并要求实现List接口

public abstract class AbstractList<E> implements List<E>{
    protected int size;
    public int size() {
        return size;
    }

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

    @Override
    public boolean contains(E element) {
        return indexOf((element))!=ELEMENT_NOT_FOUND;
    }

    @Override
    public void add(E element) {
        add(size,element);
    }
    protected void outOfBounds(int index){
        //抛出异常
        throw  new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
    }
    protected void rangeCheck(int index){
        //检查index是否正确
        if(index<0||index>=size){
            outOfBounds(index);
        }
    }
    protected void rangeCheckForAdd(int index){
        //检查添加的index位置是否正确
        if(index<0||index>size)
        {
            outOfBounds(index);
        }
    }
}

ArrayList 实现动态数组

public class ArrayList<T> implements List<T>{
    private T[] elements;   //所有元素
    private static final int DEFAULT_CAPACITY = 10; //默认数组大小
    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayList(int capacity) {
        //接收一个capacity，创建一个大小为capacity数组
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (T[]) new Object[capacity];
    }
    
    public T get(int index){...}
    public T set(int index, T element){...}
    public void add(int index,T element){...}
    public T remove(int index){...}
    public int indexOf(T element){...}
    public void clear(){...}

    private void ensureCapacity(int capacity){...}
    private void  trim(){...}
}

操作

Get: 返回index位置的元素
- ArrayList数组是用一段连续的内存空间开辟的数组，成员变量elements保存这段连续内存空间的基址，我们只需要通过元素的下标就可以直接访问到其元素的位置，支持随机访问。
- 我们要做的操作也很简单，只需要检查以下index是否正确，然后通过elements[index]返回元素。
  1
  2
  3
  4
  public T get(int index) {
  rangeCheck(index);
  return elements[index];
  }
  - 时间复杂度为$\bigcirc(1)$

Set: 设置index位置的元素
- 同样Set方法也很简单，只需要检查所设置的下标index是否正确，然后通过elements[index]设置新值。
  1
  2
  3
  4
  5
  6
  public T set(int index, T element) {
  rangeCheck(index);
  T old = elements[index];
  elements[index] = element;
  return old;
  }
  - 时间复杂度为$\bigcirc(1)$

Add: 往index位置添加元素

在AbstractList中默认提供往数组尾添加元素，这种情况最简单的，只需要elements[index]=element;同时对size加一即可。
用户需要再已经存储元素的末尾之前插入元素，就需要对插入之后的元素每个往后移动一个位置，给index处腾空。

再添加之前需要对当前数组进行一次ensureCapacity，根据情况进行相应的扩容。

public void add(int index,T element){
    //if(element==null) return;  //不想存储空
    rangeCheckForAdd(index);
    ensureCapacity(size+1);
    for(int i=size;i>index;i--){
        elements[i]=elements[i-1];
    }
    elements[index]=element;
    size++;
}

最坏时间复杂度（往index=0处进行插入）：$\Theta(n)$
平均时间复杂度:
- 设置index={0,1,…,n}
- 在每个位置上的概率一样都为$\frac{1}{n}$
- $平均移动次数:\frac{1}{n}\sum_{i=0}^{n}(n-i)=\frac{(n+1)}{2}$
- $\bigcirc(n)$

Remove: 删除index位置对应的元素

删除index处的元素，只需要其后面的所有元素向前移动覆盖就可把其删除，但注意的是需要把原数组最后一个位置赋值为null，不然数组会保留这份末尾数据的引用，会有多个变量引用这段内存，这段内存无法被释放

在进行删除操作后，数组的容量可能会大于存储数量很多，造成空间的浪费，可以根据需求回收内存，缩小数组的容量，进行trim

public T remove(int index){
    rangeCheck(index);
    T old=elements[index];
    for(int i=index+1;i<size;i++){
        elements[i-1]=elements[i];
    }
    elements[--size]=null;
    trim();
    return old;
}

平均时间复杂度:
- 设置index={0,1,…,n}
- 在位置上的概率一样都为$\frac{1}{n}$
- $平均移动次数:\frac{1}{n}\sum_{i=0}^{n}(n-i)=\frac{(n+1)}{2}$
- $\bigcirc(n)$

indexOf: 查看元素的位置

在进行比较时，优先考虑用quuals方法，因为用的是泛型，我们设计者是不知道它们如何比较大小的，需要用户去实现比较的逻辑

如果你的设计允许存储null，那么在寻找之前需要判断。不然在调用equals方法会报空指针错误。

public int indexOf(T element) {
    if(element==null){
        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;
        }
    }

    return ELEMENT_NOT_FOUND;
}

时间复杂度：$\bigcirc(n)$

Clear(): 清楚所有的元素
- 正常来说可以把size设置为0，我们就可以不对里面的元素进行使用，但如果是存储的是对象，对象是被数组引用中的，无法被JVM释放掉，就会显得浪费空间。所以就需要遍历把每个元素置为null
- 有一种巧妙的方法是直接给elements赋值一个新的空数组，同时把size置为0，在JVM中，垃圾回收机制会回收掉没有被引用那段空间
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  public void clear() {
  /*
  for(int i=0;i<size;i++){
  elements[i]=null;
  }
  */
  elements = (T[]) new Object[DEFAULT_CAPACITY];
  this.size=0;
  
  }
  - 时间复杂度为$\bigcirc(1)$

如何进行动态数组扩容

创建一个新的数组，扩容为多少，设计者自行设计

private void ensureCapacity(int capacity){
        int oldCapacity=elements.length;
        //如果旧容量还能装下元素,则不需要扩容
        if(oldCapacity>=capacity)   return;

        //新容量为旧容量的1.5倍
        int newCapacity=oldCapacity+(oldCapacity>>1);
        T[] newElements= (T[]) new Object[newCapacity];
        for(int i=0;i<size;i++){        //拷贝赋值
            newElements[i]=elements[i];
        }
        elements=newElements;
        System.out.println(oldCapacity+"扩容为"+newCapacity);
 }

如何进行收缩

在进行缩容时要考虑缩小的倍数，一般用右移进行除法效率更高

private void  trim(){
    int capacity=elements.length;
    int newCapacity=capacity>>1;
    //如果size大于原先容量的一半，或者缩小容量后的新容量小于设计者的DEFAULT_CAPACITY默认初始容量，就不进行缩容。
    if(size>=(newCapacity)||capacity<=DEFAULT_CAPACITY) return;
    //剩余空间还有很多

    T[] newElements= (T[]) new Object[newCapacity];
    for(int i=0;i<size;i++){
        newElements[i]=elements[i];
    }
    elements=newElements;
    System.out.println(capacity+"缩容为"+newCapacity);
}

如果扩容倍数，缩容时机设计不得当，有可能会导致复杂震荡（反复扩容和缩容
- 只要扩容倍数与缩容倍数等于1就会有这种明显的震荡
对象数组
- Object[] objects=new Object[6];