Java 链表的定义与简单实例

Java链表是一种线性数据结构，它由一个个节点串联起来，每个节点保存了数据元素和指向后续节点的引用。链表可以用于在数据的插入、删除、读取等操作中，灵活地调整数据的排列顺序，因此在Java中被广泛应用。

链表的定义

Java中常用的链表有单向链表和双向链表。单向链表每个节点只保存了指向后续节点的引用，而双向链表除了保存指向后续节点的引用，还保存了指向前继节点的引用。下面是单向链表的定义：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

其中，val表示节点保存的数据元素，next表示指向下一个节点的引用。通过不断遍历 next 可以到达链表的末端。要创建一个链表，我们需要将节点依次串联起来，例如：

ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
n1.next = n2;
n2.next = n3;

这样就创建了一个包含3个节点的单向链表，头节点为 n1。

链表的简单实例

1. 链表的遍历

遍历链表是最常见的链表操作之一，可以通过一个指针从头节点开始，依次遍历每个节点。以下是一个遍历链表并打印节点值的示例代码：

ListNode p = n1;
while (p != null) {
    System.out.println(p.val);
    p = p.next;
}

在示例代码中，每次循环我们通过 p 访问当前节点的值并打印，然后将指针移动到下一个节点。

2. 链表的插入

链表的插入是通过修改节点间的指针来实现的。要在链表中插入一个新的节点，我们需要先找到插入位置所在的节点，然后将新节点的 next 指针指向插入位置的下一个节点，再将插入位置的 next 指针指向新节点。以下是一个向链表插入新节点的示例代码：

ListNode n4 = new ListNode(4);
ListNode p = n1;
while (p.next != null && p.next.val < n4.val) {
    p = p.next;
}
n4.next = p.next;
p.next = n4;

在示例代码中，我们先通过遍历链表找到插入位置所在的节点 p，然后将新节点 n4 的 next 指针指向 p 的下一个节点，并将 p 的 next 指针指向新节点 n4。

总结

Java链表是一种灵活的数据结构，在数据处理中经常被使用。通过定义节点类，将节点串联起来，我们可以方便地实现链表的遍历、插入、删除等常见操作。在实际应用中，我们可以根据需求选择单向链表还是双向链表，并根据具体的数据结构设计进行优化。