Array vs Linked List – Difference between Array and Linked List

コンピュータのメモリ内にデータがどのように格納されるか、疑問に思ったことはありませんか。

すべてのプログラミング言語は、int、char、float などの基本的なデータ構造を提供し、プリミティブ型の値を格納します。 しかし、ユーザー定義のデータ型を使用すると、必要に応じてデータ構造を作成することができます。 これは、レンガで家を作るようなもので、必要な構造の任意のタイプを作成できます。

Array

データ構造の最も単純なタイプは配列で、共通の見出しまたは変数名の下に、メモリの連続したブロックに類似したデータのセットを格納するために使用します。

Array Representation

Array Representation (Source)

Array のインデックスは 0 で始まり、配列のすべての要素はそのインデックスを使ってアクセスすることができる。 配列のインデックスを使用すると、任意の要素に直接アクセスできるため、配列に対する操作は非常に高速になります。

Linked List

一方、連続したメモリブロックを必要としない、シンプルで非常に便利なデータ構造がリンクされたリスト(Linked List)です。 プログラムの実行中に動的にメモリを割り当てる必要がある場合に使用されます。 これは、エンジン (ヘッド) があり、すべての車両 (ノード) が直接または他の車両を介して間接的に列車のエンジンにリンクされている列車のように視覚化することができます。 リストの任意のノードにアクセスするには、要素に直接アクセスできる配列とは異なり、リストを線形にトラバースする必要があります。

Array vs Linked List – Array と Linked List の違い

共通名を持つ同じデータ タイプの要素コレクションであり、そのデータ型は配列とリンクされます。

Parameters Array Linked List
定義
サイズ 固定、一度宣言すると変更できない。 可変、実行時に変更できる。
メモリ割り当て 連続したメモリブロックが必要。 ランダムにメモリを割り当てることができる。
アクセス 直接またはランダムにアクセス、すなわち、。 配列のインデックスまたは添え字を指定します。 順次アクセス、すなわち、,
挿入と削除 要素を挿入または削除するために、他の要素を移動して空いたスペースを確保する必要があるため、比較的遅い。
検索 バイナリサーチとリニアサーチ リニアサーチ
余分なスペースは必要ない リストのノード間を結ぶにはポインタを使っており、余分のスペースが必要である リスト内のノードをリンクするには、ポインタは使用されているが、これはスペースが必要である。
メモリ使用量 非効率 効率
タイプ 1次元、2次元、多次元、 シングル、ダブル、循環リンクリストがある。

C++ における配列の実装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;
int main()
{
int arr; // サイズ5の整数配列の宣言
arr=5; // 配列要素への値の代入
arr=4; // 配列のインデックスは 0 から始まり、サイズ 1 で終わることに注意
arr=3;
arr=2;
arr=1; for(int i=0;i<5;i++)
cout<<arr<” “; // 配列要素を表示
return 0.0;
}

出力

5 4 3 2 1

C++によるリンクリストの実装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include<iostream>
using namespace std;
/* リンクリストのデータを格納するためのユーザ定義構造の作成 */
struct Node
{
int data;
struct Node *next; // リンクリストのノードへのポインタ
};
struct Node* head = NULL.*NULL;
/* ノードの挿入とリンクの関数 */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // リストには要素がないので、ヘッドはどこも指していない。 // 動的にメモリを確保する
new_node->data = new_data;
new_node->next = head;
head = new_node;
} }.
/* リストのデータを表示する関数 */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr !*) {
リスト内のデータを表示する関数。= NULL)
{
cout<< ptr->data <<” “;
ptr = ptr->next;
} ←クリックすると拡大します。
}
int main()
{
insert(5); // リストにデータを挿入する
insert(1);
insert(4);
insert(6);
insert(7); // リンクリストは、です。 “;
display();
return 0;
}

Output

リンクリストは、です。 7 6 4 1 5

Video Tutorial

Leave a Reply

コメントを残す

メールアドレスが公開されることはありません。