データ構造は、使用する言語に関係なく、コンピュータサイエンスとプログラミングの基本的な側面です。それらについての完全な知識があると、データを効率的に整理、管理、保存、および変更するのに役立ちます。ユースケースに適したデータ構造を特定することで、パフォーマンスを大幅に向上させることができます。
ただし、JavaScriptには、デフォルトで配列やオブジェクトなどのプリミティブデータ構造のみが付属しています。しかし、ECMAScript 6(ES6)クラスの導入により、プリミティブデータ構造を使用してスタックやキューなどのカスタムデータ構造を作成できるようになりました。
スナップチャットでブロックされたかどうかを確認する方法
スタックデータ構造
スタックデータ構造により、LIFO(後入れ先出し)方式で既存のデータの上に新しいデータをプッシュできます。この線形データ構造は、簡単な例を使用して簡単に視覚化できます。テーブルの上に置かれたプレートのスタックを考えてみましょう。スタックの一番上からのみプレートを追加または削除できます。
JavaScript配列を使用してスタックデータ構造を実装する方法は次のとおりです。 ES6クラス :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}
スタックで実行できる操作のいくつかを調べて構築してみましょう。
プッシュ操作
プッシュ操作は、新しいデータをスタックに挿入するために使用されます。 pushメソッドを呼び出すときに、データをパラメーターとして渡す必要があります。データを挿入する前に、スタックのトップポインタが1つインクリメントされ、新しいデータが一番上の位置に挿入されます。
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}
ポップオペレーション
ポップ操作は、スタックの最上位のデータ要素を削除するために使用されます。この操作を実行している間、トップポインタは1減少します。
pop() {
if (this.top <0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}
ピーク操作
ピーク操作は、スタックの最上位に存在する値を返すために使用されます。このデータを取得するための時間計算量はO(1)です。
もっと詳しく知る: Big-O表記とは何ですか?
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}
リンクリストのデータ構造
リンクリストは、ポインタを使用して相互に接続された多数のノードで構成される線形データ構造です。リスト内の各ノードには、データと、リスト内の次のノードを指すポインター変数が含まれています。
詳細:プログラマー向けポインターの概要
スタックとは異なり、JavaScriptでのリンクリストの実装には2つのクラスが必要です。最初のクラスは ノード ノードを作成するためのクラスであり、2番目のクラスは LinkedList リンクリストですべての操作を実行するクラス。ヘッドポインタはリンクリストの最初のノードを指し、テールポインタはリンクリストの最後のノードを指します。
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
リンクリストで実行できる主な操作は次のとおりです。
追加操作
追加操作は、リンクリストの最後に新しいノードを追加するために使用されます。新しいノードを挿入するためのパラメーターとしてデータを渡す必要があります。まず、を使用して新しいノードオブジェクトを作成します 新着 JavaScriptのキーワード。
リンクリストが空の場合、ヘッドポインタとテールポインタの両方が新しいノードを指します。それ以外の場合は、テールポインタのみが新しいノードを指します。
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
return this;
}
挿入操作
特定のインデックスに新しいノードを挿入するには、挿入操作を利用できます。このメソッドは、挿入するデータと挿入されるインデックスの2つのパラメーターを取ります。最悪の場合、このメソッドはリスト全体をトラバースする必要があるため、時間計算量がO(N)になります。
insert(data, index) {
if (index this.size) return undefined;
if (index === 0) {
this.head = new Node(data, this.head);
!this.tail ? (this.tail = this.head) : null;
this.size++;
return this;
}
if (index === this.size) return this.append(data);
let count = 0;
let beforeNode = this.head;
while (count !== index) {
beforeNode = beforeNode.next;
count++;
}
const newNode = new Node(data);
let afterNode = beforeNode.next;
newNode.next = afterNode;
beforeNode.next = newNode;
this.size++;
return this;
}
削除操作
削除操作は、リンクリストをトラバースして、削除されるノードへの参照を取得し、前のノードのリンクを削除します。挿入操作と同様に、削除操作も最悪の場合O(N)の時間計算量を持ちます。
deleteNode(index) {
if (index === 0) {
const removedHead = this.head;
this.head = this.head.next;
this.size--;
this.size === 0 ? (this.tail = null) : null;
return removedHead;
}
if (index === this.size - 1) {
if (!this.head) return undefined;
let currentNode = this.head;
let newTail = currentNode;
while (currentNode.next) {
newTail = currentNode;
currentNode = currentNode.next;
}
this.tail = newTail;
this.tail.next = null;
this.size--;
this.size === 0 ? ([this.head, this.tail] = [null, null]) : null;
return currentNode;
}
if (index this.size - 1) return undefined;
let count = 0;
let beforeNode = this.head;
while (count !== index - 1) {
beforeNode = beforeNode.next;
count++;
}
const removedNode = beforeNode.next;
let afterNode = removedNode.next;
beforeNode.next = afterNode;
removedNode.next = null;
this.size--;
return removedNode;
}
キューのデータ構造
キューのデータ構造は、キューに立っている多数の人々に似ています。最初にキューに入った人が他の人より先に出されます。同様に、この線形データ構造は、FIFO(先入れ先出し)アプローチに従ってデータを挿入および削除します。このデータ構造は、次の方法でリンクリストを使用してJavaScriptで再作成できます。
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}
JavaScriptでキューにデータを挿入したりキューからデータを削除したりする方法は次のとおりです。
故障したハードドライブの兆候
エンキュー操作
エンキュー操作は、新しいデータをキューに挿入します。このメソッドの呼び出し中に、キューのデータ構造が空の場合、フロントポインタとリアポインタの両方が、キューに新しく挿入されたノードを指します。キューが空でない場合、新しいノードがリストの最後に追加され、後部ポインターがこのノードを指します。
enqueue(data) {
const newNode = new Node(data);
if (!this.front) {
this.front = newNode;
this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
return this;
}
デキュー操作
デキュー操作により、キューの最初の要素が削除されます。デキュー操作中、ヘッドポインタはリストの2番目のノードに移動します。この2番目のノードがキューの先頭になります。
dequeue() {
if (!this.front) return undefined;
if (this.front === this.rear) this.rear = null;
const dequeuedNode = this.front;
this.front = this.front.next;
this.size--;
return dequeuedNode;
}
データ構造後の次のステップ
データ構造は、特にプログラミングに不慣れな場合は、理解するのが難しい概念になる可能性があります。ただし、他のスキルと同様に、練習は、アプリケーションにデータを保存および管理するための効率を真に理解し、評価するのに役立ちます。
アルゴリズムはデータ構造と同じくらい便利で、プログラミングの旅の次の論理的なステップになる可能性があります。では、バブルソートなどのソートアルゴリズムから始めてみませんか?
共有 共有 つぶやき Eメール バブルソートアルゴリズムの紹介バブルソートアルゴリズム:配列のソートの優れた入門書。
次を読む 関連トピック- プログラミング
- JavaScript
- プログラミング
- コーディングチュートリアル
Nitinは、熱心なソフトウェア開発者であり、JavaScriptテクノロジーを使用してWebアプリケーションを開発するコンピューターエンジニアリングの学生です。彼はフリーランスのWeb開発者として働いており、自由な時間にLinuxとプログラミングのために書くのが好きです。
NitinRanganathのその他の作品ニュースレターを購読する
ニュースレターに参加して、技術的なヒント、レビュー、無料の電子書籍、限定セールを入手してください。
購読するにはここをクリックしてください