[音楽再生] DOUG LLOYD：すべての権利。 だから、あなただけのことを終了した場合 申し訳ありません重リンクリストの動画 私はであなたをオフに左 接戦のビット。 しかし、私はあなたが最後までここにしてくれてうれしいです 二重リンクリストの物語。 

ですから、から思い出す場合 そのビデオは、私たちは話しました 重リンク方法について リストは、当社の能力に出席行います 情報に対処します どこの要素数 またはアイテムの数で リストには、拡大または縮小することができます。 私たちは今に対処することができます そのような何か、どこ 我々は、配列とそれに対処できませんでした。 

しかし、彼らは1苦しむん クリティカル制限します 重リンクされていることで リスト、我々は今まで移動することができます リストを単一方向インチ そして、唯一の本当の状況 それが問題になることができる場所 我々がしようとしていたときでした 単一の要素を削除します。 そして、私たちもそれを行う方法については説明しませんでした 擬似コードで重リンクリストインチ それは確かになんとかですが、 それが面倒のビットすることができます。 だから、自分自身を見つける場合 どこ状況で あなたは、削除しようとしています リストから単一の要素 またはそれが必要になることになるだろう あなたが削除されますことを から単一の要素 リストには、あなたがお勧めします 二重リンクを使用することを検討します 代わりに一重リンクリストのリスト。 二重リンクリストは、あなたを可能にしていることから 前後の両方を移動します 代わりのリストを ちょうど前方list--を通じて ただ1つの余分な要素を追加することにより、 私たちの構造定義へ 二重リンクリストのノードの。 

繰り返しますが、あなたはするつもりはない場合 単一の要素を削除します list--から、私たちは追加しているので、 私たちの構造への追加フィールド 定義、ノード自身 二重リンクリストの 大きくなるとしています。 彼らは取るつもりです メモリのバイト以上アップ。 そして、もしそうなら、これはものではありません あなたは何をする必要があるとしています、 あなたはそれがだ決めるかもしれません トレードオフの価値もありません 余分を過ごすために持っています メモリのバイトが必要 二重リンクリストのためにあなたがいないのであれば 単一の要素を削除することになるだろう。 しかし、彼らはまた、クールです あまりにも他のもののために。 

私が言ったように、私たちは追加する必要があります 私たちの構造への1つのフィールド この概念definition-- 前ポインタの。 片方向リンクリストのですから、 、値と次のポインタを持っています そう二重リンクリストは、単に持っています 同様に後方に移動する方法。 

今一重リンクで 我々は話をリストビデオ、 これらについての5です あなたがする必要があります主なもの リンクされたリストで動作するように行うことができます。 そして、これらのほとんどの、事実 それは二重リンクリストだこと 本当に大きなジャンプではありません。 我々はまだちょうどによってを通じて検索することができます 最初から最後まで前進。 我々はまだ外のノードを作成することができます 薄い空気、ほとんど同じように。 私たちはかなりのリストを削除することができます あまりにも多くの同じように。 その唯一のもの 微妙に異なっており、 本当に、挿入されています リストに新しいノード、 そして、我々は最終的に削除について話しましょう 同様に、リストから単一の要素。 ここでも、かなり 私たちがしている他の3、 それらについて話をするつもりはありません 今、彼らはただだから 議論のアイデアに非常にマイナーな改良 重リンクリストビデオインチ 

それでは、新しいノードを挿入してみましょう 二重リンクリストへ。 我々はこのことについて話しました 同様にリストを、片方向リンク、 しかし余分のカップルがあります 二重リンクリストをキャッチします。 私たちは[ですか？渡す？]の頭の中で ここにリストといくつかの任意の値、 私たちは、新しいヘッドを取得したいです この機能のうち、リストの。 それはdllnodeスターを返す理由です。 だから手順は何ですか？ これらは、再び、非常に類似しています 重リンクするリスト 1つの余分な追加されています。 我々は新しいのためのスペースを割り当てたいです ノードとチェックは、それが有効だことを確認します。 私たちは、そのノードを埋めるためにしたいです どのような情報を私たち それに載せていきたいと思います。 我々はdo--する必要がある最後の事 私たちがしなければならない余分なもの、rather-- 前のポインタを修正することです リストの古い頭の。 覚えているので、 二重リンクリスト、 我々は前進することができます そして、backwards--します 各ノードは、実際に指すことを意味し 他の2つのノードへの代わりに一つだけ。 だから、我々は修正する必要があります リストの古いヘッド の新しいヘッドに後方に指すように 何かしたリンクリスト、 我々は前に行う必要はありませんでした。 前と同じように、私達はちょうど返します リストの新しい先頭へのポインタ。 

だからここにリストがあります。 我々は、このリストに12を挿入します。 図がいることに注意してください 若干異なります。 各ノードは3 fields--が含まれています データ、および赤の次のポインタ、 青の前のポインタ。 何も、15ノードの前に来ることはありません ため、その前のポインタはNULLです。 これは、リストの先頭です。 その前には何もありません。 そして、何も10ノードの後に​​来ることはありませんし、 ので、次のポインタだとしてもnullです。 

それでは、このリストに12を追加してみましょう。 私たちは、ノードの[聞こえない]のスペースを必要としています。 私たちは、その中に12を置きます。 そして再び、私たちは本当にする必要があります チェーンを壊さないように注意してください。 私たちは、再配置したいです 正しい順序でのポイ​​ンタ。 そして、時にはそれがmean--可能性があります 我々は特に見るよう 我々はいくつかを持っているんdelete--と 冗長ポインタが、それは大丈夫です。 

だから我々は最初に何をすべきかをしたいですか？ 私がお勧めします あなたはおそらくべき事 12のポインタを埋めるためにあるん あなたは誰に触れる前に、ノード。 それでは、12は、次を指すように起こっていますか？ 15。 何が12の前に来ますか？ 何もありません。 今、私たちは満たされました 12で追加情報 それは、前のページ次のページ、および値があります。 

今、私たちは15--この余分なを持つことができます 私たちabout--話していたステップ バック12から15ポイントを持つことができます。 そして今、我々はの頭を移動することができます また、12なるようにリンクされたリスト。 だから、私たちにかなり似ています 重リンクリストをやっていました、 の余分なステップを除き、 リストの古い頭を結びます リストの新しいヘッドにバックします。 

今度は、最終的に削除させて リンクされたリストからノード。 それでは、私たちは持っているとしましょう 他のいくつかの機能その 我々は削除するノードを見つけることです そして、正確に私たちのポインタを与えています 我々は削除するノード。 私たちも、need--言うことはありません 頭はまだグローバルに宣言されています。 ここでは、ヘッドを必要としません。 すべてこの機能がやっている私たちはきています 正確ノードたちへのポインタを見つけました を取り除きたいです。 のは、それを取り除くしてみましょう。 これは、と非常に簡単です 二重リンクリスト。 それが実際ですFirst-- ちょうどカップルの事。 私達はちょうど、周囲を修正する必要があります ノードのポインタ彼らはスキップするように ノードは、我々は削除します。 そして、我々は、そのノードを削除することができます。 だからもう一度、私たちはここを通過しています。 我々は明らかにすることを決定しました 我々は、ノードXを削除したいです そして再び、私は何です way--によってhere--やっ 以下のための一般的なケースであります 中央にあるノード。 がいくつかあります そのあなたの余分な注意事項 あなたが削除しているときに考慮する必要があります リストの先頭 またはリストの最後。 特別のカップルがあります そこに対処するためのコーナーケース。 

だから、これは、任意のノードを削除するために働きます そのlist-- 1の途中で 前方に合法的なポインタを持っています 後方と合法的なポインタ、 正当前と次のポインタ。 繰り返しますが、作業している場合 末端を有する、あなた それらを処理する必要があります 若干異なります、 私たちはするつもりはありません 今それについて話しています。 しかし、あなたはおそらくすることができます 必要なものを見つけ出します このビデオを見て、単に行うことができます。 

だから我々は孤立しましたXのXはノードです 我々は、リストから削除します。 私たちは何をしますか？ まず、再配置する必要があります 外のポインタ。 私たちは再配置する必要があります 9の次は13をスキップします ポイントは10--するためにどの 我々だけでやったものです。 そして、我々はまた、する必要が 10の前に並べ替え 9にポイントの代わりに13を指します。 

だからもう一度、これがありました で開始するための図。 これが私たちの連鎖でした。 私たちは、13をスキップする必要があります 我々はまた、保存する必要があります リストの整合性。 我々は、いずれかを失いたくありません いずれかの方向に情報を表示します。 だから我々は再配置する必要があります ポインタ慎重に 私たちは、すべてのチェーンに不具合が発生していません。 

だから我々は、9の次のポインタを言うことができます 同じ場所を指します その13の次の 今ポインタポイント。 我々は最終的にしているため、 13をスキップしたいだろう。 だから、どこに13ポイントの横には、 9ではなくそこに指すようにしたいです。 だから、それです。 そして、どこに13ポイントバック 13の前に来るものは何でも、 我々はポイントに10をしたいです その代わりに13に。 あなたが従うならば今、気づきます 矢印は、我々は13をドロップすることができます 実際に任意の情報を失うことなく。 私たちは、リストの整合性を保ってきました 順方向および逆方向の両方に移動します。 そして、我々はただ並べ替えることができます 少しそれをクリーンアップします 一緒にリストを引いて。 だから我々は、再配置しました 両側のポインタ。 そして、我々は、X解放しました 13が含まれていたノード、 我々はチェーンを壊しませんでした。 だから我々はよくやりました。 

ここにリンクされたリストの最後の注意。 だからsingly-両方と二重リンク リスト、我々が見てきたように、 サポートは本当に効率的な挿入 要素の削除。 あなたはかなり行うことができます 一定時間内にそれ。 我々は削除するために行うために何をしなければなりませんでした 要素だけ秒前？ 私たちは一つのポインタを移動しました。 私たちは別のポインタを移動しました。 我々はX--は3つの操作をした解放されました。 それは、常に3つの操作にかかります ノードを解放することnode--を削除します。 

私たちはどのように挿入するのですか？ さて、私たちは常にしています 初めにタック 我々は効率的に挿入している場合。 だから我々はrearrange--する必要があります それはだ場合に応じて singly-または二重リンク リストは、3つが必要になることがあります または4つの操作を最大。 しかし、再び、それは常に3つまたは​​4つのます。 それはどのように多くの問題ではありません。 要素は、私たちのリストにあり それは、常に3つまたは​​4つのoperations--です 削除は常に同じように 3つまたは​​4つの操作。 これは、一定の時間です。 だから、本当に素晴らしいことです。 

アレイでは、我々がやっていました 挿入ソートのようなもの。 おそらく、その挿入を思い出します ソート一定時間アルゴリズムではありません。 それは実際にはかなり高価です。 だから、これは挿入するための多くの良いです。 しかし、私が述べたように 重リンクリストビデオ、 我々は正しい、ここにも欠点を持っていますか？ 私たちはする能力を失ってしまいました ランダム要素にアクセスします。 私たちは、私は要素番号4をしたい、と言うことはできません リンクされたリストまたは要素番号10 同じように我々はできます アレイにそれを行います または私達はちょうど直接インデックスすることができます 私たちの配列の要素に。 

そしてそう見つけるしようとし リンクlist--の要素 検索はimportant--ある場合 今線形時間がかかることがあります。 リストが長くなると、それ 一つの追加のステップがかかる場合があります で、リスト内のすべての単一の要素のための 我々が探しているものを見つけるために。 だから、トレードオフがあります。 プロのビットがあります ここでコン要素。 

そして、二重リンクリストはありません データ構造の組み合わせの最後の種類 我々はについて話すだろうと、 すべての基本的な建物を取ります Cのブロックは一緒に入れて。 実際には、我々は可能性があるため でもこれよりも良い行います そのデータ構造を作成します あなたがを検索することができるかもしれません 一定時間内に、あまりにも。 しかし、別のビデオでその上より。 

私はダグロイドです。 これはCS50です。