java - 在LinkedList开头插入的时间复杂度

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

另外，插入offerFirst开头的最佳方法是吗？

最佳答案

添加到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时才使用它。