假设无重复数据，Set 是否总是比 Linked List 性能表现更优？

你这个判断在绝大多数无重复数据的通用业务场景下是成立的，但并非所有场景都适用。

为什么大部分场景下Set性能更优 #

JS 引擎（以V8为例）中的Set底层基于有序哈希表实现，你给出的时间复杂度对比是完全准确的：

const set = new Set();
set.add(someValue)            // 平均O(1)时间
set.delete(someValue)         // 平均O(1)时间
set.has(someValue)            // 平均O(1)时间

const ll = new LinkedList();
ll.append(someValue)          // O(1)时间
ll.deleteHead()               // O(1)时间

// 从链表任意位置删除元素
ll.delete(someValue)          // O(n)时间
ll.contains(someValue)        // O(n)时间

普通链表的随机查找、任意位置按值删除都需要遍历全表，在需要频繁做元素存在性校验的场景下，和Set的性能差距会非常大。

存在哪些链表更有优势的场景 #

即使是处理无重复数据，以下场景链表的表现会优于Set：

• 需要在指定元素相邻位置插入/删除的场景
  Set只能在尾部追加元素，没有提供在指定元素前/后插入新元素的能力，要实现这类操作只能先把Set转成数组、操作后再重建Set，整体开销是O(n)。而如果用双向链表实现，你只要持有指定元素的节点引用，相邻插入/删除操作都是O(1)。
• 频繁操作头尾元素、不需要按值查找的队列/栈场景
  Set没有直接获取、删除头/尾元素的原生API，要删除最早插入的头部元素，需要先通过迭代器拿到头部值再调用delete，开销远大于链表直接deleteHead()的O(1)操作。
• 极端要求内存利用率的大数据量场景
  哈希表为了降低哈希冲突概率，会保留一定比例的空槽位（负载因子通常为0.6~0.8），冗余空间占比更高。链表每个节点仅存储数据和前后指针，内存密度更高，在超大数据量下内存开销会比Set低30%以上。
• 对最坏时间复杂度要求严格的场景
  Set的O(1)是平均时间复杂度，极端情况下出现大量哈希冲突时，操作时间复杂度会退化到O(n)，甚至存在哈希碰撞攻击的风险。而自实现的链表不存在哈希冲突问题，所有操作的时间复杂度都是稳定的。

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