线性表的定义

线性表(List)：零个或多个数据元素的有限序列。

若将线性表记为 (a1,...,ai-1,ai,ai+1,...an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素，a1没有前驱，an没有后继，如图：

所以线性表元素个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。

线性表的抽象数据类型

我们刚刚已经给出线性表的定义了，现在分析一下，线性表应该有一些什么样的操作呢？

除了基本的插入和删除数据，应该还需要获取长度等一系列操作，取决于你的应用。于是我们可以定义一个这样的接口：

/**
 * 线性表抽象数据模型
 */
public interface MyList<E> {
	
	/**
     * 清空线性表
     */
    void clean();
	
    /**
     * 获取线性表的元素个数
     */
    int size();
    
    /**
     * 判断线性表是否为空
     */
    boolean isEmpty();
    
    /**
     * 添加元素
     */
    void add(E elem);
    
    /**
     * 指定位置插入元素
     *
     * @param index 插入位置
     * @param elem  插入元素
     */
    void insert(int index, E elem);
    
    /**
     * 获取指定位置的元素
     *
     * @param index 查找位置
     * @return 位置对应的元素
     */
    E get(int index);
    
    /**
     * 删除该列表中指定位置的元素
     * @param index
     * @return
     */
    E remove(int index);
    
    /**
     * 获取指定位置的元素
     *
     * @param index 查找位置
     * @return 位置对应的元素
     */
    int indexOf(E elem);
}

线性表的顺序存储实现

1. 顺序存储的定义

线性表的数据存储结构，是指用一段地址连续的存储单元依次存储线性表占用的各个数据元素的存储结构。

顺序存储的特点：

• 逻辑上相邻的数据元素，在物理存储位置上也是相邻的。

• 存储密度高，事先需要分配足够应用的存储空间。

• 随机存取，查询速度快，直接访问地址单元中的数据。时间复杂度 O(1)

• 插入删除操作会引起大量的数据移动，时间复杂度O(n)

2. 顺序表的结构类描述

最简单的顺序存储线性表是数组。而Java JDK中有ArrayList很好的实现了顺序存储，ArrayList 的底层是数组队列，相当于动态数组，与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量，下面模仿ArrayList实现线性表的顺序存储结构：

import java.util.Arrays;

/**
 * 线性表的顺序存储实现
 * 
 */
public class SequenceList<E> implements MyList<E> {

	/**
	 * 默认初始容量大小
	 */
	private static final int DEFAULT_CAPACITY = 10;

	/**
	 * 空数组（用于空实例）。
	 */
	private static final Object[] EMPTY_ELEMENTDATA = {};

	// 用于默认大小空实例的共享空数组实例。
	// 我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	/**
	 * 保存数据的数组
	 */
	transient Object[] elementData;

	/**
	 * 要分配的最大数组大小
	 */
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

	/**
	 * 所包含的元素个数
	 */
	private int size;
    
    /**
	 * 带初始容量参数的构造函数。（用户自己指定容量）
	 */
	public SequenceList(int initialCapacity) {
		if (initialCapacity > 0) {
			// 创建initialCapacity大小的数组
			this.elementData = new Object[initialCapacity];
		} else if (initialCapacity == 0) {
			// 创建空数组
			this.elementData = EMPTY_ELEMENTDATA;
		} else {
			throw new IllegalArgumentException("初始容量数据不合法:" + initialCapacity);
		}
	}

	/**
	 * 默认构造函数，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组
	 * 当添加第一个元素的时候数组容量才变成10
	 */
	public SequenceList() {
		this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	}

	/**
	 * 保证内部数组容量
	 * 
	 * @param minCapacity
	 */
	private void ensureCapacityInternal(int minCapacity) {
		// 得到最小扩容量
		if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
			minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
		}
		// 判断是否需要扩容
		ensureExplicitCapacity(minCapacity);
	}

	/**
	 * 判断是否需要扩容，如果需要，调用grow方法进行扩容
	 * 
	 * @param minCapacity
	 */
	private void ensureExplicitCapacity(int minCapacity) {
		if (minCapacity - elementData.length > 0) {
			// 调用grow方法进行扩容，调用此方法代表已经开始扩容了
			grow(minCapacity);
		}
	}

	/**
	 * 扩容的核心方法。
	 */
	private void grow(int minCapacity) {
		// oldCapacity为旧容量，newCapacity为新容量
		int oldCapacity = elementData.length;

		// 将oldCapacity 右移一位，其效果相当于oldCapacity /2，
		// 我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		// 然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量
		if (newCapacity - minCapacity < 0)
			newCapacity = minCapacity;

		// 再检查新容量是否超出了定义的最大容量
		// 如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Interger.MAX_VALUE，否则，新容量大小则为
		// MAX_ARRAY_SIZE。
		if (newCapacity - MAX_ARRAY_SIZE > 0) {
			newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
		}
		// 调用copyOf方法创建新数组，并将原数组元素拷贝过去
		elementData = Arrays.copyOf(elementData, newCapacity);
	}

	/**
	 * 清空此列表
	 */
	@Override
	public void clean() {
		for (int i = 0; i < size; i++) {
			elementData[i] = null;
		}
		size = 0;

	}

	/**
	 * 返回此列表中的元素数
	 */
	@Override
	public int size() { return size; }

	/**
	 * 返回此列表是否为空
	 */
	@Override
	public boolean isEmpty() { return size == 0; }

	/**
	 * 将指定的元素追加到此列表的末尾
	 */
	@Override
	public void add(E elem) {
		ensureCapacityInternal(size + 1);
		// 添加元素的实质就相当于为数组赋值
		elementData[size++] = elem;
	}

	/**
	 * 在此列表中的指定位置插入指定的元素 先调用 rangeCheckForAdd 对index进行界限检查；然后调用
	 * ensureCapacityInternal 方法保证capacity足够大；
	 * 再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
	 */
	@Override
	public void insert(int index, E elem) {
		// 对index进行界限检查
		rangeCheckForAdd(index);
		// 扩容检查
		ensureCapacityInternal(size + 1);
		// arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己
		System.arraycopy(elementData, index, elementData, index + 1, size - index);
		elementData[index] = elem;
		size++;
	}

	/**
	 * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）
	 */
	@Override
	public E remove(int index) {
		// 对index进行界限检查
		rangeCheck(index);
		// 获取从列表中删除的元素
		E oldValue = elementData(index);

		int numMoved = size - index - 1;
		if (numMoved > 0) {
			// 与insert一样是自己复制自己
			System.arraycopy(elementData, index + 1, elementData, index, numMoved);
		}
		elementData[--size] = null;
		// 从列表中删除的元素
		return oldValue;
	}

	/**
	 * 返回此列表中指定位置的元素
	 */
	@Override
	public E get(int index) {
		rangeCheck(index);

		return elementData(index);
	}

	/**
	 * 返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为-1
	 */
	@Override
	public int indexOf(E elem) {
		if (elem == null) {
			for (int i = 0; i < size; i++) {
				if (elementData[i] == null) return i;
			}
		} else {
			for (int i = 0; i < size; i++) {
				if (elem.equals(elementData[i])) return i;
			}
		}
		return -1;
	}

	/**
	 * 返回此列表中指定位置的元素
	 */
	@SuppressWarnings("unchecked")
	E elementData(int index) {
		return (E) elementData[index];
	}

	/**
	 * 检查给定的索引是否在范围内。
	 */
	private void rangeCheck(int index) {
		if (index >= size)
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
	}

	/**
	 * 检查数组下标是否越界
	 */
	private void rangeCheckForAdd(int index) {
		if (index > size || index < 0)
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
	}

}

稀疏数组

1. 稀疏数组定义

如果一个数组(包括多维数组)中的大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组，节约空间。

一般来说，稀疏数组的处理方法是：

• 记录数组一共有几行几列，有多少个不同的数值。
• 把具有不同值的元素的行列及记录在一个小规模的数组中，从而缩小程序的规模。

如图所示，一般来说，第一行存取几行几列以及几个数值。

2. 稀疏数组应用

在编写的五子棋程序中，有存盘和续上盘的功能。

由于此时，棋盘中的棋子的坐标符合大多数元素为0的情况，所以我们可以构建一个稀疏数组来表示这道题。 那么我们可以得到二维数组转稀疏数组的思路

• 遍历二维数组，得到有效个数sum。
• 根据sum就可以创建稀疏数组sparseArr int[sum+1][3]
• 将二维数组的有效数据存入稀疏数组。

转化成稀疏数组后，还必须有可以从新恢复原来的二维数组，思路为：

• 先读取稀疏数组第一行，根据第一行的数据，创建原始的二维数组
• 读取稀疏数组后几行的数据，并赋给原始数组即可

代码实现：

import java.util.Arrays;

public class SparseArrayUtil {

	/**
	 * 将二维数组转化为稀疏数组
	 * 
	 * @param srcArray
	 * @return
	 */
	public static int[][] transform(int[][] srcArray) {
		int sum = 0;
		// 1.先遍历二维数组，得到非0的数据个数
		for (int i = 0; i < 11; i++) {
			for (int j = 0; j < 11; j++) {
				if (srcArray[i][j] != 0) {
					sum++;
				}
			}
		}
		// 2.创建对应的稀疏数组
		int[][] sparseArr = new int[sum + 1][3];
		// 3.第一行存取行数列数及非0数据个数
		sparseArr[0][0] = 11;
		sparseArr[0][1] = 11;
		sparseArr[0][2] = sum;
		// 3.遍历二维数组，将非0的值存放到sparseArr
		int count = 0;
		for (int i = 0; i < 11; i++) {
			for (int j = 0; j < 11; j++) {
				if (srcArray[i][j] != 0) {
					count++;
					sparseArr[count][0] = i;
					sparseArr[count][1] = j;
					sparseArr[count][2] = srcArray[i][j];
				}
			}
		}
		return sparseArr;
	}

	/**
	 * 将稀疏数组恢复成原始二维数组
	 * 
	 * @param sparseArr
	 * @return
	 */
	public static int[][] reduction(int[][] sparseArr) {
		// 1.先读取第一行，根据第一行的数据，创建原始的二位数据
		int[][] chessArray = new int[sparseArr[0][0]][sparseArr[0][1]];
		// 2.在读取稀疏数组后几行的数据，并赋给原始的二维数组
		for (int z = 1; z < sparseArr.length; z++) {
			chessArray[sparseArr[z][0]][sparseArr[z][1]] = sparseArr[z][2];
		}
		return chessArray;
	}

	public static void main(String[] args) {
		// 创建一个原始的二维数组。
		// 0代表没有棋子 1.代表黑子 2.蓝子
		int[][] chessArr1 = new int[11][11];

		chessArr1[1][2] = 1;
		chessArr1[2][5] = 1;
		chessArr1[3][2] = 2;
		chessArr1[5][4] = 1;
		chessArr1[4][5] = 2;
		// 输出原始的二位数组
		System.out.println("原始的二维数组为:");
		Arrays.stream(chessArr1).forEach(x -> {
			System.out.println(Arrays.toString(x));
		});

		int[][] sparseArr = SparseArrayUtil.transform(chessArr1);
		// 输出稀疏数组
		System.out.println("转化稀疏数组为:");
		Arrays.stream(sparseArr).forEach(x -> {
			System.out.println(Arrays.toString(x));
		});

		int[][] chessArr2 = SparseArrayUtil.reduction(sparseArr);
		// 输出稀疏数组
		System.out.println("还原原始数组为:");
		Arrays.stream(chessArr2).forEach(x -> {
			System.out.println(Arrays.toString(x));
		});

	}

}