线性表是数据结构中最基础、最重要的概念之一，而数组实现（顺序表）则是其实现方式中最为直观和高效的一种。
线性表的基本概念
什么是线性表
线性表（Linear List）是n个具有相同特性的数据元素的有限序列。在逻辑结构上，线性表呈现出一对一的线性关系，就像一条直线上的点，每个元素都有且仅有一个直接前驱和一个直接后继（除了首尾元素）。
线性表的存储方式
线性表在逻辑上是线性的，但在物理存储上可以有多种形式：
顺序存储：使用连续的存储空间（数组实现）
链式存储：使用不连续的存储空间通过指针连接（链表实现）
本文重点讨论顺序存储的实现方式。
顺序表的原理与特点
顺序表的本质
顺序表（Sequential List）是用一段物理地址连续的存储单元依次存储数据元素的线性结构，本质上就是数组，但增加了动态扩容和高级数据结构操作。
顺序表的核心特性
优点：
随机访问高效：通过下标访问元素，时间复杂度O(1)
存储密度高：不需要额外的指针空间
缓存友好：连续内存空间，CPU缓存命中率高
缺点：
插入删除低效：需要移动大量元素，时间复杂度O(n)
容量固定：需要预先分配空间或动态扩容
扩容代价高：扩容时需要复制所有元素
线性表ADT方法
我们主要实现以下方法
实现顺序表
我们也采用接口和实现分离的设计
实现接口层
package org.example;
/**
* @author nanak
*/
public interface SeqList<E> {
boolean add(E e);
boolean add(int i, E e);
E get(int i);
E set(int i, E e);
E remove(int i);
int indexOf(E e);
void clear();
int length();
}
实现接口
package org.example;
import java.util.Arrays;
/**
* @author nanak
*/
public class SeqListImpl<E> implements SeqList<E>{
private Object[] data;
private int count;
public SeqListImpl() {
this(10);
}
public SeqListImpl(int initialCapacity) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException("初始容量必须>0: " + initialCapacity);
}
this.data = new Object[initialCapacity];
}
@Override
public boolean add(E e) {
if (this.count==this.data.length) {
grow();
}
data[this.count]=(Object) e;
this.count++;
return true;
}
@Override
public boolean add(int i, E e) {
if (i < 0 || i > this.count) {
throw new IndexOutOfBoundsException(
"索引越界：当前大小=" + this.count + "，传入索引=" + i
);
}
if (this.count == data.length) {
grow();
}
System.arraycopy(data, i, data, i + 1, this.count - i);
data[i] = (Object) e;
this.count++;
return true;
}
@Override
public E get(int i) {
if (i < 0 || i >= this.count) {
throw new IndexOutOfBoundsException(
"索引越界：当前大小=" + this.count + "，传入索引=" + i
);
}
return (E) this.data[i];
}
@Override
public E set(int i, E e) {
E old = (E) this.data[i];
if (i < 0 || i >= this.count) {
throw new IndexOutOfBoundsException(
"索引越界：当前大小=" + this.count + "，传入索引=" + i
);
}
this.data[i] = (Object) e;
return old;
}
@Override
public E remove(int i) {
if (i < 0 || i >= this.count) {
throw new IndexOutOfBoundsException(
"索引越界：当前大小=" + this.count + "，传入索引=" + i
);
}
E temp = (E) this.data[i];
System.arraycopy(data, i + 1, data, i, count - i - 1);
this.count--;
return temp;
}
@Override
public int indexOf(E e) {
for (int i = 0; i < this.count; i++) {
if (this.data[i] == null && e == null) {
return i;
}
if (this.data[i].equals(e)) {
return i;
}
}
return -1;
}
@Override
public void clear() {
this.data = new Object[10];
this.count = 0;
}
@Override
public int length() {
return this.count;
}
public int getCapacity() {
return this.data.length;
}
private void grow() {
int oldCapacity = data.length;
// 扩容公式：原容量 + 原容量/2（位运算更高效）
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 数组拷贝：创建新数组并复制原数据
data = Arrays.copyOf(data, newCapacity);
}
}
进行测试
package org.example;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
/**
* SeqListImpl 测试类
*/
public class SeqListImplTest {
private SeqListImpl<String> seqList;
/**
* 每个测试方法执行前初始化空顺序表
*/
@BeforeEach
void setUp() {
seqList = new SeqListImpl<>();
}
/**
* 测试默认初始化容量（10）
*/
@Test
void testDefaultCapacity() {
assertEquals(10, seqList.getCapacity());
}
/**
* 测试自定义初始化容量
*/
@Test
void testCustomCapacity() {
SeqListImpl<Integer> list = new SeqListImpl<>(5);
assertEquals(5, list.getCapacity());
}
/**
* 测试初始化容量为负数时抛出异常
*/
@Test
void testNegativeCapacity() {
assertThrows(IllegalArgumentException.class, () -> new SeqListImpl<>(-3));
}
/**
* 测试尾插元素（add(E)）
*/
@Test
void testAddTail() {
// 插入3个元素
assertTrue(seqList.add("A"));
assertTrue(seqList.add("B"));
assertTrue(seqList.add("C"));
// 验证元素顺序和值
assertEquals("A", seqList.get(0));
assertEquals("B", seqList.get(1));
assertEquals("C", seqList.get(2));
// 验证当前元素个数（count）：需通过间接方式验证（比如越界）
assertThrows(IndexOutOfBoundsException.class, () -> seqList.get(3));
}
/**
* 测试扩容逻辑（原容量10，插入11个元素触发扩容）
*/
@Test
void testGrow() {
// 插入10个元素（填满初始容量）
for (int i = 0; i < 10; i++) {
seqList.add("test" + i);
}
assertEquals(10, seqList.getCapacity()); // 扩容前容量仍为10
// 插入第11个元素，触发扩容（10 -> 15）
seqList.add("growTest");
assertEquals(15, seqList.getCapacity()); // 扩容后容量变为15
assertEquals("growTest", seqList.get(10)); // 验证第11个元素插入成功
}
/**
* 测试指定位置插入元素（add(int, E)）
*/
@Test
void testAddByIndex() {
// 先插入基础元素
seqList.add("A");
seqList.add("C");
// 在索引1位置插入B
seqList.add(1, "B");
// 验证插入后顺序
assertEquals("A", seqList.get(0));
assertEquals("B", seqList.get(1));
assertEquals("C", seqList.get(2));
// 测试在头部插入
seqList.add(0, "HEAD");
assertEquals("HEAD", seqList.get(0));
// 测试在尾部插入（等同于add(E)）
seqList.add(4, "TAIL");
assertEquals("TAIL", seqList.get(4));
}
/**
* 测试指定位置插入越界（索引<0 或 索引>count）
*/
@Test
void testAddByIndexOutOfBounds() {
seqList.add("A"); // count=1
// 索引<0
assertThrows(IndexOutOfBoundsException.class, () -> seqList.add(-1, "X"));
// 索引>count（当前count=1，索引2越界）
assertThrows(IndexOutOfBoundsException.class, () -> seqList.add(2, "X"));
}
/**
* 测试修改元素（set(int, E)）
*/
@Test
void testSet() {
seqList.add("OLD");
// 修改索引0的元素
String oldValue = seqList.set(0, "NEW");
// 验证返回值为旧值
assertEquals("OLD", oldValue);
// 验证新值生效
assertEquals("NEW", seqList.get(0));
}
/**
* 测试修改元素越界
*/
@Test
void testSetOutOfBounds() {
seqList.add("A");
assertThrows(IndexOutOfBoundsException.class, () -> seqList.set(1, "X"));
assertThrows(IndexOutOfBoundsException.class, () -> seqList.set(-1, "X"));
}
/**
* 测试删除元素（remove(int)）
*/
@Test
void testRemove() {
seqList.add("A");
seqList.add("B");
seqList.add("C");
// 删除索引1的元素（B）
String removed = seqList.remove(1);
assertEquals("B", removed);
// 验证删除后元素移位
assertEquals("C", seqList.get(1));
// 验证删除后越界
assertThrows(IndexOutOfBoundsException.class, () -> seqList.get(2));
}
/**
* 测试删除元素越界
*/
@Test
void testRemoveOutOfBounds() {
seqList.add("A");
assertThrows(IndexOutOfBoundsException.class, () -> seqList.remove(1));
assertThrows(IndexOutOfBoundsException.class, () -> seqList.remove(-1));
}
/**
* 测试查找元素索引（indexOf(E)）
*/
@Test
void testIndexOf() {
seqList.add("A");
seqList.add("B");
seqList.add("A");
// 查找存在的元素（返回第一个匹配索引）
assertEquals(0, seqList.indexOf("A"));
assertEquals(1, seqList.indexOf("B"));
// 查找不存在的元素
assertEquals(-1, seqList.indexOf("C"));
// 查找null（需处理空指针，补充测试）
seqList.add(null);
assertEquals(3, seqList.indexOf(null));
}
/**
* 测试清空顺序表（clear）
*/
@Test
void testClear() {
seqList.add("A");
seqList.add("B");
seqList.clear();
// 验证清空后元素不可访问
assertThrows(IndexOutOfBoundsException.class, () -> seqList.get(0));
// 验证容量重置为默认0
assertEquals(0, seqList.length());
}
/**
* 测试get方法越界
*/
@Test
void testGetOutOfBounds() {
// 空表访问索引0
assertThrows(IndexOutOfBoundsException.class, () -> seqList.get(0));
// 访问负索引
assertThrows(IndexOutOfBoundsException.class, () -> seqList.get(-1));
}
}
全部通过