Java数据结构之数组学习心得

科技 07-11 来源： JAVA小学生

最近在学习Java的数据结构，Java中的数据结构主要包含了数组、链表、队列、堆、栈、二叉树等等。感觉学习一下这些数据结构以及对应操作这些数据结构的算法，在后续的学习工作中，对基础知识的理解，或者在编程时能更好的优化性能还是有很大帮助的。本文对于想回炉巩固Java基础知识和想从基础开始学习Java数据结构的朋友会有所帮助。
本文只对以上数据结构中的简单类型做阐述，例如数组，文章只描述一维数组，对复杂的多位数组暂不作描述。

一、基本概念

Java数组属于对象类型，所以创建数组时要使用new关键字。即变量是数组的引用，存在内存栈中，具体数据是对象，存在内存堆中。栈中的变量引用了堆中对象的地址。

以下两种方式都可以创建和初始化一个数组，两种方式是等价的。都相当于在内存中new了一块空间来存储数组数据。

int[] array = {1,2,3,4,5,6,7,8,9,10};
下面的创建和初始化方式中，一旦定义了中括号中的数组大小，这个数组长度就不可变了。
Java中ArrayList的底层实现也使用了数组，但ArrayList的大小是可变的。有兴趣的朋友可以翻看一下ArrayList的代码实现。每次数组动态增加的长度是原来的1.5倍。这里不多说。
int[] array = new int[10];
array[0] = 1;
array[1] = 2;
...
array[9] = 10;

建议把中括号放在类型后，而不是放在变量名后。这样可以清楚的说明数组类型是类型的一部分而不是变量的一部分（有点拗口）。

一个对象数组中某个元素的对象值可以为null。

相关算法

对数组的操作简单说就几种，分别是：查找元素、删除元素和插入元素。对于数组本身又分为有序数组和无序数组两种。

在说各个算法之前先把部分代码列出，后续补充具体方法的内容。

public class Array {
 //成员变量，定义数组
 private Integer[] array;
 // 成员变量，数组元素个数
 private int elems;
 /**
 * 数组构造函数
 * @param max
 */
 public Array(int max) {
 array = new Integer[max];
 elems = 0;
 }
 /**
 * 判断value在数组中是否存在
 * @param value
 * @return 返回对应元素的下标，如果没找到返回-1
 */
 public int find(Integer value) {
 // do something
 }
 /**
 * 插入元素
 * @param value
 */
 public void insert(Integer value) {
 // do something 
 }
 /**
 * 删除元素
 * @param value
 * @return 删除掉返回true，否则返回false
 */
 public boolean delete(Integer value) {
 // do something 
 }
}

无序数组

查找：线性查找，遍历整个数组，将匹配项返回。

/**
 * 判断value在数组中是否存在
 * @param value
 * @return 返回对应元素的下标，如果没找到返回-1
 */
 public int find(Integer value) {
 // 循环整个数组，如果找到直接返回下标
 for (int i = 0; i < elems; i++) {
 if (array[j] == value) {
 return j;
 }
 // 如果j是元素的总个数，说明没找到
 return -1;
 }

删除：先找到要删除元素对应的下标，将匹配项后的元素前移。

/**
 * 删除元素
 * @param value
 * @return 删除掉返回true，否则返回false
 */
 public boolean delete(Integer value) {
 int index = find(value);
 // index是-1，说明没找到
 if (index == -1) {
 return false;
 } else {
 // 找到后，将后面的元素前移
 for (int k = index; k < elems; k++) {
 array[k] = array[k + 1];
 }
 elems--;
 return true;
 }
}

插入：直接插入到数组的最后一位。

/**
 * 插入元素
 * @param value
 */
 public void insert(Integer value) {
 array[elems] = value;
 elems++;
 }

有序数组

查找：二分查找（折半查找），有重复元素，返回最后一个匹配元素的下标。

public int find(Integer searchKey) {
 //开始下标
 int start = 0;
 //结束下标
 int end = elems - 1;
 while (start <= end) {
 //中间索引元素
 int middle = (start + end) / 2;
 if (array[middle] > key) {
 end = middle - 1;
 } else if (array[middle] < key) {
 start = middle + 1;
 } else {
 return middle;
 }
 }
 return -1;
}

删除：利用以上二分查找到得到的下标值，将该下标后的元素前移。

/**
 * 删除元素
 * @param value
 * @return 删除掉返回true，否则返回false
 */
 public boolean delete(long value) {
 // 查找值是value元素的数组下标
 int j = find(value);
 // 如果下标是数组长度，说明未找到。如：数组长度是10，则最大下标值应为9.如果返回的是10.说明没找到。
 if (j == elems) {
 return false;
 } else {
 // 删除的元素后面的元素前移
 for (int k = j; k < elems; k++) {
 array[k] = array[k + 1];
 }
 // 数组元素个数减一
 elems--;
 return true;
 }
}

插入：利用以上二分查找得到的下标值，将该下标后的元素后移，并将该元素赋给找到的下标位置。

/**
 * 插入一个元素
 * @param value
 */
public void insert(Integer value) {
 int i;
 // 循环数组所有元素，当找到某元素比value大时，说明此处是插入该值的位置。则break。此时i即为要插入的位置。
 for (i = 0; i < elems; i++) {
 if (array[i] > value) {
 break;
 }
 }
 // 从数组长度开始向前循环，将i值后面的元素后移
 for (int k = elems; k > i; k--) {
 array[k] = array[k - 1];
 }
 // 将value插入到i位置
 array[i] = value;
 // 数组元素个数加一
 elems++;
}