自已编写一个Java数组

孤云

前言：
         最近开始学习数据结构，刚学到数组，写下此篇博客记录下学习内容。如文中有不对的地方还请大佬指出。正文：
        1.数组（Array）：数组是一种线性表数据结构，它是一组连续的空间和相同的数据类型组成。
        2.数据的时间复杂度分析：
           1）插入：最好的情况为O(1),最坏的情况为O(n)，均摊为O(n)。
           2)  删除：最好的情况为O(1),最坏的情况为O(n)，均摊为O(n)。
           3）查询：最好的情况为O(1),最坏的情况为O(n)，均摊为O(n)。
       原因：
       插入：如果在索引3处插入一个新的值20，因为数组是一组连续的空间，为了保持数据的连续性，数据将会进行数据搬移动作，将索引3及后面的值向后移动，造成大量的时间消耗。最好的情况就是在数组的最后一个位置进行插入操作，这样就避免了大量的数据搬移。如果不需要数据的连续性，可以考虑将3处的值移动到数组末尾处，然后在将值插入到3处，这样就避免的数据的搬移。
       删除：跟插入相似，不过是将数据往前搬移。可以考虑将要删除的值做个标记，等数组内存不够用时统一做删除操作。
                                        图片是用excel制作的，有点丑。
                                       
                                       
      查询:数组查询需要遍历，遍历需要O(n)的时间。当需要查询某个值时如果这个值刚好在下标0处那么时间复杂度就为O(1)，这种情况一般很少见。如果是排好序的数组通过二分法查找时间复杂度就是O(logn）。
3.数组的优缺点
       缺点：因为数据是一组连续的空间，所以当没有连续的空间时，就没有足够的内存分配。例：当我们需要创建一个100M的数组时，此时虚拟机内存刚好只剩100M，但不是连续的，就会造成内存不够分配。
       优点：数组支持随机访问(也就是直接通过下标访问)，时间复杂度为O(1)。
4.数组的寻址公式：array_address = first_address + i * data_type_size;  first_address是数组第一个元素所在的内存地址，i是下标，data_type_size是数据类型大小。
       例：比如说我们要找到下标3的内存地址，第一个元素的内存地址是1024，数据类型是int类型，int类型占4个字节。那么array[3]_address = 1024 + 3 * 4；就是下标3的内存地址了。
5.下面开始用代码实现一个自已的数组，我使用的是Java语言编写的。

[Java] 纯文本查看 复制代码

?

001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190

/**  * @Description: 自定义数组  * @Date 2018/12/22 17:28  * @Version 1.0  **/ public class CustomArray<E> {     /**      * 数组      */     private E[] data;     /**      * 数组元素的个数      */     private int size;       /**      * 指定大小的构造器      */     public CustomArray(int capacity){         //大于0才创建数组         if(capacity > 0) {             data = (E[]) new Object[capacity];             size = 0;         }else {             throw new IllegalArgumentException("Illegal Capacity:  "+ capacity);         }     }       /**      * 默认数组大小为10      */     public CustomArray(){         this(10);     }       /**      *  获取元素的个数      */     public int getSize(){         return size;     }       /**      *  获取数组的容量      */     public int getCapacity(){         return data.length;     }       /**      *  数组元素是否为空      */     public boolean isEmpty(){         return size == 0;     }       /**      * 向数组末尾添加元素      */     public void addLast(E e){         add(size,e);     }       /**      *  向数组第一位添加元素      */     public void addFirst(E e){         add(0,e);     }       /**      *  在指定索引处添加元素      */     public void add(int index,E e){         //数组是否存满         if(size == data.length){             throw new IllegalArgumentException("Array space is exhausted");         }         //索引非法         if(index <0 || index > data.length){             throw new ArrayIndexOutOfBoundsException("Array index out of range: " + index);         }         //搬移数据         for (int i=size -1;i >= index;i--){             data[i + 1] = data[i];         }         data[index] = e;         size ++;     }       /**      *  获取指定索引处的值      */     public E get(int index){         //索引非法         if(index < 0 || index > data.length){             throw new ArrayIndexOutOfBoundsException("Array index out of range: " + index);         }         return data[index];     }       /**      *  修改指定索引处的值      */     public void set(int index,E e){         //索引非法         if(index <0 || index > data.length){             throw new ArrayIndexOutOfBoundsException("Array index out of range: " + index);         }         data[index] = e;     }       /**      *  删除指定索引处的值      */     public void remove(int index){         //索引非法         if(index <0 || index > data.length){             throw new ArrayIndexOutOfBoundsException("Array index out of range: " + index);         }         //数据搬移         for (int i = index + 1 ; i < size  ; i++) {             data[i-1] = data[i ];         }         //将最后一个元素的值设置为null         data[size -1 ] = null;         size --;     }       /**      *  删除某一个元素      */     public boolean removeElement(E e){         //调用查找方法，寻找元素的索引         //只删除找到的第一个         int i = find(e);         //找到则执行删除操作         if(i != -1){             remove(i);             return true;         }         return false;     }       /**      *  查询数组中是否包含某个值      *  包含返回true，否则返回false      */     public boolean contains(E e){         for (int i = 0; i < data.length; i++) {             if(data[i].equals(e)){                 return true;             }         }         return false;     }       /**      *  查找指定内容的索引      *  如果未找到，返回-1      */     public int find(E e){         for (int i = 0; i < data.length; i++) {             if(data[i].equals(e)){                 return i;             }         }         return -1;     }         /**      * 重写toString 方便打印      */     @Override     public String toString() {         StringBuilder sb = new StringBuilder();         sb.append(String.format("Array: size=%d ,capacity=%d \n",size,data.length));         sb.append("[");         for (int i=0;i<size;i++){             sb.append(data[i]);             if(i != size -1 ){                 sb.append(" , ");             }         }         sb.append("]");         return sb.toString();     }   }

测试代码

[Java] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

/**  * @Description  自定义数组测试类  * @Date 2018/12/22 22:28  * @Version 1.0  **/ public class CustomArrayTest {       public static void main(String[] args) {         CustomArray<Integer> customArray = new CustomArray();         for (int i = 0; i < customArray.getCapacity(); i++) {             //向数组末尾插入元素             customArray.addLast(i );         }         //测试删除         customArray.remove(2);         //测试指定索引添加         customArray.add(9,10);         //测试查找         System.out.println("查找结果: " + customArray.find(5 ));         //测试获取指定索引的值         System.out.println("指定索引位置的值: " + customArray.get(5 ));         //测试包含         System.out.println("数组中是否包含这个元素: " + customArray.contains(6));         //打印输出数组元素         System.out.println(customArray);     } }

czg52225

我很赞同！

Wmizi

有时候觉得数组很简单，有时候又会觉得数组是个神奇的东西，楼主加油哦，Java对我来说实在是不想看，我还是乖乖的看我的python吧

另虫

可以参考工厂模式写的；