필기 데이터 구조 - 동적 배열 목록

1. 배열 기초
배열 의 가장 큰 데 이 터 를 저장 하 는 선형 데이터 구조 로 가장 원시 적 인 배열 은 정적 배열 로 배열 의 용량 을 설명 해 야 한다. new 에서 배열 대상 의 크기 가 바 뀌 지 않 으 면 색인 을 통 해 데이터 의 추가 삭제 와 검 사 를 할 수 있다.우 리 는 정적 배열 의 2 차 패 키 징 을 통 해 동적 배열 로 개선 할 수 있다.
4. 567917. 배열 의 가장 큰 장점: 빠 른 조회
4. 567917. 배열 은 '색인 에 의미 가 있다' 는 상황 에 사용 하 는 것 이 가장 좋다
4. 567917. 그러나 모든 의미 있 는 색인 이 배열 에 적용 되 는 것 은 아니다.예 를 들 어 배열 로 인원 을 저장 할 때 신분증 번호 로 색인 을 충당 할 때 인원 을 구별 할 수 있 지만 신분증 번호 가 너무 길 어서 메모리 공간 을 크게 낭비 하면 얻 는 것 보다 잃 는 것 이 많다
4. 567917. 배열 도 색인 이 의미 가 없 는 상황 을 처리 할 수 있다
2. 정적 배열 을 기반 으로 한 동적 배열 링크 (자바 의 ArrayList 와 비교 가능)

package com.tc.javabase.datastructure.array;


import java.util.Arrays;

/**
 * @Classname ArrayList
 * @Description                 
 *
 *        ：
 *              
 *                           O(n)
 *                           O(1)
 *                          O(n)
 *
 *            
 *                      O(1)
 *                      O(1)
 *                    O(1)
 *                     O(n)
 *                      O(n)
 *
 *              
 *                      O(n)
 *                      O(1)
 *                      O(n)
 *
 *              
 *                  O(1)
 *                  O(1)
 *                  O(1)
 *
 *       ：
 *    ：O(n)  addLast(): O(1)
 *    ：O(n)  removeLast(): O(1)
 *    ：    : O(1)       : O(n)
 *    :     : O(1)       : O(n)
 *
 *                              ，          （         ）
 *           O(1).
 *
 * @Date 2020/7/15 19:53
 * @Created by zhangtianci
 */
public class ArrayList {
    private E[] data;
    private int size;

    /**
     *       
     *        8
     */
    public ArrayList() {
        this.data = (E[]) new Object[8];
        this.size = 0;
    }

    public ArrayList(int capacity) {
        this.data = (E[]) new Object[capacity];
        this.size = 0;
    }

    public ArrayList(E[] arr){
        data = (E[])new Object[arr.length];
        for(int i = 0 ; i < arr.length ; i ++)
            data[i] = arr[i];
        size = arr.length;
    }


    /**
     *       
     *             
     *             
     *               
     */

    /**
     *             
     *
     *      :O(n)
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     *             
     *
     *      :O(1)
     */
    public void addLast(E e) {
        //      
        //        
//        if (size == getArrayLength()){
//            throw new IllegalArgumentException("      ，         ！");
//        }
//
//        array[size] = e;
//        size++;


        //    add(int index,int e)
        add(size, e);
    }

    /**
     *               
     *
     *
     *      :O(n)
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        //      
        //1.        
//        if (size == getArrayLength()){
//            throw new IllegalArgumentException("      ，         ！");
//        }

        //2.         index < 0 || index >= getArrayLength() || index > size
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("       !");
        }

        //   
        if (size == getCapacity()) {
            resize(data.length * 2);
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

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


    /**
     *     
     *       
     *       
     *         
     */

    /**
     *       
     *
     *      :O(1)
     * @return
     */
    public E getFirst() {
        return get(0);
    }

    /**
     *       
     *
     *      :O(1)
     * @return
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     *         
     *
     *      :O(1)
     * @param index
     * @return
     */
    public E get(int index) {
        //      
        //          index < 0 || index >= size
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("        ！");
        }
        return data[index];
    }

    /**
     *       
     *      
     *      
     *         
     */

    /**
     *      
     *
     *      :O(n)
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     *      
     *
     *      :O(1)
     */
    public E removeLast() {
        return remove(size - 1);
    }

    /**
     *         
     *
     *     :O(n)
     * @param index
     */
    public E remove(int index) {
        //      
        //         index < 0 || index >= size
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("       ");
        }

        E e = get(index);
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        size--;
        data[size] = null;

        //  
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }
        return e;
    }

    /**
     *       
     *      
     *      
     *       
     *
     */

    /**
     *      
     *
     *      :O(1)
     * @param e
     */
    public void setFirst(E e) {
        set(0, e);
    }

    /**
     *      
     *
     *      :O(1)
     * @param e
     */
    public void setLast(E e) {
        set(size - 1, e);
    }

    /**
     *       
     *
     *      :O(1)
     * @param index
     * @param e
     */
    public void set(int index, E e) {
        //    
        //         index < 0 || index >= size
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("        ！");
        }
        data[index] = e;
    }


    /**
     *        
     *
     *      :O(n)
     */
    public boolean contain(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

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

    /**
     *            
     *
     * @return
     */
    public int getSize() {
        return size;
    }

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


    public boolean isEmpty(){
        return size == 0 ? true : false;
    }

    public void swap(int i, int j){

        if(i < 0 || i >= size || j < 0 || j >= size)
            throw new IllegalArgumentException("Index is illegal.");

        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    /**
     *   toString
     *
     */
    @Override
    public String toString() {
        return "ArrayList{" +
                "array=" + Arrays.toString(data) +
                ", size=" + size +
                '}';
    }




    public static void main(String[] args) {


        int i = 1;

        while (i == 1){

        }

        /**
         *          
         */
        ArrayList arrayList = new ArrayList(5);
        arrayList.addFirst(1);
        arrayList.addFirst(2);
        ;
        arrayList.addFirst(3);
        System.out.println(arrayList.toString());
        arrayList.add(2, 0);
        System.out.println(arrayList.toString());
        arrayList.addLast(99);
        System.out.println(arrayList.toString());
        arrayList.addLast(99);
        System.out.println(arrayList.toString());


        /**
         *         
         */
        System.out.println("first element: " + arrayList.getFirst());
        System.out.println("last element: " + arrayList.getLast());
        System.out.println("get element index of 1 :" + arrayList.get(1));

        /**
         *         
         */
        arrayList.removeFirst();
        arrayList.removeLast();
        arrayList.remove(1);
        arrayList.removeLast();
        System.out.println(arrayList.toString());

        /**
         *         
         */
        arrayList.setFirst(12);
        arrayList.setLast(13);
        arrayList.set(1, 55);
        System.out.println(arrayList.toString());

        /**
         *          
         */
        System.out.println(arrayList.contain(12));
        System.out.println(arrayList.contain(55));
        System.out.println(arrayList.contain(515));

        /**
         *          
         */

        System.out.println(arrayList.find(12));
        System.out.println(arrayList.find(55));
        System.out.println(arrayList.find(515));
    }
}