双方向リストについて

[kuu]

こんばんは
今回質問したのは双方向リストと線形リストの違いについてです。

「双方向リストと線形リストでは、双方向リストのほうが高速」と、あるサイトに書いてありましたが、プログラムを見てみると、
双方向リストでも線形リストでも、ループ処理をしてるので結局速度は変わらないのではないでしょうか？
しかも、追加の仕方もただ「前にもアクセスできる」というだけで、基本的に線形リストと同じやり方でした。
それどころか、線形リストよりも複雑だし・・・。
双方向リストと線形リストの違いは「前にアクセスできる」というだけなのでしょうか？

また、循環リストもありますがあれもただ循環してるだけで、高速になるわけでもないし使いどころがよくわかりません。

こんなバカな質問ですが、よろしくお願いします。

[nil]

双方向リストと線形リストでは線形リストのほうが高速になるのではないでしょうか。
双方向リストは線形リストに比べ処理が若干増えますし、前の要素へのポインタを所持する分構造体のサイズが大きくなり、
その分変数の動的確保に時間がかかります。

双方向リストと線形リストの違いは前にアクセスできる、という点のみです。
ただし、これが結構重要で、
線形リストの場合、要素の削除をするときに前の要素のポインタがわからないため、これに若干の制約がかかります。
対して双方向リストの場合、自由に要素の削除ができます。
また、要素の追加をしたい場合に、線形リストは指定した要素の後ろにしか追加できませんが、双方向リストでは前に要素を追加できます。

違いについては少し調べた程度の知識しかないため、間違っているところなどあるかもしれませんが、だいたいこのような感じだと思います。

[non]

前に戻ることができるという意味でいえば、条件によっては双方向の方が早い場合もあるかもしれませんね。
単方向でも1個前も覚えておいて、検索した場所の前にノードを追加したり、検索したノードを再度、先頭から調べなくても削除することができます。

[kuu]

なるほど・・・
線形リストのほうが高速だけど削除が面倒、双方向リストは線形リストよりは遅いけど削除が楽ということ。
ということは、線形リストも双方向リストも追加の仕方など、基本的に同じように組んでもいいということですね

nonさんが言うように、やはり、ケースバイケースということですか。

とても早いご回答ありがとうございます！解決しました！