数组

数据结构

• 数据在计算机中进行组织和存储,更高效的获取数据或者修改数据
• 线性结构
  • 数组
  • 栈
  • 队列
  • 链表
  • 哈希表
• 数结构
  • 二叉树
  • 二分搜索数
  • AVL
  • 红黑树
  • Treap
  • Splay
  • 堆
  • Trie
  • 线段树
  • K-D树
  • 并查集
  • 哈夫曼树
• 图结构
  • 邻接矩阵
  • 邻接表

数组

// 增O(n)删O(n)改O(1或n)查O(1或n)
public class Array{
    
    private int[] data;

    private int size;

    public Array(int capacity){
        data = new int[capacity];
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public int getCapacity(){
        return data.length;
    }

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

    // O(1)
    public void addLast(int e){
        add(size,e);
    }

    // O(n)
    public void addFirst(int e){
        add(0,e);
    }

    // O(n)
    public void add(int index, int e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("
                Add failed. Require index >= 0 and index <= size");
        }
        if(size == data.length){
            resize(2 * data.length);
        }
        for(int i = size - 1; i >= index; i--){
            data[i] = data[i-1];
        }
        data[index] = e;
        size++;
    }

   // O(1)
   public  int get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("
                Get failed. index is illegal");
        }
        return data[index];
    }

    public int getLast(){
        return get(size-1);
    }

    public int getFirst(){
        return get(0);
    }

    // O(1)
    public void set(int index, int e){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("
                Get failed. index is illegal");
        }
        data[index] = e;
    }

    // O(n)
    public boolean contains(int e){
        for(int i = 0; i < size; i++){
            if(data[i] == e){
                return true;
            }
        }
        return false;
    }

    // O(n)
    public int find(int e){
        for(int i = 0; i < size; i++){
            if(data[i] == e){
                return i;
            }
        }
        return -1;
    }

    // O(n)
    public int remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("
                Remove failed. Index is illegal");
        }
        int ret = data[index];
        for(int i = index + 1; i < size; i++){
            data[i-1] = data[i];
        } 
        size--;
        if(size == data.length / 4 && data.length / 2 != 0){
            resize(data.length / 2);
        }
        return ret;
    }

    // O(n)
    public int removeFirst(){
        return remove(0);
    }

    // O(1)
    public int removeLast(){
        return remove(size-1);
    }

    public void removeElement(int e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for(int i = 0; i < size; i++){
            sb.append(data[i]);
            if(i != size - 1){
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    private void resize(int newCapacity){
        int[] newData = new int[newCapacity];
        for(int i = 0; i < size; i++){
            newData[i] = data[i];
        }
        data = newData;
    }
}