在PostgreSQL中表示单链表并获取指定节点的所有前置节点

简洁高效的递归CTE方案 #

直接从目标节点的直接前驱开始递归追溯，避免冗余逻辑：

WITH RECURSIVE predecessor_chain AS (
  -- 初始步骤：定位目标节点的直接前置节点
  SELECT node_id, next_node_id
  FROM linked_list
  WHERE next_node_id = 3 -- 替换为你要查询的目标节点ID
  UNION ALL
  -- 递归步骤：向上追溯当前节点的前置节点
  SELECT ll.node_id, ll.next_node_id
  FROM linked_list ll
  JOIN predecessor_chain pc ON ll.next_node_id = pc.node_id
)
-- 按链表顺序聚合为数组（从最早的前置节点到直接前置节点）
SELECT ARRAY_AGG(node_id ORDER BY node_id) AS all_predecessors
FROM predecessor_chain;

方案说明 #

• 递归起点直接锁定指向目标节点的节点，无需后续过滤目标节点本身，逻辑更简洁，查询效率更高。
• 递归过程通过关联当前节点的next_node_id与上一轮的node_id，不断向上遍历整个前驱链，直到无更上层节点为止。
• 最终用ARRAY_AGG并按node_id排序，得到顺序正确的前驱数组（比如查询节点3时返回[1,2]）。

原代码的问题分析 #

你之前的代码将递归起点设为目标节点本身（WHERE node_id = 3），虽然能通过关联找到前驱，但需要额外过滤目标节点，逻辑冗余。调整起点后，直接从直接前驱开始遍历，减少了递归的初始数据集和后续过滤步骤。

参数化查询（可选） #

如果需要动态传入目标节点ID，可使用PostgreSQL参数化查询：

WITH RECURSIVE predecessor_chain AS (
  SELECT node_id, next_node_id
  FROM linked_list
  WHERE next_node_id = $1 -- $1为传入的目标节点ID参数
  UNION ALL
  SELECT ll.node_id, ll.next_node_id
  FROM linked_list ll
  JOIN predecessor_chain pc ON ll.next_node_id = pc.node_id
)
SELECT ARRAY_AGG(node_id ORDER BY node_id) AS all_predecessors
FROM predecessor_chain;

当目标节点无前置节点时（比如节点4），查询会返回空数组，符合预期。

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