一、Java 集合框架
Java 集合框架是存储和操作对象的核心体系,主要分为 Collection(单列) 和 Map(双列)。
Collection 接口体系
- 根接口:
Collection定义了增删改查、遍历等基础操作。 - 子接口:
List:有序且可重复。Set:无序且不可重复。Queue:队列结构。
Map 接口体系
- 存储键值对(Key-Value),Key 唯一。
- 子接口如
SortedMap支持按键排序。
本文重点聚焦于 List 接口的实现类之一:LinkedList。
二、链表数据结构
在底层数据结构中,链表通过非连续的内存单元存储元素。理解其节点构成有助于掌握 Java 中的实现逻辑。
- 节点(Node):基本存储单元,包含数据域(业务数据)和指针域(指向下一个或上一个节点的引用)。
- 头指针:指向链表第一个节点的入口引用。
- 尾节点:最后一个节点,单向链表中通常指向
null。
三、手动实现单链表
为了深入理解原理,我们可以尝试手写一个无头结点的单向链表。这有助于理清增删操作的边界条件。
1. 节点定义
static class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
2. 核心方法实现
这里展示几个关键操作,实际开发中建议直接复用 JDK 提供的工具类,但理解源码逻辑至关重要。
创建与插入
ListNode head;
// 头插法:O(1)
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
// 尾插法:需遍历至尾部 O(n)
{
(data);
(head == ) {
head = node;
;
}
head;
(cur.next != ) {
cur = cur.next;
}
cur.next = node;
}
{
(index < || index > size()) {
System.out.println();
;
}
(index == ) {
addFirst(data);
;
}
(index == size()) {
addLast(data);
;
}
findIndex(index - );
(data);
node.next = prev.next;
prev.next = node;
}
ListNode {
head;
;
(count != index) {
cur = cur.next;
count++;
}
cur;
}


