链表的基本概念与Java中的实现基础
链表是一种线性数据结构，与数组不同，它的元素在内存中不是连续存储的，而是通过指针（引用）连接成一系列节点，每个节点包含两部分：数据域（存储实际数据）和指针域（指向下一个节点的引用），链表的常见类型包括单链表、双链表和循环链表，其中单链表是最基础的形式，每个节点仅指向其后继节点。
在Java中，链表没有内置的原始数据类型，而是通过对象和引用来实现，开发者可以通过自定义类或使用Java集合框架中的LinkedList类来操作链表，理解链表的底层原理对于高效使用和优化代码至关重要，因此本文将从基础实现到进阶操作，详细讲解Java中创建链表的方法。
自定义单链表的实现步骤
定义节点类
单链表的核心是节点类，每个节点包含数据域和指向下一个节点的引用，以下是节点类的简单实现：
class ListNode {
int data; // 数据域，存储节点数据
ListNode next; // 指针域，指向下一个节点
// 构造方法，初始化节点数据
public ListNode(int data) {
this.data = data;
this.next = null; // 新节点的next默认为null
}
}
通过构造方法，可以在创建节点时直接赋值，并将next初始化为null，表示当前节点暂无后继节点。
创建链表类
链表类需要管理头节点，并提供添加节点、遍历链表等操作，以下是基础的单链表类实现：
class LinkedList {
private ListNode head; // 头节点，不存储实际数据，仅作为入口
// 构造方法，初始化空链表
public LinkedList() {
this.head = null;
}
// 在链表尾部添加节点
public void append(int data) {
ListNode newNode = new ListNode(data);
if (head == null) {
head = newNode; // 如果链表为空，头节点指向新节点
} else {
ListNode current = head;
while (current.next != null) {
current = current.next; // 遍历到链表末尾
}
current.next = newNode; // 将末尾节点的next指向新节点
}
}
// 遍历并打印链表
public void display() {
ListNode current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
}
使用自定义链表
创建链表对象并添加节点，最后遍历输出：
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.display(); // 输出：1 -> 2 -> 3 -> null
}
}
Java集合框架中的LinkedList类
除了自定义实现，Java提供了java.util.LinkedList类，它实现了List和Deque接口，支持动态扩容和丰富的操作方法。LinkedList底层基于双向链表实现，每个节点包含前驱和后继引用，适合频繁插入和删除的场景。
创建LinkedList对象
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// 创建LinkedList对象
LinkedList<String> list = new LinkedList<>();
// 添加元素
list.add("A"); // 在尾部添加
list.addFirst("B"); // 在头部添加
list.addLast("C"); // 在尾部添加
list.add(1, "D"); // 在指定位置插入
// 输出链表：B -> A -> D -> C
System.out.println(list);
}
}
常用方法
add(E element)：在链表尾部添加元素。addFirst(E element)：在链表头部添加元素。addLast(E element)：在链表尾部添加元素（等效于add）。get(int index)：获取指定位置的元素。removeFirst()：移除并返回头节点元素。removeLast()：移除并返回尾节点元素。size()：返回链表长度。
LinkedList是非线程安全的，如果在多线程环境下使用，需要通过Collections.synchronizedList()方法包装。
链表的常见操作与优化
头插法与尾插法
- 头插法：每次将新节点插入到头节点之后，新节点的
next指向原头节点，头节点更新为新节点，时间复杂度为O(1)，但会改变元素的顺序。 - 尾插法：每次将新节点连接到链表末尾，时间复杂度为O(n)（需遍历至末尾），可通过维护尾指针优化至O(1)。
删除节点
删除节点需要定位到待删除节点的前一个节点，修改其next指针，删除值为key的节点：
public void deleteNode(int key) {
if (head == null) return;
if (head.data == key) { // 删除头节点
head = head.next;
return;
}
ListNode current = head;
while (current.next != null && current.next.data != key) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next; // 跳过待删除节点
}
}
反转链表
反转链表是常见面试题，可通过迭代或递归实现，迭代法如下：
public ListNode reverseList() {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextNode = current.next; // 暂存下一个节点
current.next = prev; // 当前节点指向前一个节点
prev = current; // 前驱节点后移
current = nextNode; // 当前节点后移
}
head = prev; // 更新头节点
return head;
}
链表的应用场景与注意事项
应用场景
- 动态数据存储：链表长度可动态变化，适合元素数量不确定的场景。
- 频繁插入/删除：相比数组，链表在中间位置的插入和删除时间复杂度为O(1)，无需移动大量元素。
- 实现其他数据结构：如队列（
LinkedList实现了Deque接口）、栈等。
注意事项
- 内存占用：每个节点需额外存储指针域，空间复杂度高于数组。
- 随机访问：链表不支持随机访问，查找元素需遍历，时间复杂度为O(n)。
- 空指针异常：操作时需检查节点是否为
null，避免NullPointerException。
在Java中创建链表可以通过自定义节点类实现底层逻辑，也可直接使用LinkedList类简化开发，自定义链表有助于理解数据结构原理，而LinkedList类则提供了高效的操作方法，根据实际需求选择实现方式，并注意链表的优缺点，才能更好地发挥其性能优势，掌握链表的创建与操作,是提升编程能力和解决复杂问题的重要基础。
