PHP实现带头结点单向链表：增删改查完整示例

设计思路：带头结点的单向链表

在PHP这类动态语言中实现链表，核心在于对象间的引用传递。为了简化“头插法”或“尾插法”的特殊边界处理（如空表或首节点操作），通常采用带头结点的设计模式：

• 头结点（Head Node）：不存储实际业务数据，仅作为链表的起始锚点，其next指向第一个真实节点。
• 真实节点：包含业务数据（如编号、姓名）和指向下一个节点的指针 $next。

这种结构的好处是：add、del等操作时，无论链表是否为空，对$head->next的操作逻辑保持一致，无需单独判断头指针的变动。

完整代码实现

以下代码定义了一个 linkList 类，实现了链表的初始化、按ID自动排序添加、删除节点、修改节点属性以及遍历打印功能。

<?php 
/**
 * PHP实现链表的基本操作 - 带头结点版本
 */
class linkList {
  /**
   * 姓名
   * @var string
   */
  public $name = '';
   
  /**
   * 编号（用于唯一标识和排序）
   * @var int
   */
  public $id = 0;
   
  /**
   * 引用下一个对象（节点指针）
   * @var linkList|null
   */
  public $next = null;
   
  /**
   * 构造函数初始化数据
   * @param int $id
   * @param string $name
   */
  public function __construct($id = 0, $name = '') {
    $this->name = $name;
    $this->id  = $id;
  }
   
  /**
   * 遍历链表并输出内容
   * @param linkList $head 头结点
   */
  public static function echo_link_list($head) {
    // 注意：从 head->next 开始遍历，跳过不存数据的头结点
    $curr = $head;
    while ($curr->next != null) {
      echo '姓名:'.$curr->next->name, ' 编号:'.$curr->next->id;
      echo '<br>';
      $curr = $curr->next;
    }
  }
   
  /**
   * 添加新节点（按ID从小到大自动排序插入）
   * @param linkList $head 头结点
   * @param int $id 编号
   * @param string $name 姓名
   * @return bool 成功返回true，ID重复返回false
   */
  public static function add($head, $id, $name) {
    $curr = $head;
    $obj = new linkList($id, $name);
     
    // 寻找插入位置
    while ($curr->next != null) {
      // 如果当前ID < 下一个ID，说明找到了合适的插入位置（中间）
      if ($curr->next->id > $id) {         
        // 执行“断链-重连”操作：先让新节点指向下一个节点，再让当前节点指向新节点
        $obj->next = $curr->next;
        $curr->next = $obj;
         
        return true;
      } else if ($curr->next->id == $id) {
        // ID已存在，拒绝添加
        echo "当前Id:{$id} 重复了，请不要继续添加了！";
        echo '<br>';
        return false;
      }
      $curr = $curr->next;
    }
    
    // 如果循环结束仍未返回，说明所有现有ID都小于新ID，直接添加到尾部
    if ($curr->next == null) {
      $curr->next = $obj;
    }
  }
   
  /**
   * 删除指定ID的节点
   * @param linkList $head 头结点
   * @param int $id 要删除的编号
   * @return bool 成功返回true，未找到返回null/false
   */
  public static function del($head, $id) {
    $curr = $head;
     
    // 检查 curr->next，防止访问不存在的节点
    while($curr->next != null) {
      if ($curr->next->id == $id) {
        // 发现目标节点，跳过它（指向下下个节点）
        $curr->next = $curr->next->next;
        return true;
      }
      $curr = $curr->next;
    }
    return false; // 未找到指定ID
  }
   
  /**
   * 修改指定ID的节点姓名
   * @param linkList $head 头结点
   * @param int $id 目标编号
   * @param string $new_name 新姓名
   */
  public static function edit($head, $id, $new_name) {
    $curr = $head;
     
    while($curr->next != null) {
      if ($curr->next->id == $id) {
        // 找到节点，直接修改属性
        $curr->next->name = $new_name;
        break; // 假设ID唯一，找到后即可退出
      }
      $curr = $curr->next;
    }
  }
}

// --- 测试用例 ---

// 1. 创建头结点
$head = new linkList();

// 2. 添加节点（观察自动排序效果）
linkList::add($head, 1, 'wangdk');
linkList::add($head, 2, 'sunshuzhen');
linkList::add($head, 8, 'wanghaha');
linkList::add($head, 6, 'wangchufen');
linkList::add($head, 6, 'wangchufen'); // 测试重复ID插入
linkList::add($head, 3, 'wangdaye');

echo "添加后的链表：<br>";
linkList::echo_link_list($head);

// 3. 删除ID为1的节点
linkList::del($head, 1);

// 4. 修改ID为2的节点姓名
linkList::edit($head, 2, 'hahaha');

echo "<br>删除与修改后的链表：<br>";
linkList::echo_link_list($head); 

?>

核心逻辑解析

第一步：按序插入节点 (Add)

插入操作的关键在于找到合适的前驱节点（Predecessor）。代码使用 while 循环不断向后移动指针，比较当前节点的 ID 与新节点的 ID：

• 中间插入：当遇到 next->id > id 时，说明新节点应排在当前节点之后、下一节点之前。此时进行指针交换：先将新节点的 next 指向原 next，再将当前节点的 next 指向新节点。
• 尾部插入：若循环遍历完整个链表都没有触发插入条件，说明新ID最大，直接追加到末尾。
• 防重机制：在比较过程中，若发现 next->id == id，则直接拦截并返回错误提示。

第二步：删除与查找修改 (Del & Edit)

这两步的操作逻辑相似，都是基于前驱节点的指针跳转：

• 删除：一旦确认 curr->next 的目标节点即是要删除的对象，只需将 curr->next 直接赋值为 curr->next->next，被跳过的节点将因失去引用而被垃圾回收机制清理。
• 修改：找到对应节点后，直接更新其成员变量（如 name），无复杂的指针变化。

注意事项

在实际生产环境中，该实现主要针对教学演示。若需应用于大规模数据处理，建议注意以下几点：

1. 异常处理：完善 del 方法中未找到ID时的返回值定义。
2. 类型安全：PHP 8+ 中可使用类型声明约束参数，例如 public function __construct(int $id, string $name)。
3. 性能考量：链表不适合随机访问，频繁遍历效率低于数组。若涉及高频查询，应考虑结合哈希表或其他索引结构。