お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

さまざまなデータ構造(3)連結リスト2

データ構造

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

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

Javaのプログラム

Javaでプログラムを書いています。インスタンス変数として、先頭の要素を指し示すための矢印にあたるheadを用意しました。一つひとつのメソッドは前回の「連結リスト1」と同じ操作を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);
	}

}

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

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai