线性表
线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。
前驱元素： 若A元素在B元素的前面，则称A为B的前驱元素。
后继元素： 若B元素在A元素的后面，则称B为A的后继元素。
线性表的特征：
-
第一个数据元素没有前驱，这个数据元素被称为头结点；
-
最后一个数据元素没有后继，这个数据元素被称为尾结点；
-
除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
如果把线性表用数学语言来定义，则可以表示为(a1,...ai-1,ai,ai+1,...an)，ai-1领先于ai，ai领先于ai+1，称ai-1是ai的前驱元素，ai+1是ai的后继元素。
线性表的分类：线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。
顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
顺序表实现
API设计
类名：SequenceList
构造方法
SequenceList(int capacity)：创建容量为capacity的SequenceList对象
成员方法
public void clear()：空置线性表
public boolean isEmpty()：判断线性表是否为空，是返回true，否返回false
public int length()：获取线性表中元素的个数
public E get(int i)：读取并返回线性表中的第i个元素的值
public void insert(int i,E e)：在线性表的第i个元素之前插入一个值为e的元素
public void insert(E e)：向线性表中添加一个元素e
public E remove(int i)：删除并返回线性表中第i个数据元素
public int indexOf(E e)：返回线性表中首次出现的指定的数据元素的位序号，若不存在返回-1
成员变量
private E[] eles：存储元素的数组
private int length：当前线性表的长度
代码实现
public class SequenceList<E> {
//存储元素的数组
private Object[] eles;
//当前线性表的长度
private int length;
public SequenceList(int capacity) {
// 如果传入的个数小于1，则默认为1
if(capacity < 1) {
capacity = 1;
}
// 构造一个长度为capacity的顺序表
eles = new Object[capacity];
length = 0;
}
//空置线性表
public void clear() {
length = 0;
// 将数据整个置空
eles = new Object[eles.length];
}
//判断线性表是否为空，是返回true，否返回false
public boolean isEmpty() {
return length == 0;
}
//获取线性表中元素的个数
public int length() {
return length;
}
//读取并返回线性表中的第index个元素的值
public E get(int index) {
// 判断一下下标是否合法
if (index < 0 || index >= length) {
throw new RuntimeException("当前元素不存在");
}
return (E) eles[index];
}
//在线性表的第i个元素之前插入一个值为e的元素
public void insert(int index, E e) {
if (length == eles.length) {
throw new RuntimeException("当前表已满");
}
if (index >= eles.length) {
throw new RuntimeException("下标位置非法");
}
// 判断一下index是否合法
if (index < 0 || index > length) {
throw new RuntimeException("下标位置非法");
}
// 把index位置空出来，index位置以及后面的元素依次向后移动一位
for (int i = length; i > index; i--) {
eles[i] = eles[i - 1];
}
// 把v放到index处
eles[index] = length;
length++;
}
//向线性表中添加一个元素e
public void insert(E e) {
// 判断一下元素个数是否已经超过了数组的最大容量
if (length == eles.length) {
throw new RuntimeException("当前表已满");
}
eles[length++] = e;
}
//删除并返回线性表中第index个数据元素
public E remove(int index) {
if (index < 0 || index >= length) {
throw new RuntimeException("当前要删除的元素不存在");
}
// 获取要删除的元素
E result = (E) eles[index];
// 把index后面的元素都向前移动一格
for (int i = index; i < length - 1; i++) {
eles[i] = eles[i + 1];
}
// 元素个数-1
length--;
return result;
}
//返回线性表中首次出现的指定的数据元素的位序号(索引位置)，若不存在返回-1
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < length; i++)
if (eles[i] == null)
return i;
} else {
for (int i = 0; i < length; i++)
if (o.equals(eles[i]))
return i;
}
return -1;
}
}
可变容量的顺序表
在之前的实现中，当我们使用SequenceList时，先new SequenceList(5) 创建一个对象，创建对象时就需要指定容器的大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了5个元素，还要继续插入数据，则会报错，不能再插入。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该考虑它的容量的伸缩性。考虑容器的容量伸缩性，其实就是改变存储数据元素的数组的大小。
添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个是原数组两倍容量的新数组存储元素。
移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的1/2的新数组存储元素。
//在线性表的第i个元素之前插入一个值为e的元素
public void insert(int index, E e) {
// 判断一下index是否合法
if (index < 0 || index > length) {
throw new RuntimeException("下标位置非法");
}
if (length == eles.length) {
resize(eles.length * 2);
}
// 把index位置空出来，index位置以及后面的元素依次向后移动一位
for (int i = length; i > index; i--) {
eles[i] = eles[i - 1];
}
// 把v放到index处
eles[index] = length;
length++;
}
//向线性表中添加一个元素e
public void insert(E e) {
// 判断一下元素个数是否已经超过了数组的最大容量
if (length == eles.length) {
resize(eles.length * 2);
}
eles[length++] = e;
}
//删除并返回线性表中第index个数据元素
public E remove(int index) {
if (index < 0 || index >= length) {
throw new RuntimeException("当前要删除的元素不存在");
}
// 获取要删除的元素
E result = (E) eles[index];
// 把index后面的元素都向前移动一格
for (int i = index; i < length - 1; i++) {
eles[i] = eles[i + 1];
}
// 元素个数-1
length--;
// 判断一下当前元素数量已经不足数组大小的1/4，则重置数组大小
if (length > 0 && length < eles.length / 4) {
resize(eles.length / 2);
}
return result;
}
//将现有的数组改变为容量为newSize的新数组
private void resize(int newSize) {
// 记录旧数组
Object[] temp = eles;
// 创建新数组
eles = new Object[newSize];
// 把就旧组中的元素拷贝到新数组
for (int i = 0; i < length; i++) {
eles[i] = temp;
}
}
时间复杂度
get(i)：不难看出，不论数据元素量N有多大，只需要一次eles[i]就可以获取到对应的元素，所以时间复杂度为O(1)；
insert(int i,E e)：每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂为O(n)；
remove(int i)：每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大，移动的元素也越多，时间复杂度为O(n)；由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显。
评论区