Javaで実装する

Javaでリスト構造を実装するには，リストを表すクラスとノードを表すクラスを定義し，リストに対する操作をリストのクラスのメソッドとすればよい．

ListNodeクラス

今回の演習ではリストの要素は文字列であると仮定してよい． ListNodeクラスは要素を記憶する変数と次のノードを示すための変数によって構成されることになる．

ListNode.java

class ListNode {
    String word;
    ListNode next;      // 自分自身であるListNodeを定義に含んでいる

    ListNode(String newWord) {
        word = newWord;
        next = null;
    }
}

ここでは次のノードを示すための変数として自分自身であるListNode型の変数を用意している．リストの終端はnullで表すことができる．
このように，あるデータの定義に自分自身のデータが含まれているようなデータ構造を再帰的なデータ構造という．つまりこのノードを表すクラスは再帰的データ構造である．

Listクラス

Listクラスはリストを表すクラスになる．リストは先頭のノードが参照できれば，それに続くノードもすべて参照できる．すなわち，先頭のノードさえ記憶できればよいことになる．

List.java

class List {
    ListNode top;

    List() {
        top = null;
    }
}