1. package cn.wllsrx.zoe.java;
  3. /**
  4.  * 实现动态数组的数据结构
  5.  *
  6.  * @author zoe
  7.  * <p>
  8.  * 时间复杂度
  9.  * <p>
  10.  * addLast(e) O(1)
  11.  * addFirst(e) O(n)
  12.  * add(index,e) O(n/2)=O(n)
  13.  * 添加的操作时间复杂度总的复杂度为O(n)
  14.  * <p>
  15.  * removeLast(e) O(1)
  16.  * removeFirst(e)  O(n)
  17.  * remove(index,e)  O(n/2)=O(n)
  18.  * 删除操作时间复杂度 O(n)  resize时间复杂度O(1)
  19.  * <p>
  20.  * set(index,e)   O(1)
  21.  * 修改操作复杂度  已知索引O(1)  未知索引 O(n)
  22.  * <p>
  23.  * get(index)  O(1)
  24.  * contains(e) O(n)
  25.  * find(e) O(n)
  26.  * 查询操作时间复杂度 已知索引O(1)  未知索引 O(n)
  27.  **/
  28. public class Array<E> {
  30.     private E[] data;
  31.     private int size;
  33.     /**
  34.      * 用户传入数组长度
  35.      *
  36.      * @param capacity 数组长度
  37.      */
  38.     public Array(int capacity) {
  39.         this.data = (E[]) new Object[capacity];
  40.         this.size = 0;
  41.     }
  43.     public Array() {
  44.         this(10);
  45.     }
  47.     /**
  48.      * 获取数组中的元素个数
  49.      *
  50.      * @return 个数
  51.      */
  52.     public int getSize() {
  53.         return size;
  54.     }
  56.     /**
  57.      * 获取数组的容量
  58.      *
  59.      * @return 容量
  60.      */
  61.     public int getCapacity() {
  62.         return data.length;
  63.     }
  65.     /**
  66.      * 判断数组是否为空
  67.      *
  68.      * @return 结果
  69.      */
  70.     public boolean isEmpty() {
  71.         return size == 0;
  72.     }
  74.     /**
  75.      * 在所有元素后添加一个新元素
  76.      *
  77.      * @param e 新元素
  78.      */
  79.     public void addLast(E e) {
  80.         /*if (size == data.length) {
  81.             throw new IllegalArgumentException("addLast failed. array is full");
  82.         }
  83.         data[size] = e;
  84.         size++;*/
  85.         add(size, e);
  86.     }
  88.     /**
  89.      * 在所有元素前添加一个新元素
  90.      *
  91.      * @param e 新元素
  92.      */
  93.     public void addFirst(E e) {
  94.         add(0, e);
  95.     }
  97.     /**
  98.      * 在传入索引的位置插入新元素
  99.      *
  100.      * @param index 索引
  101.      * @param e     元素
  102.      */
  103.     public void add(int index, E e) {
  104.         //判断要插入的索引位置是否大于0
  105.         if (index < 0 || index > size) {
  106.             throw new IllegalArgumentException("add failed. array is full");
  107.         }
  108.         if (size == data.length) {
  109.             //数组内存扩容两倍
  110.             resize(2 * data.length);
  111.         }
  113.         //从最后一个下标开始,将下标大于index的元素向后挪,直到index索引位置,将e插入
  114.         for (int i = size - 1; i >= index; i--) {
  115.             //给后一个位置的元素赋上前一个元素的值
  116.             data[i + 1] = data[i];
  117.         }
  118.         data[index] = e;
  119.         size++;
  120.     }
  122.     private void resize(int newCapacity) {
  123.         E[] newData = (E[]) new Object[newCapacity];
  124.         for (int i = 0; i < size; i++) {
  125.             newData[i] = data[i];
  126.         }
  127.         data = newData;
  128.     }
  130.     /**
  131.      * 获取index索引位置的元素
  132.      *
  133.      * @param index 索引位置
  134.      * @return 元素
  135.      */
  136.     E get(int index) {
  137.         if (index < 0 || index >= size) {
  138.             throw new IllegalArgumentException("get failed. index is illegal");
  139.         }
  140.         return data[index];
  141.     }
  143.     /**
  144.      * 修改index索引位置的元素为e
  145.      *
  146.      * @param index 索引
  147.      * @param e     新元素
  148.      */
  149.     void set(int index, E e) {
  150.         if (index < 0 || index >= size) {
  151.             throw new IllegalArgumentException("get failed. index is illegal");
  152.         }
  153.         data[index] = e;
  154.     }
  156.     /**
  157.      * 数组中是否存在元素e
  158.      *
  159.      * @param e 元素
  160.      * @return 存在true
  161.      */
  162.     public boolean contains(E e) {
  163.         for (int i = 0; i < size; i++) {
  164.             if (data[i].equals(e)) {
  165.                 return true;
  166.             }
  167.         }
  168.         return false;
  169.     }
  171.     /**
  172.      * 查询元素的索引
  173.      *
  174.      * @param e 元素
  175.      * @return 存在返回索引, 不存在返回-1
  176.      */
  177.     public int find(E e) {
  178.         for (int i = 0; i < size; i++) {
  179.             if (data[i].equals(e)) {
  180.                 return i;
  181.             }
  182.         }
  183.         return -1;
  184.     }
  186.     /**
  187.      * 删除当前索引位置的元素,返回删除元素
  188.      *
  189.      * @param index 索引
  190.      * @return 删除元素
  191.      */
  192.     public E remove(int index) {
  193.         if (index < 0 || index >= size) {
  194.             throw new IllegalArgumentException("get failed. index is illegal");
  195.         }
  196.         E ret = data[index];
  197.         for (int i = index + 1; i < size; i++) {
  198.             data[i - 1] = data[i];
  199.         }
  200.         size--;
  201.         //data[size] = null;
  202.         //动态缩容数组长度 当实际数组长度是数组的四分之一时,将数组长度减半,防止复杂度震荡
  203.         if (size == data.length / 4 && data.length / 2 != 0) {
  204.             resize(data.length / 2);
  205.         }
  206.         return ret;
  207.     }
  209.     /**
  210.      * 删除数组中的第一个元素
  211.      *
  212.      * @return 被删除的元素
  213.      */
  214.     public E removeFirst() {
  215.         return remove(0);
  216.     }
  218.     /**
  219.      * 删除数组中最后一个元素
  220.      *
  221.      * @return 被删除得元素
  222.      */
  223.     public E removeLast() {
  224.         return remove(size - 1);
  225.     }
  227.     /**
  228.      * 删除元素e
  229.      *
  230.      * @param e 元素
  231.      */
  232.     public void removeElement(E e) {
  233.         int index = find(e);
  234.         if (index != -1) {
  235.             remove(index);
  236.         }
  237.     }
  239.     @Override
  240.     public String toString() {
  241.         StringBuilder builder = new StringBuilder();
  242.         builder.append(String.format("Array: size = %d,capacity = %d\n", size, data.length));
  243.         builder.append("[");
  244.         for (int i = 0; i < size; i++) {
  245.             builder.append(data[i]);
  246.             if (i != size - 1) {
  247.                 builder.append(",");
  248.             }
  249.         }
  250.         builder.append("]");
  251.         return builder.toString();
  252.     }
  255.     public static void main(String[] args) {
  256.         Array<Integer> array = new Array<>(20);
  257.         for (int i = 0; i < 10; i++) {
  258.             array.addLast(i);
  259.         }
  260.         System.out.println(array);
  261.         array.add(1, 54);
  262.         System.out.println(array);
  263.     }
  264. }

项目demo