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

Question

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

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

Answer 1

添加到 a 的前面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退货时才使用它。