使用循环

Question

比方说，我做的添加n个元素，一个LinkedList的复杂以下几点：

for(int i = 0; i < n; i++) { 
    list.add(i); 
} 

在这样的复杂性应为O（n ）如果没有尾指针，对不对？ （因为每个插入都是O（n），我做了n次插入？）但是如果有尾指针，它将是O（n），对吗？

Answer 1

是的，这是正确的。使用尾指针，您可以在O（1）的时间内通过尾指针指向的元素将值附加到链表中，更新“下一个”指针，然后更新尾指向新元素。总运行时间将是O（n）。

另一方面，没有尾指针，找到列表的最后一个元素，以便您可以更新其指针将花费时间O（n），因为列表中的所有元素都必须被扫描。因此，总运行时间将为O（n ）。

希望这会有所帮助！