Dart中如何通过前后元素比较插入列表项？及实现问题咨询

程序挂起的核心原因 #

你的place方法触发了无限循环：

• 循环条件i < length里的length是动态变化的——每次调用insert(i, item)都会让列表长度+1。
• 拿插入2到[1]的场景举例：初始列表长度是1，i=0时符合条件插入2，长度变成2；i递增到1，此时i < length依然成立，再次执行判断，因为next为null（当前是最后一个元素），comparator返回true，又会插入2，长度变为3……以此类推，循环永远停不下来。
• 另外，找到符合条件的位置后没有终止循环，会导致同一个元素被重复插入。

修复后的代码实现 #

可以先遍历找到目标位置，再执行一次插入；或者找到位置后插入并立即break，这里推荐前者，逻辑更清晰：

extension ListExtension<T> on List<T> {
  void place(T item, bool Function(T? prev, T curr, T? next) comparator) {
    int insertIndex = length; // 默认插在列表末尾
    for (int i = 0; i < length; i++) {
      final prev = elementAtOrNull(i - 1);
      final next = elementAtOrNull(i + 1);
      if (comparator(prev, item, next)) {
        insertIndex = i;
        break; // 找到第一个符合条件的位置就停止遍历
      }
    }
    insert(insertIndex, item);
  }
}

同时你的comparator有重复逻辑，可以简化：

bool comparator(int? prev, int curr, int? next) {
  if (next == null) return true;
  if (prev == null) return curr < next;
  return curr >= prev && curr < next;
}

修改后测试就能正常通过。

基于普通List的这种插入方式，主要性能瓶颈：

• 遍历开销：最坏情况需要遍历整个列表（比如插入到末尾），时间复杂度O(n)。
• 插入开销：List的insert操作需要把插入位置后的所有元素向后移动一位，时间复杂度O(n)。
• 整体每次插入的时间复杂度是O(n)，如果频繁插入大量元素，总复杂度会达到O(n²)，大数据量场景下会有明显卡顿。

如果需要频繁维护有序集合，优先考虑以下方案：

• SortedList（来自collection包）：这是专门为有序集合设计的结构，插入、查找操作的时间复杂度为O(log n)，内部通过二分查找定位插入位置，比手动实现高效得多。使用示例：

  import 'package:collection/collection.dart';
  
  void main() {
    final sortedList = SortedList<int>((a, b) => a.compareTo(b));
    sortedList.add(1);
    sortedList.add(2);
    sortedList.add(4);
    sortedList.add(3);
    print(sortedList); // 输出 [1,2,3,4]
  }
  

• 平衡二叉树：如果不想依赖第三方包，也可以自己实现红黑树或AVL树，但开发成本较高，不如直接用成熟的第三方库。
• LinkedList：插入操作本身是O(1)，但查找插入位置依然需要O(n)遍历，整体性能和普通List差不多，仅适合已经持有目标节点引用的场景。

你的场景是处理流式非有序数据，SortedList可以完美适配——无需每次全量排序，每次插入都能自动维护有序性，避免ListView因为全量排序导致的界面抖动。

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