链表实现Set集合

来源：7-7 基于二分搜索树的映射实现

北京_鲁班七号

2018-09-14

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

写回答

1回答

liuyubobobo

2018-09-14

已采纳

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

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

加油！：）

北京_鲁班七号

非常感谢！

2018-09-17

共1条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

回答 1

回答 3

回答 1

回答 1

回答 1