リンクリストでキューを実装します。なぜ頭に挿入して尾を取り除くのが悪いのでしょうか？

Question

私の教科書、Javaのデータ構造、アルゴリズムでは、著者は、リンクリストを使用してキューを実装するときに、リストのヘッドにあるキューの前面を選択し、キューの背面を選択します。リスト。このようにして、頭から取り出して尾に挿入します。

著者はその後、「なぜ頭に挿入して尾を取り除くのが悪いのか」と不可解に尋ねます。答えを提供することなく。

違いが本当に何なのかわかりません。実際には、「ヘッド」と「テール」は、私たちが定義する任意の名前です。 enqueue（）に頭を追加して古い頭への参照を作成すると、尾から引っ張って尾を動かした場合、何がそんなに悪いでしょうか？

著者の質問に対する答えは何ですか？

Answer 1

単一のリンクリストでは、すべての要素には次の要素へのポインターがあります。テール要素への追加のポインタがある場合、それはあなたに一定の数のOG操作を取得します 追加 尾のリストに：テールポインターを取得し、尾の後に要素を追加し、この新しい要素を新しい尾として置きます。頭から削除するには、一定の数の操作も必要です。新しいアイテムを新しいアイテム、ヘッド、ポイントオールドヘッドにします。

でも、 削除 尾から、現在の尾の前身へのポインターが必要です。これには、要素があるのと同じくらい多くの操作が必要です。

もう1つの解決策は、二重リンクリストを使用することです。その後、何を選択できますが、メモリの2倍を使用します。

Answer 2

頭から離れて尾に挿入することは、頭と尾のポインターを想定して、単独でリンクされたリストを使用した一定の時間操作です。尾に挿入することも一定の時間です。しかし、尾から離れるということは、尾のポインターを頭に向かって動かすことを意味します。バックポインターがないため、リスト全体を横断して尾の前に要素を見つけることなく、それを行うことはできません。これにより、挿入は一定の時間操作ではなく線形時間になり、それが悪化します。