LinkedListSet中的add的方法不是头部添加一个节点，复杂度是O(1)，为什么是O(n)

Question

Answer 1

liuyubobobo 2018-08-02 01:05:02

由于Set中不能有重复元素，所以使用LinkedList实现Set，添加操作有两种实现方案：

1）添加元素前查重，确认待添加元素和LinkedList中已有元素不重复后直接添加在头结点。此时查重的复杂度是O(n)的；

2）维护LinkedList中的元素有序，每次添加元素的位置根据元素大小决定（在决定元素添加位置的时候顺便查重），此时，添加操作的复杂度是O(n)的；

上述两种方案，基于LinkedList实现Set，添加操作的时间复杂度都是O(n)的：）

• 提问者 慕容9198694 #1

  明白了，谢谢老师