Java中创建链表的基础概念
链表是一种线性数据结构,与数组不同，它不要求连续的内存空间，而是通过节点（Node）之间的指针连接而成，每个节点包含两部分：数据域（存储实际数据）和指针域（指向下一个节点的引用），在Java中，链表的实现通常基于对象和引用，常见的类型包括单向链表、双向链表和循环链表，本文将详细介绍如何使用Java创建单向链表，包括节点定义、链表类实现、基本操作及实际应用示例。
链表节点的定义
链表的核心是节点,因此首先需要定义节点类，节点类通常包含两个成员变量：一个存储数据（可以是任意数据类型，通过泛型实现），另一个存储下一个节点的引用。
class Node<T> {
T data; // 数据域，存储节点数据
Node<T> next; // 指针域，指向下一个节点
// 构造方法，初始化节点数据和next引用
public Node(T data) {
this.data = data;
this.next = null; // 新节点的next默认为null
}
}
这里使用泛型<T>使节点类可以存储任意类型的数据（如Integer、String等），提高了代码的复用性，构造方法接收数据参数，并将next初始化为null，表示新节点默认没有后续节点。
链表类的实现
定义节点类后,需要创建一个链表类来管理所有节点，链表类通常包含头节点（head）作为链表的入口，并提供添加、删除、查找等操作方法。
链表类的结构
class LinkedList<T> {
private Node<T> head; // 头节点，指向链表的第一个节点
// 构造方法，初始化空链表
public LinkedList() {
this.head = null;
}
}
头节点head是链表的起点，若head为null，则链表为空，构造方法初始化时将head设为null，表示创建一个空链表。
添加节点操作
添加节点是链表的基本操作之一,常见的添加方式包括在链表头部添加、尾部添加或指定位置添加，这里以尾部添加为例，介绍实现方法。
// 在链表尾部添加节点
public void append(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode; // 若链表为空，新节点作为头节点
return;
}
Node<T> current = head;
while (current.next != null) {
current = current.next; // 遍历到最后一个节点
}
current.next = newNode; // 将新节点连接到链表尾部
}
逻辑说明：
- 首先创建新节点,若链表为空（
head == null），则直接将新节点设为头节点； - 若链表非空,则从头节点开始遍历，直到找到最后一个节点（
current.next == null），然后将新节点的引用赋给最后一个节点的next域，完成添加。
遍历链表
遍历链表是查看链表数据的基本操作,通过从头节点开始依次访问每个节点的数据域，直到next为null为止。
// 遍历链表并打印节点数据
public void display() {
if (head == null) {
System.out.println("链表为空");
return;
}
Node<T> current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
逻辑说明：
- 检查链表是否为空,若为空则提示并返回；
- 否则从头节点开始,循环打印每个节点的数据，并移动
current指针到下一个节点，直到current为null时结束，最后打印null表示链表结束。
删除节点操作
删除节点需要根据数据值或位置找到目标节点,并修改其前驱节点的next指针，跳过目标节点，以下是根据数据值删除节点的实现：
// 根据数据值删除节点（删除第一个匹配的节点）
public void delete(T data) {
if (head == null) {
return; // 空链表，无需删除
}
// 若头节点就是要删除的节点
if (head.data.equals(data)) {
head = head.next;
return;
}
Node<T> current = head;
while (current.next != null && !current.next.data.equals(data)) {
current = current.next; // 遍历找到目标节点的前驱节点
}
// 若找到目标节点，则删除
if (current.next != null) {
current.next = current.next.next;
}
}
逻辑说明：
- 若链表为空,直接返回；
- 若头节点的数据匹配目标数据,则将头节点指向下一个节点（相当于删除头节点）；
- 否则遍历链表,找到目标节点的前驱节点（
current），然后将其next指向目标节点的下一个节点，完成删除。
查找节点
查找操作根据数据值在链表中搜索目标节点,若找到则返回节点，否则返回null。
// 根据数据值查找节点，返回节点对象（未找到返回null）
public Node<T> search(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) {
return current; // 找到节点，返回
}
current = current.next;
}
return null; // 未找到
}
链表的完整实现与测试
将上述方法整合到LinkedList类中，并编写测试代码验证功能。
完整的LinkedList类
class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
class LinkedList<T> {
private Node<T> head;
public LinkedList() {
this.head = null;
}
// 在尾部添加节点
public void append(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode;
return;
}
Node<T> current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
// 遍历链表
public void display() {
if (head == null) {
System.out.println("链表为空");
return;
}
Node<T> current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
// 删除节点
public void delete(T data) {
if (head == null) return;
if (head.data.equals(data)) {
head = head.next;
return;
}
Node<T> current = head;
while (current.next != null && !current.next.data.equals(data)) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
// 查找节点
public Node<T> search(T data) {
Node<T> current = head;
while (current != null) {
if (current.data.equals(data)) {
return current;
}
current = current.next;
}
return null;
}
}
测试代码
public class LinkedListTest {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
// 添加节点
list.append(10);
list.append(20);
list.append(30);
list.append(40);
System.out.println("添加节点后的链表：");
list.display(); // 输出：10 -> 20 -> 30 -> 40 -> null
// 查找节点
Node<Integer> foundNode = list.search(30);
if (foundNode != null) {
System.out.println("找到节点：" + foundNode.data); // 输出：找到节点：30
} else {
System.out.println("未找到节点");
}
// 删除节点
list.delete(20);
System.out.println("删除节点20后的链表：");
list.display(); // 输出：10 -> 30 -> 40 -> null
// 删除头节点
list.delete(10);
System.out.println("删除头节点10后的链表：");
list.display(); // 输出：30 -> 40 -> null
// 删除不存在的节点
list.delete(99);
System.out.println("尝试删除不存在的节点99后的链表：");
list.display(); // 输出：30 -> 40 -> null
}
}
链表的扩展与注意事项
双向链表与循环链表
单向链表只能从头节点向后遍历,若需要双向遍历，可定义双向链表节点，增加prev指向前驱节点：
class DoublyNode<T> {
T data;
DoublyNode<T> prev;
DoublyNode<T> next;
public DoublyNode(T data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
循环链表则将尾节点的next指向头节点，形成闭环，适用于循环队列等场景。
链表与数组的区别
- 内存空间：数组需要连续内存，链表通过节点连接，内存非连续；
- 插入/删除：链表在指定位置插入或删除只需修改指针，时间复杂度为O(1)（已知节点位置），而数组需要移动元素，时间复杂度为O(n)；
- 随机访问：数组可通过索引直接访问元素（O(1)），链表需遍历查找（O(n)）。
边界情况处理
在实现链表操作时,需特别注意边界情况，如空链表、删除头节点、查找不存在的数据等，避免空指针异常。
通过定义节点类和链表类,结合添加、删除、查找、遍历等基本操作，可以在Java中完整实现链表数据结构，链表的灵活性使其在动态数据管理（如LRU缓存、栈、队列等）中广泛应用，掌握链表的实现原理，有助于深入理解Java的引用机制和内存管理，为学习更复杂的数据结构（如树、图）奠定基础。
