C言語のリンクリストをオブジェクト指向風に書いてみる（PythonとJavaとのコード比較あり）

## はじめに

最近、「C言語でリンクリストを書いてみた」という投稿を2件みかけました。
いずれも、C言語らしい書き方をしておられましたので、オブジェクト指向風な書き方をコメントさせていただきました。

* [リンクリストの練習 その1 - Qiita](https://qiita.com/Kippie/items/b8a0c092b8e9c591b473)
* [C言語　再帰処理とリンクリスト構造を使った数字のリスト - Qiita](https://qiita.com/Kchan_01/items/359a63b796ea90df26ff)

オブジェクト指向風な書き方をすることで、オブジェクト指向の理解の助けになればと思い、本記事を書くことにしました。
難しいオブジェクト指向の考え方は抜きにして、構造体の拡張版＝ユーザ定義型としてクラスを使います。

## リンクリスト

リンクリストについては、他の記事やサイトをご覧ください。
参考： https://ja.wikipedia.org/wiki/連結リスト

まず、リンクリストに使う構造体を2種類用意します。

* `struct node` ： リストの要素
* `struct list` ： `node`をリンクリスト管理

以下のルールでオブジェクト指向風な書き方にします。

* **構造体へのポインタ** を **クラス名** として `typedef` する
* **クラス名** は **最初を大文字** にして **ポインタ型**＝**参照型** であることを明示する
* **クラスの関数名** は **クラス名とアンダースコア** で始めて **名前衝突** を避ける
* メモリ獲得関数名は **`new`** にする
* 獲得した **個々のメモリ領域** のことを「**インスタンス**」と呼ぶ
* 各クラスの **メモリ獲得＆初期化関数** も `new` にする、この関数を「**コンストラクタ**」と呼ぶ
* **コンストラクタ** は **インスタンス** を返す
* コンストラクタ以外の **クラスの関数** を「**メソッド**」と呼ぶ
* 各**メソッド**の **第一引数** を **インスタンス** にする

## C言語での関数実装例

```c
#include <stdio.h>
#include <stdlib.h>

typedef const char *String;

void *new(size_t size)
{
    void *memory = malloc(size);
    if (memory == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(8);
    }
    return memory;
}

/*
 * class Node {
 */
typedef struct node {
    int data;
    struct node *next;
} *Node;

Node Node_new(int data)
{
    Node node = new(sizeof(*node));
    node->data = data;
    node->next = NULL;
    return node;
}

void Node_output(Node node, String separator) {
    printf("%d%s", node->data, separator);
}

void Node_free(Node node)
{
    node->next = NULL;
    free(node);
}

/* } */

/*
 * class List {
 */
typedef struct list {
    Node head;
    Node tail;
} *List;

List List_new()
{
    List list = new(sizeof(*list));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

void List_add(List list, int data)
{
    Node node = Node_new(data);
    if (list->head == NULL) {
        list->head = node;
        list->tail = node;
    } else {
        list->tail->next = node;
        list->tail = node;
    }
}

void List_input(List list)
{
    int size;
    if (scanf("%d", &size) != 1) {
        fprintf(stderr, "Invalid size\n");
        exit(1);
    }
    for (int i = 0; i < size; i++) {
        int data;
        if (scanf("%d", &data) != 1) {
            fprintf(stderr, "Invalid data\n");
            exit(2);
        }
        List_add(list, data);
    }
}

void List_output(List list)
{
    for (Node node = list->head; node != NULL; node = node->next) {
        Node_output(node, " ");
    }
    printf("\n");
}

void List_free(List list)
{
    Node node = list->head;
    while (node != NULL) {
        Node next = node->next;
        Node_free(node);  // cannot access node members after here
        node = next;
    }
    list->head = NULL;
    list->tail = NULL;
    free(list);
}

/* } */

int main(void)
{
    List list = List_new();
    List_input(list);
    List_output(list);
    List_free(list);
}
```

## Pythonでの関数実装例

C言語とPythonの相違点を下表に示します。

|C言語|Python|
|---|---|
|変数宣言|不要<br>変数代入すると変数辞書に `{変数名: 値}` の形で変数登録される。|
|構造体定義|不要<br>インスタンスに自由に変数代入できる|
|型定義<br>`typedef`|クラス定義<br>整数の`123`は、自動的に`int`型の`123`インスタンスが作られる。|
|ポインタのメンバアクセス演算子<br>`->`|インスタンスのメンバアクセス演算子<br>`.`|
|NULL|None|
|処理ブロックは `{` と `}` で囲む| 処理ブロックはインデントを下げる |
|`printf`関数|`print`関数<br>ただし、自動的に改行される。<br>改行されないときは`end`引数で改行文字の代わりを指定。|
|`malloc`関数|`クラス名()`<br>class定義するとメモリ確保関数（コンストラクタ）が自動的に作られる<br>クラス名がメモリ確保関数名になる。|
|`free`関数|不要<br>使わなくなったメモリ領域は自動返却される。<br>`del`文で強制返却もできる。|
|`scanf`関数`|`input`関数<br>1行分の文字列を読み込む。<br>整数化は`int`関数。<br>空白分割は`split`メソッド。|

比較のため、空のメモリ領域（インスタンス）を確保する `new`クラス を定義してあります。

```py
class new:
    pass

#
# class Node {
#/
def Node_new(data):
    node = new()
    node.data = data
    node.next = None
    return node

def Node_output(node, separator):
    print(node.data, end=separator)

# }

#
# class List {
#/
def List_new():
    list = new()
    list.head = None
    list.tail = None
    return list

def List_add(list, data):
    node = Node_new(data)
    if list.head is None:
        list.head = node
        list.tail = node
    else:
        list.tail.next = node
        list.tail = node

def List_input(list):
    size = int(input())  # Pythonでは使用しない
    for data in input().split():
        List_add(list, int(data))

def List_output(list):
    node = list.head
    while node is not None:
        Node_output(node, " ")
        node = node.next
    print()

# }

def main():
    list = List_new()
    List_input(list)
    List_output(list)
    del list

if __name__ == '__main__':
    main()
```

## Pythonでのクラス実装例

Node と List をクラス定義することで、それぞれのクラスでメモリ確保されるようになるので、newクラスが不要になります。
初期化処理は、`__init__` メソッドに書きます。コンストラクタがメモリ確保したあと、自動的に呼び出してくれます。

クラス定義することで名前空間が作られ、クラス内に定義した関数は他のクラスの関数と名前が衝突しても異なる関数としてそれぞれ使用できるので、「**クラス名とアンダースコア**」を取り除きます。

`クラス名_メソッド名(インスタンス, その他引数)` と書いていたのを 
`インスタンス.メソッド(その他引数)` と書くと、
`クラス名.メソッド名(インスタンス, その他引数)` を呼び出してくれます。

メソッドの第一引数のインスタンス変数名は、`self` にするのが慣習になっています。

```py
class Node:

    def __init__(self, data):
        self.data = data
        self.next = None

    def output(self, separator):
        print(self.data, end=separator)


class List:

    def __init__(self):
        self.head = None
        self.tail = None

    def add(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def input(self):
        size = int(input())  # Pythonでは使用しない
        for data in input().split():
            self.add(int(data))

    def output(self):
        node = self.head
        while node is not None:
            node.output(" ")
            node = node.next
        print()


def main():
    list = List()
    list.input()
    list.output()
    del list

if __name__ == '__main__':
    main()
```

## Javaでのクラス実装例

基本的な文法はC言語と同じです。
クラスは構造体の拡張版だと思えばいいです。
構造体の中に関数定義を書けて、他のクラスと名前衝突を気にせずに自由にメンバ定義やメソッド定義できます。
メソッドの第一引数のインスタンス引数は記述不要で、暗黙の第一引数`this`が自動定義されてインスタンスが代入されます。
クラス名と同じメソッドがコンストラクタになります。インスタンスthisが暗黙定義されますので、復帰値型やreturnの記述は不要です。
scanfはScannerクラスで代用しています。

```java:LinkedList.java
import java.util.Scanner;

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }

    void output(String separator) {
        System.out.print(this.data + separator);
    }
}

class List {
    Node head;
    Node tail;

    List() {
        this.head = null;
        this.tail = null;
    }

    void add(int data) {
        Node node = new Node(data);
        if (this.head == null) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
    }

    void input() {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        for (int i = 0; i < size; i++) {
            int data = scanner.nextInt();
            add(data);
        }
    }

    void output() {
        for (Node node = this.head; node != null; node = node.next) {
            node.output(" ");
        }
        System.out.print("\n");
    }
}

public class LinkedList {
    public static void main(String[] args) {
        List list = new List();
        list.input();
        list.output();
    }
}
```