在实践中是链表加O(N)或O(1)

Question

据说链表中的添加和删除是在恒定的时间内发生的，即O（1），但对元素的访问是在与列表大小成比例的时间内进行的。我的问题是，如何在不首先遍历的情况下删除或添加任何元素？在这种情况下，增加或删除的顺序不是O（N）吗？

以Java为例，当我们使用这样的api时会发生什么：

   LinkedList stamps = new LinkedList();
   stamps.add(new Stamp("Brazil"));
   stamps.add(new Stamp("Spain"));
   ---
   ----
   stamps.add(new Stamp("UnitedStates");  //say this is kth element in the list
   ----
   stamps.add(new Stamp("India");

那么，当有人做stamp.remove（k）时，这个操作怎么会在恒定时间内发生呢？

Answer 1

只有当您有一个指向列表上实际节点的指针时，从链接列表中删除项目才能在恒定时间内工作。如果你唯一拥有的是你想要删除第"n"个节点的信息，那么就无法知道它是哪一个——在这种情况下，你需要首先遍历列表，当然是O（n）。

另一方面，添加总是在恒定的时间内进行，因为它与列表中已经包含的元素数量无关。在提供的示例中，对add（）的每次调用都是O（1），不包括调用类Stamp的构造函数的开销。添加到链接列表只是将另一个元素附加到其末尾。当然，这是假设链表的实现知道哪个节点当前位于列表的末尾。如果它不知道这一点，那么，当然，需要遍历整个列表。