自已编写一个Java数组
本帖最后由 孤云 于 2018-12-23 00:03 编辑前言：
最近开始学习数据结构，刚学到数组，写下此篇博客记录下学习内容。如文中有不对的地方还请大佬指出。正文：
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制作的，有点丑。
https://img-blog.csdnimg.cn/2018122222544155.png
https://img-blog.csdnimg.cn/20181222225559563.png
查询:数组查询需要遍历，遍历需要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_address = 1024 + 3 * 4；就是下标3的内存地址了。
5.下面开始用代码实现一个自已的数组，我使用的是Java语言编写的。
/**
* @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;
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 = data;
}
data = e;
size ++;
}
/**
*获取指定索引处的值
*/
public E get(int index){
//索引非法
if(index < 0 || index > data.length){
throw new ArrayIndexOutOfBoundsException("Array index out of range: " + index);
}
return data;
}
/**
*修改指定索引处的值
*/
public void set(int index,E e){
//索引非法
if(index <0 || index > data.length){
throw new ArrayIndexOutOfBoundsException("Array index out of range: " + index);
}
data = 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 = data;
}
//将最后一个元素的值设置为null
data = 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.equals(e)){
return true;
}
}
return false;
}
/**
*查找指定内容的索引
*如果未找到，返回-1
*/
public int find(E e){
for (int i = 0; i < data.length; i++) {
if(data.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);
if(i != size -1 ){
sb.append(" , ");
}
}
sb.append("]");
return sb.toString();
}
}
测试代码
/**
* @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);
}
}
我很赞同！ 有时候觉得数组很简单，有时候又会觉得数组是个神奇的东西，楼主加油哦，Java对我来说实在是不想看，我还是乖乖的看我的python吧 可以参考工厂模式写的；
页:
[1]