さまざまなデータ構造（３）連結リスト２

2019-02-09データ構造

こんにちは。前回に引き続き、今回も連結リストです。今回はいよいよプログラムです。

ちなみに、前の２回が関連するので「片方向リスト用のノード」、「連結リスト１」をご覧ください。

Javaのプログラム

Javaでプログラムを書いています。インスタンス変数として、先頭の要素を指し示すための矢印にあたるheadを用意しました。一つひとつのメソッドは前回の「連結リスト１」と同じ操作をJavaで書いているだけなので、考え方を知りたい場合には前回の投稿をご覧ください。

package data_structure;

public class MyLinkedList<E> {

    private MyNode<E> head;

    MyLinkedList() {
        head = null;
    }

    public int size() {
        int size = 0;
        MyNode<E> tmp = head;

        while (tmp != null) {
            tmp = tmp.getNext();
            size++;
        }
        return size;
    }

    public void add(int index, E element) {
        MyNode<E> n = new MyNode<E>();
        n.setElement(element);

        if (index == 0) {
            n.setNext(head);
            head = n;
            return;
        }

        MyNode<E> tmp = getNthNode(index - 1);
        n.setNext(tmp.getNext());
        tmp.setNext(n);
    }

    public void add(E element) {
        add(size(), element);
    }

    public void set(int index, E element) {
        getNthNode(index).setElement(element);
    }

    public E get(int index) {
        return getNthNode(index).getElement();
    }

    public void remove(int index) {
        if (index == 0) {
            head = head.getNext();
            return;
        }
        MyNode<E> tmp = getNthNode(index - 1);
        tmp.setNext(tmp.getNext().getNext());
    }

    public String toString() {
        String result = "";
        for (MyNode<E> n = head; n != null; n = n.getNext()) {
            result += n.toString();
        }
        return result;
    }

    private MyNode<E> getNthNode(int index) {
        MyNode<E> result = head;
        for (int count = 0; count < index; count++) {
            result = result.getNext();
        }
        return result;
    }
}

動作確認をするプログラム

上のプログラムで作ったMyLinkedListクラスが正しく動作するかを確かめるプログラムです。ひととおり確かめています。

package data_structure;

public class MyLinkedListExec {

    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<String>();

        list.add("青森県");
        System.out.println(list);

        list.add("みやぎ県");
        System.out.println(list);

        list.add(0, "北海道");
        System.out.println(list);

        list.add(2, "岩手県");
        System.out.println(list);

        list.add("秋田県");
        System.out.println(list);

        list.set(3, "宮城県");
        System.out.println(list);

        System.out.println(list.get(1));

        list.remove(1);
        System.out.println(list);

        list.remove(0);
        System.out.println(list);
    }

}

次回からは、ここで作った連結リストを使って別のデータ構造を作っていきます。今回はこれでおしまい。それではまた。