大话数据结构一：线性表的顺序存储结构

1. 线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。

2. Java实现线性表的顺序存储结构：

// 顺序存储结构
public class SequenceList {
	private static final int DEFAULT_SIZE = 10; // 默认初始化数组大小
	private int size; // 当前数组大小
	private static Object[] array;

	public SequenceList() {
		init(DEFAULT_SIZE);
	}

	public SequenceList(int size) {
		init(size);
	}

	// 初始化数组大小
	public void init(int size) {
		this.size = 0;
		array = new Object[size];
	}

	public void add(int index, Object obj) {
		checkSize(index);
		if (size == array.length) {// 判断size如果等于length, 说明原数组装满了
			Object[] newArray = new Object[array.length * 3 / 2 + 1];//创建一个更大的数组
			System.arraycopy(array, 0, newArray, 0, array.length);//将原有数据复制到新数组
			array = newArray; // array指向新数组
		}
		for (int j = size; j > index; j--) {
			array[j] = array[j - 1]; // 将要插入位置后的数据元素往后移动一位
		}
		array[index] = obj;
		size++;
	}

	// 删除一个元素
	public void remove(int index) {
		if (size == 0) {
			throw new RuntimeException("list已空");
		}
		checkSize(index);
		for (int j = index; j < size - 1; j++) {
			array[j] = array[j + 1];
		}
		size--;
	}

	// 通过索引获取元素
	public Object get(int index) {
		checkSize(index);
		return array[index];
	}

	// 显示所有元素
	public void display() {
		for (int i = 0; i < size; i++) {
			System.out.print(" " + array[i]);
		}
	}

	// 获取列表长度
	public int size() {
		return size;
	}

	// 列表是否为空
	public boolean isEmpty() {
		return size == 0;
	}

	private void checkSize(int index) {
		if (index < 0 || index > size) // 判断如果获取的index越界, 抛出异常
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
	}
}

// 测试程序
public class SequenceTest {
	public static void main(String[] args) {
		SequenceList seqList = new SequenceList();
		seqList.add(0, 1);
		seqList.add(1, 2);
		seqList.add(2, 3);
		seqList.add(3, 4);
		seqList.add(4, 5);
		seqList.add(5, 6);
		seqList.add(6, 7);
		seqList.add(7, 8);
		seqList.add(8, 9);
		seqList.add(9, 10);
		seqList.add(10, 11);
		seqList.add(11, 12);
		seqList.display();
		System.out.println();
		seqList.remove(1);
		seqList.display();
	}
}

3. 插入和删除的时间复杂度：

元素插入到第i个位置或者删除第i个元素，需要移动n-i个元素，根据概率原理，每个位置插入或删除元素的可能性是相同的，为（n-1）/ 2。平均的时间复杂度为O(n)

4. 线性表顺序存储的优缺点：

优点：无须为表中元素逻辑关系而增加额外的存储空间，同时可以快速存取表中任一位置的元素。

缺点：插入和删除操作需要移动大量的元素，当线性表长度变化较大时，难以确定存储空间的容量。