JavaScriptにおける連結リストの実装とLeetcodeインタビュー問題への解決

導入

計算機科学において,noデータ構造は,効率的なアクセスと修正を可能にするデータ組織,管理,記憶形式である.データ構造は大量のデータを効率的に管理する手段を提供する.
配列、リンクリスト、レコード、ユニオン、バイナリツリー、グラフを含むデータ構造のさまざまな種類があります.
この記事では、リンクリスト、それは実装、様々な方法をリンクリストといくつかのインタビューの質問に行うことができます見ていきます.

どのようなリンクリストですか？

対角リストともいう.ノードは任意のデータ型(原始または非原始)です.各ノードは値を持ち、リンクリストの次のノードにポイントします.すなわち、ノードは次のノードを意識している.

リンクリストは、配列の後の2番目の最も使用されるデータ構造です、そして、それは配列と類似しています.リンクリストのエントリポイントはheadと呼ばれ、最後のノードはNULLを指します.リンクされたリストが空の場合、頭はNULLになります.

連結リストの種類

があるthree リンクリストの基本的な型は、

シンボリックリンクリスト:これは最も単純なタイプで、各ノードはデータと次のノードへのポインタを持っています.これは、一方向にデータの横断を許可します.

二重リンクリスト:これはそれぞれのノードが前のノードと次のノードを指すデータと2つのポインタを持つ複合型です.データの横断は双方向です.

円形のリンクリスト:これは、最初のノードとその逆の最後のノードポイントを持つシンボリックリンクリストに似ています.円形の好きなリストを横断しながら、我々は任意のノードで起動することができますし、我々が開始した同じノードに到達するまで任意の方向と後方にリストを横断します.このように、円形のリンクリストは開始および終了を有しない.

なぜリンクリストを使用しますか？

配列のように、LinkedListはデータの追加、削除、挿入のようなすべての操作を行う線形データ構造です.以下はリンクリストの利点です.

挿入と削除:配列の最初に要素を追加すると、項目を並べ替えて、大きなデータベースに取り組んでいる間、面倒なことになるインデックスをシフトします.リンクリストでは、ノードの次のポインタに存在するアドレスを更新します

サイズ:リンクされたリストのノードがデータが散乱アドレスで存在できるように、次のノードを認識しているので、実行時に変更できないメモリの非散乱ブロック内のデータを格納する配列と異なり、実行時に変更することができる動的なサイズを許容します.

メモリ割り当て:配列の場合、配列の宣言時にコンパイル時にメモリ割り当てが行われます.リンクリストの場合、実行時にデータが追加されたときにメモリが割り当てられます.

メモリの無駄:メモリ割り当てがリンクリストの実行時に行われるので、メモリの無駄はありません.配列で、100のサイズが宣言されて、データを保存するために80だけが利用されるなら.残りの20スペースは無駄です.

実装:スタックやキューなどの線形データ構造は、しばしばリンクリストを使用して簡単に実装されます.

連結リストの制限

メモリの利用:メモリはデータを格納するために必要であり、また、リスト内の次のノードを指します.LinkedListは配列と比較してより多くのメモリを必要とします.

検索操作:リンクリストで、配列のインデックスのような要素への直接アクセスはできません.これは、全体のリストを通過し、時間の無駄につながる可能性が含まれます

メモリの無駄:逆方向の走査が可能なダブルリンクリストでは、ノードは前と前の要素を意識している.これは、使用しない場合は余分なメモリと無駄が必要です.

リンクのリストと配列のための時間の複雑さとビッグO表記！

連結リストの実施

クラスを作りましょうLinkedList リストの初期化head , and tail to null とコンストラクタ関数の長さ0です.

また、リスト内のノードを作成するためにクラスを使用します.これは、new キーワード.

まとめ

Linkedlistのメソッド

prepend () :このメソッドはノードを先頭のリストに追加します.

printdata () :このメソッドはリストに存在するすべてのノードを出力します.これは、ノード、ポインタ、次のノードを示しています.

add () :リンクされたリストの最後のノードとして新しいノードを追加します.

getlength () :リストの長さを返します.

find () :このメソッドは、ノードが引数として渡されたことを検出します.またはnull を返します.

delete () :引数から参照するノードを削除します.

code snippets available on

• code pen
• github

Leetcodeインタビュー

Question 1

問題1の解決

解説
LinkedListのノードを削除すると、ターゲットの先の次のノードへの移動ポインタが含まれます.

 node.val = node.next.val ;

Basically saying, where we have 5 as the val, replace it with next val which is 1. this remove 5 from the node.

node.next = node.next.next;

here, our node is an array, [4,5,1,9]. our node.next.next will be [1,9]. This delete the node and its value.

概要

本稿では、我々は議論したlinkedlist , 種類のlinkedlist , 利益と制限array , leetcode問題に使用できるメソッドとソリューション.
読書ありがとう
あなたが新しい記事を発表したときに通知を取得したいですか?クリックhere
ISIAKA ABDULAHI