多级嵌套列表任意位置移除对象（跳过图遍历搜索）实现方案

存在深度无理论上限的嵌套同构元素列表，每个元素可持有相同结构的子列表，给定待删除的元素ID集合，需要高效移除任意层级的对应元素，避免全量枚举带来的过高时间开销，现有元素结构定义如下（可根据方案调整）：

public class NavigationPath
{
    public int Id { get; set; }
    public string Name { get; set; }
    public string Value { get; set; }
    public List<NavigationPath> Childs { get; set; }
}

结构参考：

核心思路是单次遍历构建双向索引，将删除操作的时间开销从全树扫描降级为直接定位，整体时间复杂度为初始化O(n)（n为总节点数），删除操作O(k)（k为待删除节点数，不含冗余的子节点遍历），远优于朴素递归搜索删除的O(k*n)复杂度。

具体实现步骤 #

• 初始化阶段仅做一次全树遍历（节点量极大、嵌套极深的场景优先选BFS避免递归栈溢出），维护两个内存字典：
  • nodeMap：Key为节点Id，Value为对应节点实例，用于O(1)判断节点是否存在
  • parentMap：Key为节点Id，Value存储节点的直接父节点引用、节点在父节点Childs列表中的下标，用于删除时直接定位位置，无需遍历查找
• 删除操作前置处理：将传入的待删除Id集合转为HashSet<int>做O(1)存在性判断，过滤掉所有祖先节点已经在待删除集合中的节点——这部分节点会随着上层父节点删除自动脱离树结构，不需要重复操作
• 执行删除：遍历过滤后的待删除Id，直接从parentMap拿到父节点和下标，调用RemoveAt方法移除对应位置的元素即可，不需要递归遍历子树。如果需要持续维护索引有效性，仅需对被删除节点的子树做一次遍历，清理两个字典中对应的键值，避免后续索引脏读。

可选优化 #

如果允许修改原有实体结构，可以直接在NavigationPath类中增加两个属性：

public NavigationPath Parent { get; set; }
public int IndexInParent { get; set; }

构建索引时直接给这两个属性赋值，不需要单独维护全局字典，代码实现更简洁，性能没有损耗。

参考代码片段 #

索引构建（BFS实现，无递归栈溢出风险）：

// 根节点列表为当前持有的最外层NavigationPath集合
List<NavigationPath> rootList = GetRootList();
var nodeMap = new Dictionary<int, NavigationPath>();
var parentMap = new Dictionary<int, (NavigationPath parent, int index)>();
var queue = new Queue<(NavigationPath current, NavigationPath parent, int index)>();

// 根层节点入队
for (var i = 0; i < rootList.Count; i++)
{
    queue.Enqueue((rootList[i], null, i));
}

while (queue.Count > 0)
{
    var (current, parent, index) = queue.Dequeue();
    nodeMap[current.Id] = current;
    parentMap[current.Id] = (parent, index);

    if (current.Childs == null || current.Childs.Count == 0) continue;
    // 子节点入队
    for (var i = 0; i < current.Childs.Count; i++)
    {
        queue.Enqueue((current.Childs[i], current, i));
    }
}

删除逻辑实现：

HashSet<int> toDeleteIds = new HashSet<int>(GetPendingDeleteIds());
// 过滤无需重复删除的节点
var validDeleteIds = toDeleteIds.Where(id =>
{
    var (parent, _) = parentMap[id];
    return parent == null || !toDeleteIds.Contains(parent.Id);
}).ToList();

foreach (var id in validDeleteIds)
{
    var (parent, index) = parentMap[id];
    if (parent == null)
    {
        rootList.RemoveAt(index);
    }
    else
    {
        parent.Childs.RemoveAt(index);
    }
    // 按需清理索引：遍历被删节点的子树，移除字典中对应的记录
    CleanIndexForDeletedNode(id, nodeMap, parentMap);
}

注意：如果树结构后续会频繁做新增/移动操作，只需要在操作时同步更新两个字典的对应记录即可，不需要重新全量构建索引，整体开销极低。

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