一、链表的基本概念：为什么需要链表？
1.1 数组的局限性
在介绍链表之前，我们先回顾一下数组的特点：
// 数组示例
int[] arr = new int[10]; // 固定大小，一旦创建无法改变
arr[0] = 1; // 随机访问，O(1) 时间复杂度
数组的缺点：
- 大小固定，扩展/收缩成本高
- 插入和删除元素需要移动大量元素（O(n) 时间复杂度）
- 可能造成内存浪费（分配过大）或空间不足（分配过小）
假如数组的长度为 n。
- 访问：O(1) // 访问特定位置的元素
- 插入：O(n) // 最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
- 删除：O(n) // 最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时
1.2 链表的诞生
链表就是为了解决数组的这些痛点而设计的动态数据结构：
// 链表的节点定义
class Node {
int data; // 存储数据
Node next; // 指向下一个节点
public Node(int data) {
this.data = data;
this.next = null;
}
}
二、链表的核心结构与类型
2.1 单链表（Singly Linked List）
单链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点 (头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。
public class SinglyLinkedList {
// 节点定义
private static class ListNode {
int val;
ListNode next;
ListNode( x) { val = x; }
}
ListNode head;
size;
{
head = ;
size = ;
}
{
(val);
newNode.next = head;
head = newNode;
size++;
}
}
