Java中的单链表是一种常见的数据结构，用于以线性方式存储元素集合，但与数组不同，单链表中的元素不是连续存储在内存中的。
每个元素（或称为节点）包含两个部分：一部分是存储的数据（data），另一部分是指向列表中下一个元素的引用（或链接，link）。
这种结构使得单链表在插入和删除元素时更加灵活，因为不需要移动其他元素来腾出空间或填补空白。
1. 节点（Node）的定义
在Java中，单链表中的每个节点通常通过一个内部类来定义，这个内部类包含两个成员：一个是存储的数据（可以是任意类型），另一个是指向下一个节点的引用。
class ListNode<T> { T data; // 节点存储的数据 ListNode<T> next; // 指向下一个节点的引用 // 构造函数 public ListNode(T data) { this.data = data; this.next = null; // 默认下一个节点为空 }
}2. 单链表的定义
单链表本身可以看作是一个指向链表第一个节点的引用（或称为头节点），以及可能包含的一些方法，如添加、删除、查找节点等。
class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}// 输入一个数组，转换为一条单链表
ListNode createLinkedList(int[] arr) {if (arr == null || arr.length == 0) {return null;}ListNode head = new ListNode(arr[0]);ListNode cur = head;for (int i = 1; i < arr.length; i++) {cur.next = new ListNode(arr[i]);cur = cur.next;}return head;
}// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});// 遍历单链表
for (ListNode p = head; p != null; p = p.next) {System.out.println(p.val);
}// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});// 在单链表头部插入一个新节点 0
ListNode newHead = new ListNode(0);
newHead.next = head;
head = newHead;
// 现在链表变成了 0 -> 1 -> 2 -> 3 -> 4 -> 5// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});// 在单链表尾部插入一个新节点 6
ListNode p = head;
// 先走到链表的最后一个节点
while (p.next != null) {p = p.next;
}
// 现在 p 就是链表的最后一个节点
// 在 p 后面插入新节点
p.next = new ListNode(6);// 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});// 在第 3 个节点后面插入一个新节点 66
// 先要找到前驱节点，即第 3 个节点
ListNode p = head;
for (int i = 0; i < 2; i++) {p = p.next;
}
// 此时 p 指向第 3 个节点
// 组装新节点的后驱指针
ListNode newNode = new ListNode(66);
newNode.next = p.next;// 插入新节点
p.next = newNode;// 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});// 删除第 4 个节点，要操作前驱节点
ListNode p = head;
for (int i = 0; i < 2; i++) {p = p.next;
}// 此时 p 指向第 3 个节点，即要删除节点的前驱节点
// 把第 4 个节点从链表中摘除
p.next = p.next.next;// 现在链表变成了 1 -> 2 -> 3 -> 5// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});// 删除尾节点
ListNode p = head;
// 找到倒数第二个节点
while (p.next.next != null) {p = p.next;
}// 此时 p 指向倒数第二个节点
// 把尾节点从链表中摘除
p.next = null;// 现在链表变成了 1 -> 2 -> 3 -> 4// 创建一条单链表
ListNode head = createLinkedList(new int[]{1, 2, 3, 4, 5});// 删除头结点
head = head.next;// 现在链表变成了 2 -> 3 -> 4 -> 53. 单链表的基本操作
- 添加（Append）：向链表末尾添加一个新节点。
- 插入（Insert）：在链表中的指定位置插入一个新节点。
- 删除（Delete）：删除链表中的指定节点或具有特定值的节点。
- 查找（Search）：查找链表中是否存在具有特定值的节点，并返回该节点（或节点的数据）。
- 遍历（Traverse）：遍历链表中的每个节点，并对每个节点执行某些操作（如打印节点的数据）。
4. 优点和缺点
优点：
- 插入和删除操作效率高，因为不需要移动其他元素。
- 动态数据结构，大小不固定。
缺点：
- 访问链表中的元素不如数组快，因为需要从头节点开始遍历。
- 额外的空间开销，因为每个节点都需要存储指向下一个节点的引用。