Java中循环单链表如何插入元素？头插法示例代码逻辑咨询

首先明确这个实现的基础设计：该循环单链表仅维护尾节点指针last，last.next固定指向链表的第一个节点（头节点），这是理解这段代码的核心前提。

1. 为什么需要动态创建新节点 #

链表的每个节点都需要独立的内存空间来存储两部分内容：节点存储的数据data、指向下一个节点的指针next。

• 如果使用栈内存（非动态创建）分配节点，当前addBegin函数执行结束后，栈内存会被系统自动回收，新节点的内存会被释放，插入到链表中的节点就变成了非法的野指针，后续访问会直接出错。
• 动态创建（new Node()）是在堆内存中申请空间，这部分内存的生命周期由开发者控制，只要不手动释放就会一直有效，插入到链表后可以正常访问。

2. 插入时不需要“移动节点腾空间” #

链表和数组的存储结构完全不同：

• 数组是连续内存存储，在头部插入元素时必须把所有现有元素往后移动一位才能腾出位置，时间复杂度为O(n)。
• 链表的每个节点都是离散分布在内存中的，节点之间仅靠指针关联，插入新节点时根本不需要移动任何现有节点的物理位置，只需要修改两个指针的指向就能把新节点串进链表中，时间复杂度为O(1)。

代码步骤逐行拆解（非空链表场景） #

我们用一个实际例子辅助理解：假设现有循环单链表为1->2->3->1，尾节点last指向3，last.next就是头节点1，现在要插入值为0的新节点到头部。

static Node addBegin(Node last, int data)
{
    if (last == null)
        return addToEmpty(last, data); // 空链表逻辑你已经理解，跳过
    
    Node temp = new Node(); // 动态创建新节点，对应我们要插的0节点
    temp.data = data; // 新节点的data赋值为0

    // 第一步：新节点的next指向原来的头节点，也就是temp.next = 1
    temp.next = last.next;
    // 第二步：尾节点的next指向新节点，也就是last.next = 0，现在链表变成 3->0->1->2->3，新节点0就成了新的头节点
    last.next = temp;
  
    return last;
}

插入完成后新的循环链表为0->1->2->3->0，完全符合头插的要求，整个过程没有任何现有节点的内存位置发生变化，仅修改了两个指针的指向。

内容的提问来源于stack exchange，提问作者captaincabbage