リンクされたリストを使用して実装されたスタックADTの時間複雑度

Question

LinkedListを使用して実装されたStack抽象データ型のput（x）関数とget（）関数の時間複雑度はどのくらいですか？

私の最初の考えは、両方ともO（1）であったということでした。しかし、get（）が先頭ノードからリスト内の最後の要素をたどって削除して戻す必要がある場合、get（）関数はO（n）になります。

また、put（x）関数は、新しいノードをインストールする最後のノードを見つけるためにリスト全体を走査しなければなりません。これもO（n）になります。

「特別な」バージョンのLinkedListが使用された場合、リストの最後のノードへのポインタが常に保持されていた場合、これらは両方とも一定の時間操作になります。私はLinkedListの標準実装でこれを利用できないと理解していますか？

Answer 1

リストの最後には挿入する必要はありません。 （単独リンクされた）リストの先頭に挿入すると、両方ともO(1)になります。

スタックは、1,2,3が含まれています

[1]->[2]->[3] 

プッシュ5：

[5]->[1]->[2]->[3] 

ポップ：スタック操作をプッシュする二重リンクリストについて

[1]->[2]->[3], returning 5 

Answer 2

やポップ必要があります両方ともO（1）である。

単一リンクリストがついている場合は、テールだけでなくヘッドにもポインタを保持するという一定のオーバーヘッドがあると仮定して、エンキューとデキューのO（1）キュー操作を行うことができます。また、償却された一定のオーバーヘッドで2つのキューからスタックを作ることができるので、最終的にはO（1）pushとpopを実現できます。