当前位置：首页 > news >正文

链表：头插法与尾插法 - Higurashi

news 2026/5/12 12:12:29

一、头插法

定义：头插法是指在链表头部进行节点插入的方法。其核心特点是，新插入的节点总成为链表的第一个有效节点。因此，如果按数据1, 2, 3的顺序进行头插操作，最终链表的节点排列顺序将是3, 2, 1。简而言之，头插法实现的是逆序插入。

代码示例：使用头插法建立单链表

我们首先定义链表节点结构：

class ListNode {int data;ListNode next;public ListNode(int data) {this.data = data;this.next = null;}public ListNode() {this(0); // 无参构造：用于头结点}
}

然后新建一个单链表类，后面将在该类基础上补充头插和尾插对应方法：

import java.util.Scanner;public class LinkedList {private ListNode head; // 头结点（dummy node），不存有效数据private Scanner scanner;public LinkedList() {this.head = new ListNode(); // 创建头结点，next = nullthis.scanner = new Scanner(System.in);}// 工具方法：遍历打印链表（不含头结点）public void print() {ListNode p = head.next;System.out.print("链表内容：");if (p == null) {System.out.println("空");return;}while (p != null) {System.out.print(p.data + " -> ");p = p.next;}System.out.println("null");}// 获取头结点（仅用于测试或外部操作）public ListNode getHead() {return head;}// 关闭 scanner（避免资源泄露）public void close() {scanner.close();}
}

下面是使用头插法创建链表的代码：

// 头插法：逆序插入
public void headInsert() {System.out.print("请输入节点数据（输入 -1 结束）：");int x = scanner.nextInt();while (x != -1) {ListNode newNode = new ListNode(x);// 关键两步（头插核心）newNode.next = head.next;head.next = newNode;System.out.print("请输入节点数据（输入 -1 结束）：");x = scanner.nextInt();}
}

图示如下：

小结：头插法通常应用于需要将数据进行逆序存储的场景，例如链表逆置操作。

二、尾插法

定义：尾插法是指在链表尾部进行节点插入的方法。其主要特点是，新插入的节点总成为链表的最后一个有效节点。因此，如果按数据1, 2, 3的顺序进行尾插操作，最终链表的节点排列顺序依然是1, 2, 3。简而言之，尾插法实现的是顺序插入。

代码示例：使用尾插法建立单链表

// 尾插法：顺序插入
public void tailInsert() {ListNode tail = head; // tail 指向当前尾节点（初始为头结点）System.out.print("请输入节点数据（输入 -1 结束）：");int x = scanner.nextInt();while (x != -1) {ListNode newNode = new ListNode(x);// 关键两步（尾插核心）tail.next = newNode;tail = newNode; // 更新尾指针System.out.print("请输入节点数据（输入 -1 结束）：");x = scanner.nextInt();}// 最后一个节点的 next 本来就是 null，可省略；显式写出更清晰tail.next = null;
}

图示如下：