在LinkedList开头插入的时间复杂性

Question

我很好奇在LinkedList的开头插入元素的时间复杂性。我知道LinkedList本身会将现有元素向右移动一个索引，但要做到这一点，它会进行与列表中现有元素一样多的迭代吗？

此外，在开头插入offerFirst的最佳方式是什么？

Answer 1

在恒定时间内添加到LinkedList的前面：

public void addFirst(E e) 
{
    addBefore(e, header.next);
}
private Entry<E> addBefore(E e, Entry<E> entry) 
{
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
}

它不受元素需要移位的数组的支持。正如您所看到的，所需要做的只是一组引用重新分配。

编辑：

为了解决您对offerFirst的担忧，它只是：

public boolean offerFirst(E e) 
{
     addFirst(e); 
     return true;
}

因此，正如我在评论中所说，只有当您想要返回boolean时才使用它。

Answer 2

在列表前面插入一个项目只会做两件事（都很轻）：

1） 更新HEAD指针（这是告诉我们第一个元素在哪里的指针）

2） 将新元素的NEXT指针设置为旧HEAD元素。

这是一个非常轻量级的操作，代表了链表的优势之一。

我对Java不是很了解，但由于offerFirst的设计目的是在列表的前面添加一个元素，所以它可能是最好的方法