数组、数组的基础实现及常见操作复杂度分析

Alleria Windrunner 2019-11-17

382

数组

数组是存储在连续内存位置的项的集合。其目的是用来连续存储多个相同类型的项。这样，只需要简单的向基础值添加偏移量，即可轻松的计算出每个元素的位置。数组的第一个元素的内存位置（通常由数组的名称表示）。

上图可视为楼梯的顶层视图，你位于楼梯底部。每个元素都可以由数组中的索引唯一标识。

数组的基础实现

数组是一组由公用名称引用的类似类型变量。Java中的数组的工作方式与C/C++的工作方式不同。以下是有关Java数组的一些重要要点：

在Java中，所有数组都是动态分配的。
由于数组是 Java 中的对象，因此我们可以使用成员长度来查找它们的长度。但是在C/C++ 中，我们使用大小查找长度。
Java 数组变量也可以像其它数据类型之后具有[]的变量一样声明。
数组中的变量是有序的，每个变量都有一个从 0 开始的索引。
Java 数组可以用作静态字段、局部变量或方法参数。
数组的大小必须由整形int 值指定，不能是长整形long或短整形 short。
数组类型的直接超类是 Object。
每种数组类型都实现了Cloneable 和 java.io.Serializable接口。

数组可以包含基元数据类型以及类的对象，具体取决于数组的定义。对于基元数据类型，实际值存储在连续的内存位置。对于类的对象，实际对象存储在堆的段中。

创建、初始化，访问数组

一维数组

一维数组声明的一般形式如下：

type var-name[];
OR
type[] var-name;
复制

数组的声明由两部分组成：类型和名称。类型表示数组中组成元素的数据类型。元素类型确定包含数组的每个元素的数据类型。与 int 类型的数组一样，我们还可以创建其他基元数据类型（如字符、浮点、双精度）的数组等或用户定义的数据类型（类的对象）。因此，数组的元素类型确定数组将持有哪种类型的数据类型。例如：

// 两种声明方式都是有效的
int intArray[]; 
or int[] intArray;


byte byteArray[];
short shortsArray[];
boolean booleanArray[];
long longArray[];
float floatArray[];
double doubleArray[];
char charArray[];


// 用户自定义MyClass类型的数组 
MyClass myClassArray[];


Object[]  ao,        // 对象数组
Collection[] ca;  // 集合数组
复制

尽管第一种方式声明确定了 intArray 是数组变量这一事实，但实际上不存在任何数组。它只是告诉编译器此（intArray）变量将包含整数类型的数组。要将 intArray 与实际的物理整数数组链接，必须使用 new 创建一个 intArray 并将其赋值给 intArray。

在Java中初始化数组

声明数组时，仅创建数组的引用。要实际创建或为数组提供内存，请按如下所示：一维数组的创建方式如下：

int intArray[];    //声明数组
intArray = new int[20];  // 分配内存给数组
复制

int[] intArray = new int[20]; // 两者一起声明
复制

注意：

由 new 分配的数组中的元素将自动初始化为零（对于数字类型）、false（对于布尔值）或 null（对于引用类型）。
获取数组是一个两步过程。首先，必须声明所需数组类型的变量。其次，必须分配将持有数组的内存，使用 new，并将其分配给数组变量。因此，在 Java 中，所有数组都是动态分配的。

数组书面量

在数组的大小和数组的变量已知的情况下，可以使用字面量的方式声明数组。

int[] intArray = new int[]{ 1,2,3,4,5,6,7,8,9,10 }; 
 // Declaring array literal
复制

此数组的长度确定所创建的数组的长度。
无需在最新版本的 Java 中使用new int[] 的方式声明数组。

使用for循环访问Java数组元素

数组中的每个元素都通过其索引进行访问。索引以 0 开头，以（总数组大小）-1 结束。可以使用 Java for Loop 访问数组的所有元素。

for (int i = 0; i < arr.length; i++)
  System.out.println("Element at index " + i + 
                                " : "+ arr[i]);
复制

对象数组

创建对象数组就像以以下方式创建基元类型数据项数组一样。

Student[] arr = new Student[7]; //student 是用户自定义的类
复制

数组越界

如果我们尝试访问数组大小以外的元素，会发生什么情况？JVM 会抛出ArrayIndexOutBoundsException异常，以表示数组已使用非法索引进行访问。异常抛出的索引一般为负或大于或等于数组大小。例如：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2
    at XXX.main(File.java:12)
复制

多维数组

多维数组是包含其他数组引用的数组的每个元素的数组。这些也称为锯齿数组。通过附加每个维度的一组方括号（[]）来创建多维数组。例如：

int[][] intArray = new int[10][20]; 二纬数组
int[][][] intArray = new int[10][20][10]; 三纬数组
复制

将数组传递给方法

与变量一样，我们也可以将数组传递给方法。例如，下面的程序将数组传递给方法sum，用于计算数组值的总和。

// Java program to demonstrate 
// passing of array to method


class Test 
{   
  // Driver method 
  public static void main(String args[]) 
  { 
    int arr[] = {3, 1, 2, 5, 4}; 
    
    // passing array to method m1 
    sum(arr); 
  
  }


  public static void sum(int[] arr) 
  { 
    // getting sum of array values 
    int sum = 0; 
    
    for (int i = 0; i < arr.length; i++) 
      sum+=arr[i]; 
    
    System.out.println("sum of array values : " + sum); 
  } 
}
复制

从方法返回数组

与往常一样，方法也可以返回数组。例如，下面的程序从方法 m1 返回数组。

// Java program to demonstrate 
// return of array from method


class Test 
{   
  // Driver method 
  public static void main(String args[]) 
  { 
    int arr[] = m1(); 
    
    for (int i = 0; i < arr.length; i++) 
      System.out.print(arr[i]+" "); 
  
  }


  public static int[] m1() 
  { 
    // returning array 
    return new int[]{1,2,3}; 
  } 
}
复制

数组的类对象

每个数组都有一个关联的 Class 对象，与具有相同组件类型的所有其他数组共享。例如:

// Java program to demonstrate 
// Class Objects for Arrays


class Test 
{ 
  public static void main(String args[]) 
  { 
    int intArray[] = new int[3]; 
    byte byteArray[] = new byte[3]; 
    short shortsArray[] = new short[3]; 
    
    // array of Strings 
    String[] strArray = new String[3]; 
    
    System.out.println(intArray.getClass()); 
    System.out.println(intArray.getClass().getSuperclass()); 
    System.out.println(byteArray.getClass()); 
    System.out.println(shortsArray.getClass()); 
    System.out.println(strArray.getClass()); 
  } 
}
复制

解释:

字符串"[I"是int类型的数组运行时类对象类型签名。
任何数组类型的直接超类是唯一的 java.lang.Object。
字符串"[B"是byte类型的数组运行时类对象类型签名。
字符串"[S"是byte类型的数组运行时类对象类型签名。
字符串"[L"是byte类型的数组运行时类对象类型签名。

数组的克隆

克隆单维数组（如 Object[]）时，使用包含原始数组元素副本而不是引用的新数组执行"深度复制"。

// Java program to demonstrate 
// cloning of one-dimensional arrays


class Test 
{   
  public static void main(String args[]) 
  { 
    int intArray[] = {1,2,3}; 
    
    int cloneArray[] = intArray.clone(); 
    
    // will print false as deep copy is created 
    // for one-dimensional array 
    System.out.println(intArray == cloneArray); 
    
    for (int i = 0; i < cloneArray.length; i++) { 
      System.out.print(cloneArray[i]+" "); 
    } 
  } 
}
复制

但是，多维数组的克隆（如 Object[][]）是一个"浅拷贝"，也就是说，它只创建一个新数组，每个元素数组都引用原始元素数组，但子数组是共享的。

// Java program to demonstrate 
// cloning of multi-dimensional arrays


class Test 
{   
  public static void main(String args[]) 
  { 
    int intArray[][] = {{1,2,3},{4,5}}; 
    
    int cloneArray[][] = intArray.clone(); 
    
    // will print false 
    System.out.println(intArray == cloneArray); 
    
    // will print true as shallow copy is created 
    // i.e. sub-arrays are shared 
    System.out.println(intArray[0] == cloneArray[0]); 
    System.out.println(intArray[1] == cloneArray[1]); 
    
  } 
}
复制

常见操作复杂度分析

查找(访问)元素

因为对于数组来说，数组里面的每个元素在初始化的时候就分配好了内存地址，所以查找(访问)数组元素的时间复杂度为O(1)。

增加元素

对于元素额增加，如果在数组的中间位置要插入一个元素，那么插入之后位置的所有元素都要向后移动，所以平均来说增加元素的时间复杂度为O(n)。

删除元素

和增加元素类似，删除元素的平均复杂度也为O(n)。

那怎么解决数组的这些问题呢？嗯，我们的一些科学家前辈就发明了链表这种数据结构，详见下篇《链表、链表的基础实现及常见操作复杂度分析》。

数据库

文章转载自Alleria Windrunner，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数组、数组的基础实现及常见操作复杂度分析

评论