线性表是数据结构中最基础、最重要的概念之一，而链表实现则是其实现方式中的一种。
线性表的基本概念
什么是线性表
线性表（Linear List）是n个具有相同特性的数据元素的有限序列。在逻辑结构上，线性表呈现出一对一的线性关系，就像一条直线上的点，每个元素都有且仅有一个直接前驱和一个直接后继（除了首尾元素）。
线性表的存储方式
线性表在逻辑上是线性的，但在物理存储上可以有多种形式：
顺序存储：使用连续的存储空间（数组实现）
链式存储：使用不连续的存储空间通过指针连接（链表实现）
本文重点讨论顺序存储的实现方式。
链表的原理与特点
链表的本质
链表是一种非连续、非顺序的线性数据结构，其核心是通过「节点」存储数据，并通过节点中的「指针 / 引用」建立节点间的逻辑关系，从而模拟线性表的有序性。
链表的核心特性
一、单链表（基础款）
优点：
插入删除高效：找到目标节点后仅需修改指针指向，时间复杂度 O (1)（查找节点环节为 O (n)）
容量动态：无需预先分配固定内存空间，节点随数据增减动态创建 / 释放，长度无硬性限制
内存利用率高：非连续存储模式，可充分利用内存碎片，避免连续大内存块的浪费
缺点：
随机访问低效：无下标机制，访问第 n 个元素需从表头顺序遍历，时间复杂度 O (n)
存储密度低：每个节点需额外存储「后继指针（next）」，增加内存开销
缓存不友好：节点分散存储，CPU 缓存无法批量加载数据，命中率远低于数组
操作风险高：指针修改易引发空指针、死循环等问题，调试难度较大
二、双向链表（扩展款）
专属优点：
遍历灵活：同时维护「前驱指针（prev）」和「后继指针（next）」，支持正向 / 反向双向遍历
删除效率更高：删除节点时无需额外遍历查找前驱节点，直接通过 prev 指针定位，操作复杂度 O (1)
专属缺点：
指针开销翻倍：需同时维护两个指针，内存占用比单链表更高
插入 / 修改逻辑复杂：新增 / 删除节点时需同步更新前后节点的 prev 和 next 指针，代码逻辑复杂度提升
三、循环链表（特殊款）
专属优点：
无首尾边界：尾节点指针指向头节点，形成环形结构，适配环形遍历场景（如约瑟夫环、环形队列）
专属缺点：
易触发死循环：遍历过程若未设置终止条件，会无限循环遍历
首尾判断复杂：需额外标记或计数区分 “遍历完成”，增加业务逻辑复杂度
线性表ADT方法
我们主要实现以下方法
实现链表
我们也采用接口和实现分离的设计来实现一个单向链表
实现接口层
package org.example;
/**
* @author nanak
*/
public interface LinkList<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;
/**
* @author nanak
*/
public class LinkListImpl<E> implements LinkList<E> {
private Node<E> first;
private Node<E> last;
private int count = 0;
@Override
public boolean add(E e) {
// 采用尾插法
if (this.first == null) {
this.first = new Node<>(e, null);
this.count++;
this.last = this.first;
return true;
}
this.last.next = new Node<>(e, null);
this.last = this.last.next;
this.count++;
return true;
}
@Override
public boolean add(int i, E e) {
if (i < 0 || i > this.count) {
throw new IndexOutOfBoundsException(
"索引越界：当前大小=" + this.count + "，传入索引=" + i
);
}
// 如果是0
if (i == 0) {
Node<E> node = new Node<>(e, this.first);
this.first = node;
this.count++;
if (this.last == null) {
this.last = this.first;
}
return true;
}
// 如果是this.count, 说明是尾部
if (i == this.count) {
add(e);
return true;
}
Node<E> node = this.first;
// 移动到前驱节点(i-1)
for (int j = 0; j < i - 1; j++) {
node = node.next;
}
node.next = new Node<>(e, node.next);
this.count++;
return true;
}
@Override
public E get(int i) {
if (i < 0 || i >= this.count) {
throw new IndexOutOfBoundsException(
"索引越界：当前大小=" + this.count + "，传入索引=" + i
);
}
Node<E> node = this.first;
// 移动到目标节点
for (int j = 0; j < i; j++) {
node = node.next;
}
return node.data;
}
@Override
public E set(int i, E e) {
if (i < 0 || i >= this.count) {
throw new IndexOutOfBoundsException(
"索引越界：当前大小=" + this.count + "，传入索引=" + i
);
}
Node<E> node = this.first;
// 移动到目标节点
for (int j = 0; j < i; j++) {
node = node.next;
}
E old = node.data;
node.data = e;
return old;
}
@Override
public E remove(int i) {
if (i < 0 || i >= this.count) {
throw new IndexOutOfBoundsException(
"索引越界：当前大小=" + this.count + "，传入索引=" + i
);
}
Node<E> node = this.first;
// 处理头删
if (i == 0) {
this.first = this.first.next;
this.count--;
return node.data;
}
for (int j = 0; j < i - 1; j++) {
node = node.next;
}
Node<E> temp = node.next;
node.next = node.next.next;
this.count--;
// 处理尾删
if (node.next == null) {
this.last = node;
}
return temp.data;
}
@Override
public int indexOf(E e) {
// 特殊情况 e==null或者node.data == null
Node<E> node = this.first;
for (int i = 0; i < this.count; i++) {
if (node.data == null && e == null) {
return i;
}
if (node.data != null && node.data.equals(e)) {
return i;
}
node = node.next;
}
return -1;
}
@Override
public void clear() {
Node<E> current = this.first;
while (current != null) {
Node<E> nextNode = current.next;
// 释放当前节点的所有引用
current.data = null;
current.next = null;
// 移动到下一个节点
current = nextNode;
}
this.first = null;
this.last = null;
this.count = 0;
}
@Override
public int length() {
return this.count;
}
class Node<E> {
E data;
Node<E> next;
public Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
}
进行测试
package org.example;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
/**
* LinkListImpl 单元测试
* 覆盖：add/remove/get/set/indexOf/clear/length 所有核心方法
*/
class LinkListImplTest {
private LinkList<Integer> list;
// 每个测试方法执行前初始化空链表
@BeforeEach
void setUp() {
list = new LinkListImpl<>();
}
// ==================== add(E e) 尾插法测试 ====================
@Test
void testAdd_E_EmptyList() {
// 空链表尾插
assertTrue(list.add(10));
assertEquals(1, list.length());
assertEquals(10, list.get(0));
assertSame(list.get(0), list.get(0)); // 验证节点数据正确
}
@Test
void testAdd_E_MultiElements() {
// 多元素尾插
list.add(1);
list.add(2);
list.add(3);
assertEquals(3, list.length());
assertEquals(1, list.get(0));
assertEquals(2, list.get(1));
assertEquals(3, list.get(2));
}
// ==================== add(int i, E e) 指定索引插入测试 ====================
@Test
void testAdd_Index_E_Head() {
// 头插（i=0）
list.add(0, 1);
list.add(0, 2);
assertEquals(2, list.length());
assertEquals(2, list.get(0));
assertEquals(1, list.get(1));
}
@Test
void testAdd_Index_E_Tail() {
// 尾插（i=count）
list.add(0, 1);
list.add(1, 2); // i=count=1
list.add(2, 3); // i=count=2
assertEquals(3, list.length());
assertEquals(3, list.get(2));
}
@Test
void testAdd_Index_E_Middle() {
// 中间插入
list.add(1);
list.add(3);
list.add(1, 2); // 插入到索引1
assertEquals(3, list.length());
assertEquals(1, list.get(0));
assertEquals(2, list.get(1));
assertEquals(3, list.get(2));
}
@Test
void testAdd_Index_E_OutOfBounds() {
// 越界插入（i=-1 / i>count）
assertThrows(IndexOutOfBoundsException.class, () -> list.add(-1, 1));
assertThrows(IndexOutOfBoundsException.class, () -> list.add(1, 1)); // 空链表i=1>count=0
list.add(0, 1);
assertThrows(IndexOutOfBoundsException.class, () -> list.add(2, 2)); // count=1，i=2>1
}
// ==================== get(int i) 获取元素测试 ====================
@Test
void testGet_ValidIndex() {
list.add(10);
list.add(20);
assertEquals(10, list.get(0));
assertEquals(20, list.get(1));
}
@Test
void testGet_OutOfBounds() {
// 越界获取（i=-1 / i>=count）
assertThrows(IndexOutOfBoundsException.class, () -> list.get(-1));
assertThrows(IndexOutOfBoundsException.class, () -> list.get(0)); // 空链表i=0>=count=0
list.add(1);
assertThrows(IndexOutOfBoundsException.class, () -> list.get(1)); // count=1，i=1>=1
}
// ==================== set(int i, E e) 修改元素测试 ====================
@Test
void testSet_ValidIndex() {
list.add(1);
list.add(2);
// 修改索引1的元素
Integer old = list.set(1, 3);
assertEquals(2, old); // 返回旧值
assertEquals(3, list.get(1)); // 验证新值
}
@Test
void testSet_OutOfBounds() {
assertThrows(IndexOutOfBoundsException.class, () -> list.set(-1, 1));
assertThrows(IndexOutOfBoundsException.class, () -> list.set(0, 1)); // 空链表
list.add(1);
assertThrows(IndexOutOfBoundsException.class, () -> list.set(1, 2)); // count=1，i=1>=1
}
// ==================== remove(int i) 删除元素测试 ====================
@Test
void testRemove_Head() {
// 头删
list.add(1);
list.add(2);
Integer removed = list.remove(0);
assertEquals(1, removed);
assertEquals(1, list.length());
assertEquals(2, list.get(0));
}
@Test
void testRemove_Tail() {
// 尾删
list.add(1);
list.add(2);
list.add(3);
Integer removed = list.remove(2);
assertEquals(3, removed);
assertEquals(2, list.length());
assertEquals(2, list.get(1));
// 验证last指针更新
list.add(4); // 尾插新元素，验证last正确
assertEquals(4, list.get(2));
}
@Test
void testRemove_Middle() {
// 中间删除
list.add(1);
list.add(2);
list.add(3);
Integer removed = list.remove(1);
assertEquals(2, removed);
assertEquals(2, list.length());
assertEquals(1, list.get(0));
assertEquals(3, list.get(1));
}
@Test
void testRemove_OnlyOneElement() {
// 删除唯一元素（验证first/last置空）
list.add(1);
list.remove(0);
assertEquals(0, list.length());
assertThrows(IndexOutOfBoundsException.class, () -> list.get(0));
}
@Test
void testRemove_OutOfBounds() {
assertThrows(IndexOutOfBoundsException.class, () -> list.remove(-1));
assertThrows(IndexOutOfBoundsException.class, () -> list.remove(0)); // 空链表
list.add(1);
assertThrows(IndexOutOfBoundsException.class, () -> list.remove(1)); // count=1，i=1>=1
}
// ==================== indexOf(E e) 查找索引测试 ====================
@Test
void testIndexOf_ExistElement() {
list.add(1);
list.add(2);
list.add(3);
assertEquals(0, list.indexOf(1));
assertEquals(1, list.indexOf(2));
assertEquals(2, list.indexOf(3));
}
@Test
void testIndexOf_NullElement() {
// 测试null元素
LinkList<String> strList = new LinkListImpl<>();
strList.add(null);
strList.add("test");
assertEquals(0, strList.indexOf(null));
assertEquals(1, strList.indexOf("test"));
assertEquals(-1, strList.indexOf("null"));
}
@Test
void testIndexOf_NotExistElement() {
list.add(1);
list.add(2);
assertEquals(-1, list.indexOf(3));
assertEquals(-1, list.indexOf(null)); // 链表无null元素
}
// ==================== clear() 清空链表测试 ====================
@Test
void testClear() {
list.add(1);
list.add(2);
list.clear();
assertEquals(0, list.length());
assertThrows(IndexOutOfBoundsException.class, () -> list.get(0));
// 清空后可正常新增
list.add(3);
assertEquals(1, list.length());
assertEquals(3, list.get(0));
}
// ==================== length() 长度测试 ====================
@Test
void testLength() {
assertEquals(0, list.length());
list.add(1);
assertEquals(1, list.length());
list.add(2);
assertEquals(2, list.length());
list.remove(0);
assertEquals(1, list.length());
list.clear();
assertEquals(0, list.length());
}
}
全部通过