面接官:すでに配列がある以上、なぜチェーンテーブルを作るのですか。

本文は微信プラットフォームに発表された:プログラマー面接官
20 w字を超える「フロントエンド面接とステップアップガイド」はgithubに移動できます
多くの開発者にとって、チェーンテーブル(linked list)というデータ構造はよく知られているし、よく知られているのは確かに非常に基礎的なデータ構造であるため、よく知られていないのは私たちが業務開発でそれを使う確率が確かに大きくないからだ.
多くの場合、配列で作業をうまく行うことができ、あまり違いは生じません.チェーンテーブルの存在の意味は何ですか.チェーンテーブルは配列に比べて何かメリットや不足がありますか?

チェーン時計とは

チェーンテーブルは一般的な基礎データ構造である、線形テーブルであるが、線形の順序でデータを記憶するのではなく、各ノードに次のノードに格納ポインタ(Pointer)である.
本質的に言えば、チェーンテーブルと配列は確かに似ている点があり、彼らの同じ点はすべて線形データ構造であり、これは木と図とは異なり、それらの違いは配列が連続メモリであることであり、チェーンテーブルは連続メモリではなく、チェーンテーブルのノードとノードの間にポインタで連絡することができる.
もちろん、チェーンテーブルにも異なる形態があり、主に3種類に分けられる:一方向チェーンテーブル、双方向チェーンテーブル、循環チェーンテーブル.

たんほうこうチェーンテーブル

一方向チェーンテーブルのノードは、通常、ノードが格納値valと、ノードのポインタnextとの2つの部分から構成される.
チェーンテーブルは配列と同様に、検索、挿入、削除、読み取りなどの操作も可能であるが、チェーンテーブルと配列の特性が異なるため、操作の複雑さが異なる.

パフォーマンスの検索

一方向チェーンテーブルの検索操作は、通常、次のようになります.

は、先頭ノードから入る、対ノードの値の比較を開始し、異なる場合はポインタによって次のノード

に入る.

上記の動作を繰り返し、同じ値が見つかるまで、またはノードのポインタがnull

を指す.
チェーンテーブルの検索性能は配列と同様に時間複雑度がO(n)である.

削除のパフォーマンスの挿入

チェーンテーブルと配列の最大の違いは、削除、挿入の性能の優位性にあり、チェーンテーブルは非連続メモリであるため、配列のように挿入、削除操作の際に大きな面積のメンバーシフトを行う必要はありません.例えば、a、bノードの間に新しいノードcを挿入し、チェーンテーブルは以下の必要があります.

aはbを指すポインタを切り離し、c

を指す.

cノードはポインタをbに向け、

を終了する.
この挿入操作はポインタを動かすだけでよい、挿入、削除の時間的複雑さはO(1)のみである.
チェーンテーブルの挿入操作は次のとおりです.
チェーンテーブルの削除操作は次のとおりです.

読み取りパフォーマンス

チェーンテーブルに比べても、読み出し操作が配列にはるかに及ばず、配列の読み出し操作が効率的であるのは、連続メモリであるため、配列の読み出しはアドレス式によって迅速に位置決めことができ、チェーンテーブルは非連続メモリであるため、指針によって1つのノードを遍歴しなければならないという劣勢がある.
例えば、1つの配列について、3番目のメンバーを読み出すには、arr[2]でメンバーを迅速に取得する必要があり、チェーンテーブルはヘッダノードから入る必要があり、ポインタで後続のノードに入る必要がある.

シーンの適用

双方向チェーンテーブルの存在により、一方向チェーンテーブルの適用シーンは比較的少ない、多くのシーンの双方向チェーンテーブルがより優れて完成できるためである.
しかし、一方向チェーンテーブルは役に立たないわけではありません.以下のシーンでは、一方向チェーンテーブルの姿があります.

取り消し機能は、各種テキスト、グラフィックエディタに多く見られるが、取り消しやり直しはエディタシーンでは日常茶飯事であり、一方向チェーンテーブルは良好な削除特性のため、このシーンでは

に適している.

実装図、hashMapなどのいくつかの高度なデータ構造

にほうこうチェーンテーブル

前述のように、一方向チェーンテーブルの応用シーンは多くないが、本当に生産環境で広く運用されているのは双方向チェーンテーブルである.
双方向チェーンテーブルは一方向チェーンテーブルと比較して何か特別な点がありますか?
双方向チェーンテーブルに新しいポインタprevがノードの前のノードを指すのを見たが、もちろんポインタが1つ増えたため、双方向チェーンテーブルはよりメモリを占める.
双方向チェーンテーブルに前置ポインタが1つ増えたことを軽視しないでください.多くのシーンでは、このポインタが多くなったため、効率が高く、実用的です.
例えばエディタの「undo/redo」操作は、双方向チェーンテーブルがより適用され、前後ポインタを持つため、ユーザは前後操作を自由に行うことができ、これが一方向チェーンテーブルである場合、ユーザがチェーンテーブルを遍歴する必要がある場合の時間複雑度はO(n)である.
実際の生産レベルのアプリケーションではエディタが採用するデータ構造と設計モードはもっと複雑で、例えばWordはPiece Tableデータ構造とCommand queueモードを採用して「undo/redo」を実現しているが、これは後の話である.

ループチェーンテーブル

ループチェーンテーブルは、その名の通り、一方向チェーンテーブルの末尾ポインタをチェーンテーブルヘッダノードに向けています.
ループチェーンテーブルの1つの応用シーンはオペレーティングシステムの時間分割の問題であり、例えば1台のコンピュータがあるが、複数のユーザーが使用しているので、CPUが複数のユーザーの要求を処理するとリソースを奪う可能性が高い.この時、コンピュータは時間分割戦略を取って各ユーザーの使用体験を保証する.
各ユーザはループチェーンテーブル上のノードと見なすことができ、CPUは各ノードに一定の処理時間を割り当て、一定の処理時間後に次のノードに入り、無限にループすることで、各ユーザの体験を保証することができ、1人のユーザがCPUを奪い取って他のユーザが応答できない場合がない.
もちろん、ジョセフ環の問題は一方向循環チェーンテーブルの代表的な応用であり、興味のあるものは深く理解することができる.
もちろん双方向チェーンテーブルの首尾はつながっていますか?これが双方向ループチェーンテーブルである.
ノードにはクエリーがなく、大量の挿入と削除があるシーンがあります.これがTimerモジュールです.ほとんどのネットワークI/O要求は、timeout操作制御socketのタイムアウト状況を提供する、ここではsettimeoutに大量に使用され、これらのtimeoutタイマのほとんどは使用できない(データが時間通りに正常に応答する)ので、応答するcleartimeout操作が大量に行われるため、nodeは双方向ループチェーンテーブルを採用してTimerモジュールの性能を向上させ、その詳細は後述しない.

                                             ！
TimersList  timer1  timer2  timer4  timer3  ......
                1000ms        1050ms       1100ms       1200ms   

小結

これにより,チェーンテーブルというデータ構造について一定の認識が得られ,その非連続メモリの特性によりチェーンテーブルは頻繁に挿入・削除されるシーンに非常に適しており,読み取りシーンよりも長くなく,配列の特性と適切に相補的に形成されているため,現在では問題に戻ることができ,チェーンテーブルの特性は配列と相補的であり,それぞれ長さがあり,チェーンテーブルはポインタの存在によってリングチェーンテーブルを形成することができる.特定のシーンでも便利なので、チェーンテーブルの存在が必要です.
では、今よくある面接の思考問題があります.
私达がふだん使っている微信の小さいプログラムは最近使う机能があって、时间の最近のは最も上で、时间の顺番によって后ろに并んで、使った小さいプログラムが一定の数より大きい时、最もよく使わない小さいプログラムは现れなくて、あなたはどのようにこのアルゴリズムを设计しますか?