链表实现Set集合

Question

为什么set集合拿链表实现add方法 调用的是链表addFirst方法 而不是addLast方法

Answer 1

liuyubobobo 2018-09-14 10:46:22

使用addLast也可以，不会改变LinkedListSet的add操作是O(n)复杂度这个事实：）因为我们都需要通过contains方法来确认当前链表内没有待添加元素，而contains方法是O(n)的。

但是由于我们自己实现的LinkedList没有维护尾指针，所以，在链表头添加元素是O(1)的，而在链表尾添加元素需要先扫描整个链表到最后的位置，再添加。所以单纯从addFirst和addLast的角度，我们实现的链表，addFirst是O(1)的，addLast是O(n)的：）

加油！：）

• 提问者 北京_鲁班七号 #1

  非常感谢！