データ構造とアルゴリズム Vol.2

Vol.2: Linked List

この版ではLinked Listの必要性とその使い方について学びます。

Linked Listの必要性

👌 一般的には、配列を使用してデータを順次保存し、一覧表示できます。
👌 排熱を使用する場合、メモリ容量が不要な場合があるからです。

既存の配列ベースリスト

データを順番に保存し、処理するときは配列ベースのリストを簡単に利用できます。

例）

#include <stdio.h>
#define INF 10000

int arr[INF];
int count = 0;

void addBack(int data) {
  arr[count] = data;
  count ++;
}

void addFirst(int data) {
  for (int i = count; i >= 1; i--) {
    arr[i] = arr[i - 1];
  }
  arr[0] = data;
  count++;
}

void show() {
  for (int i =0; i < count; i++) {
  printf("%d", arr[i]);
  }
}

int main(void) {
  addBack(5);
  addBack(8);
  addBack(7);   
  addFirst(3);
  addFirst(4);
  show();
  system("pause");
  return 0; 
}

result-> 4 3 5 8 7

🤔 では、特定の位置の元素を削除する関数はどうやって作成しますか？
特定の位置の元素を削除するremoveAt()関数は以下の通りです。

void removeAt(int index) {
  for (int i = index; i < count -1; i++) {
    arr[i] = arr[i + 1];
  }
  count--;
}

✍ 　配列ベースリストの特徴
- 配列しているので、特定の場所の元素にすぐにアクセスできるというメリットがあります。
- データが入るスペースをあらかじめメモリに割り当てておかなければならないという短所があります。
- 任意の位置への挿入や削除が非効率です。 ➡ 特定の位置に挿入する時、または削除する時は既存の値を一つずつ全部移動させなければならない。

ポインタベースのLinked List

-　一般的にLinked Listは構造体とポインターを一緒に使用して実現します。
-　Linked Listは、リストの中間地点にノードを追加したり削除したりできなければなりません。
-　必要なたびにメモリ容量の割り当てを受けます。

📌 Singly Linked List
単一接続リストは以下のような形で表すことができます。
ポインタを利用して単方向的に次のノードを指します。
一般的に、接続リストの開始ノードをヘッド(Head)といい、別に管理します。
次のノードがない最後のノードの次の位置の値には、NULLを入れます。

例) Linked Listに特定の元素を挿入する方法

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

//一つの構造体にデータとその次ノードを指すnext変数を入れる。
typedef struct Node{
    int data;
    struct Node *next;
} Node;

Node *head; 
//Linkedは常にヘッドノードから出発
//ノードは常にポインタ変数で動的割り当てを利用して変数を作ることができるようにするのが一般的

void addFront(Node *root, int data) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = root->next;
    root->next = node;
}

void removeFront(Node *root) {
    Node *front = root->next;
    root->next = front->next;
    free(front);
}

void freeAll(Node *root) {
    Node *cur = head->next;
    while (cur != NULL) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

void showAll(Node *root){
    Node *cur = head->next;
    while (cur != NULL) {
        printf("%d" , cur->data);
        cur= cur->next;
    }
}

int main(void) {
    head = (Node*) malloc(sizeof(Node));
    head->next = NULL; //常にLinked Listの最後はNullでなければならない。
    addFront(head, 2);
    addFront(head ,1);
    addFront(head, 7);
    addFront(head, 9);
    addFront(head, 8);
    removeFront(head);
    showAll(head);
    freeAll(head);

    return 0;
}

🤔 結果は？
result-> 9 7 1 2

Linked List実装における注意点

❗ 挿入および削除機能での例外事項を処理する必要があります。
❗ 削除する元素がないのに、削除する場合、頭(Head)ノード自体を間違えて入れる場合などをチェックする必要があります。

✍ 　Linked Listの特徴
- 挿入と削除が配列に比べて簡単であるという長所があります。
- 配列と違って特定インデックスに直ちにアクセスできず、元素を順番に検索しなければならないという短所があります。
- 追加的なポインタ変数が使用されるため、メモリスペースが無駄になります。

まとめ

👌 Linked Listはデータを線形に保存して処理する一つの方法です。
👌 従来の配列よりも挿入と削除が多い場合に有効です。
👌 ただ、特定のインデックスにすぐに参照することが多い場合は配列を利用するのが効率的です。

📚参考講義：コンピューター工学専攻必須オールインワンパッケージOnline
👆 上記の講義はCとC++を言語を前提に説明しています。