面试题：Java中LinkedList插入删除效率相关问题

Question

在Java的LinkedList中，向链表头部插入一个元素和向链表尾部插入一个元素，在时间复杂度上有什么区别？请解释原因。

Answer 1

1. 向链表头部插入元素：
   • 时间复杂度：$O(1)$。
   • 原因：在Java的LinkedList中，它维护了一个指向链表头节点的引用（first）。当向链表头部插入元素时，只需创建新节点，然后将新节点的next指针指向原头节点，再把链表的头节点引用指向新节点即可。这些操作不依赖于链表的长度，无论链表有多长，都可以在固定时间内完成，所以时间复杂度为$O(1)$。
2. 向链表尾部插入元素：
   • 时间复杂度：$O(1)$。
   • 原因：Java的LinkedList不仅维护了头节点引用（first），还维护了尾节点引用（last）。向链表尾部插入元素时，创建新节点，将尾节点的next指针指向新节点，然后更新尾节点引用为新节点。同样，这些操作不依赖于链表的长度，可在固定时间内完成，因此时间复杂度也是$O(1)$。

总体来说，在Java的LinkedList中，向链表头部插入元素和向链表尾部插入元素在时间复杂度上没有区别，均为$O(1)$。