2

I am curious about the time complexity of inserting an element at the beginning of a LinkedList. I understand the LinkedList itself will shift the existing elements one index to the right but, to do that, will it make as many iterations as there are existing elements in the list?

Also, is the best way to insert at the beginning offerFirst ?

4

2 に答える 2

7

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したがって、コメントで述べたように、返品が必要な場合にのみ使用してください。

于 2013-07-25T00:41:29.053 に答える
1

リストの先頭に項目を挿入すると、次の 2 つのことだけが行われます (どちらも非常に軽量です)。

1) HEAD ポインターを更新します (これは、最初の要素がどこにあるかを示すポインターです)

2) 新しい要素の NEXT ポインタを古い HEAD 要素に設定します。

これは非常に軽量な操作であり、リンク リストの強みの 1 つです。

私は Java をよく知りませんが、offerFirst はリストの先頭に要素を追加するように設計されているため、おそらくこれが最善の方法です。

于 2013-07-25T00:43:27.383 に答える