数据结构（顺序表、队列、栈、单链表）

时间复杂度

时间复杂度

线性表

具有相同数据类型的n个数据元素的有限序列

除第一个元素外，每个元素有且仅由一个直接前驱 除最后一个元素有且仅由一个直接后继

需要的部分

1. 存储空间大小
2. 最大容量
3. 当前长度

存储方式

1. 顺序存储
2. 链式存储

顺序表(JAVA)

算法流程：在顺序表L的第i(1 ≤ i ≤ L.length + 1)个位置插入新元素E。如果i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的所有元素后移一个位置，来插入新的元素e,顺序表长度增加1，插入成功，返回true

public class ArrayList<T> {

    private Object[] data = null; // 默认设置为null 
    
    private int length;
    
    private int current;
    
    
    public ArrayList(int initSize) { // 初始化顺序表 定义表的大小
        if(initSize > 0 ) { // 判断initSize的值是否合法
            this.length = initSize; // 容量
            
            this.current = 0; // 当前数组下标默认为0
            
            this.data = new Object[initSize]; // 初始化线性表
        }else {
            throw new RuntimeException("初始化大小不能小于0:" + initSize);
        }
    }
    
    public Boolean insert(Object elem) {  // 在末尾插入元素
        if(this.isFull()) {
            return false;
        }
        data[current] = elem;
        current ++;
        return true;
    }
    
    public Boolean insertToIndex(int index,Object elem) { // 按下标插入元素
        if(isFull()) {
            return false;
        }
        if(index > current) {
            return false;
        }
        for(int i = current - 1;i > index - 1;i --) {
            data[i + 1] = data[i];
        }
        data[index] = elem;
        current ++;
        return true;
    }
    
    public Boolean isFull() { // 判断表是否已满
        if(this.current >= this.length) {
            length *= 2; // 如果已满扩大表的容量 
            this.data = Arrays.copyOf(data, length); // 将原数组进行拷贝
        }
        return false;
    }
    
    public int size() { // 获取表的长度
        return this.current;
    }
    
    public int length() { // 获取表的容量
        return this.length;
    }
    
    /*
    * 
    * @param index 下标
    * @return 
    */
    public Boolean removeToIndex(int index) { // 按下标删除元素
        if(index >= current ) {
            return false;
        }
        for(int i = index;i <current - 1; i++) {
            data[i] = data[i + 1];
        }
        data[current - 1] = null;
        current --;
        return true;
    }
    
    public T getDataByIndex(int index) { // 根据下标获取数据
        if(index >= current && index < 0) {
            return null;
        }
        return (T) data[index];
    }
    
    public Boolean isEmpty() { // 判断是否为空
        return this.current == 0;
    }   
}

二分法查找

public static int dichotomy(int[] arr,int target) {
     int begin = 0;
    
     int end = arr.length;
    
     int middle = (begin + end)/2;
     
     int index = -1;
     
     while(begin <= end) {
         if(arr[middle] == target) {
             index = middle;
             break;
         }else if(arr[middle] < target){
             begin = middle + 1; 
         }else {
             end = middle - 1;
         }
         middle = (begin + end)/2;
     }
     return index;
}

栈（后进先出）

public class MyStack<T> {
    
    private Object[] data;
    
    public MyStack() {
        data = new Object[0];
    }
    
    // 压入数据
    public void push(T elem) {
        // 创建一个新数组
        Object[] newArr = new Object[data.length + 1];
        // 把原数组中的数据复制到新数组中
        for(int i = 0;i < data.length;i++) {
            newArr[i] = data[i];
        }
        
        newArr[data.length] = elem;
        data = newArr;
    }
    
    // 取出栈顶元素数据
    public T pop() {
        if(isEmpty()) {
            throw new RuntimeException("stack is empty");
        }
        T popObj = (T)data[data.length - 1];
        Object[] newArr = new Object[data.length - 1];
        for(int i =0;i < data.length -1;i++) {
            newArr[i] = data[i];
        }
        data = newArr;
        return popObj;
    }
    
    // 查看栈顶元素
    public T peek() {
         if(isEmpty()) {
            throw new RuntimeException("stack is empty");
        }
        return (T)data[data.length - 1];
    }
    
    // 查看是否为空
    public Boolean isEmpty() {
        return data.length == 0;
    }
}

队列（先进先出）

实现的方式与栈类似

单链表

public class Node <E> {

    private Object data; // 数据域
    
    private Node<E> next; // 节点域
    
    public Node(E elem) {
        // TODO Auto-generated constructor stub
        this.data = elem;
    }
    // 获取下一节点
    public Node next() {
        return this.next;
    }
    
    // 为节点追加节点
    public Node append(Node node) {
        // 当前节点
        Node currentNode = this;
        // 循环向后找
        while(true) {
            // 取出当前节点
            Node nextNode = currentNode.next;
            // 如果没有下一个节点，即下个节点为Null跳出循环
            if(nextNode == null){
                break;
            }
            // 赋值给当前节点
            currentNode = nextNode;
        }
        currentNode.next = node;
        return this;
    }
    
    public E getData() {
        return (E)data;
    }
    
    // 显示所有节点信息
    public void show() {
        Node currentNode = this;
        while(true) {
            System.out.print(currentNode.data + " ");
            if(currentNode.next == null)break;
            currentNode = currentNode.next;
        }
        System.out.println();
    }
    
    // 删除下一个节点
    public void removeNext() {
        // 取出下下一个节点
        Node newNext = next.next;
        // 把下下一个节点设置为当前节点的下一个节点
        this.next = newNext;
    }
    
    // 插入节点作为当前节点的下一节点
    public void insert(Node node) {
        // 取出下一个节点,作为下下一个节点
        Node nextNextNode = this.next;
        // 把新节点插入
        this.next = node;
        // 把下下一个节点接到新节点后
        node.next = nextNextNode;
    }
    
    // 判断是否为最后一个节点
    public boolean isLast() {
        return this.next == null;
    }
}

循环链表

private Node<E> next;
修改为
private Node<E> this;
即最后一个节点的下一个节点为第一个节点