Javaで連結リストの実装

さて週末やることのノルマの一つ目です。今回は

「連結リスト」

の実装をやりました。参考書をガン見しながらやったのでいつもより綺麗なプログラムになりましたｗ

まず連結リストの基礎知識をおさらいしてみます

・リストを実現するデータには、この「連結リスト」と「配列」がある

・連結リストとは、リストに含まれる各要素をリンクによってつなぎあわせたもの

・セルの一つ一つに、前後のセルへのリンクを持たせるため、リンク１つ分のメモリが必要になるため、配列よりメモリをくう

・しかし、要素の挿入や削除が簡単に行える

実装した感想ですが、ポインタを思い出してしんどかったですｗ

コード自体は確かに簡潔な記述になっていると思います。じゃあ貼っていきます。

ー次の要素だけのリンクだけをもつ連結リスト / LinkedList.javaー

	
public class Cell{
    Cell next; //次のセルへのリンク
	Object data; //このセルのデータ
	int num; //このセルの順番
	
	Cell(Object data){
		next = null;
		this.data = data;
	}
}   

まずリストのひな形をつくります。これを操作してリストを表現していきます。

/*
 *今回は昇順にint型のデータを並べたリスト構造を実装
 **/
public class LinkedList{
	final Cell header;
	
	public LinkedList(){
		header = new Cell("List Head");
	}

	//リストへの挿入
	public void insert(int num){
		Cell p = header.next;
		Cell q = header;
		while(p != null && num > (Integer)p.data){
			q = p;
			p = p.next;
		}
		
		Cell newCell = new Cell(num);
		newCell.next = p;
		q.next = newCell;
	}
	
	//リストからの削除(dataがnumであるリストを削除する)
	public void delete(int num){
		Cell p = header.next;
		Cell q = header;
		
		if(q == null){
			throw new IllegalStateException("リストが空なので削除できません");
		}
		
		while(num != (Integer)p.data){
			q = p;
			p = p.next;
			if(p == null){
				throw new IllegalStateException("指定したデータは存在しません");
			}
		}
		q.next = p.next;
	}
	
	public String toString(){
		StringBuilder st = new StringBuilder();
		st.append("[ ");
		for(Cell p = header.next; p!=null; p=p.next){
			st.append(p.data + " ");
		}
		st.append("]");
		return st.toString();
	}
	
}

ポインタ操作みたいでしんどい。図を書きながら何とか理解。

public class Main {
	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		list.insert(2);
		list.insert(5);
		list.insert(4);
		
		System.out.println(list.toString());
		list.delete(4);
		System.out.println(list.toString());
		
		LinkedList list2 = new LinkedList();
		list2.insert(2);
		list2.insert(5);
		list2.insert(4);
		
		list2.delete(2);
		System.out.println(list2.toString());
		list.delete(10);
	}
}

 

実行結果はこんな感じ。まあ参考書をほとんど真似たので。。。

ー双方向のリンクをもつ双方向リスト / DLinkedLink.javaー

public class DCell {
	DCell prev; //前のセルへのリンク
	DCell next; //次のセルへのリンク
	Object data; //セルのデータ
	
	public DCell(Object data){
		this.data = data;
		prev = null;
		next = null;
	}
}

前の要素を参照するためのprevを用意します。

import java.util.NoSuchElementException;

public class DLinkedList {
	final DCell head;
	
	public DLinkedList(){
		head = new DCell("List head");
		head.prev = head.next = head;
	}
	
	//セルpの直後にdataを挿入
	private void insertAfter(DCell p,Object data){
		DCell x = new DCell(data);
		x.prev = p;
		x.next = p.next;
		p.next.prev = x;
		p.next = x;
	}
	
	//先頭にdataを挿入
	public void insertFirst(Object data){
		insertAfter(head,data);
	}
	
	public void insertLast(Object data){
		insertAfter(head.prev,data);
	}
	
	//指定したセルを削除する
	private void remove(DCell p){
		p.prev.next = p.next;
		p.next.prev = p.prev;
	}
	
	public Object removeFirst(){
		if(isEmpty()){
			throw new NoSuchElementException("リストが空です");
		}
		
		DCell cell = head.next;
		remove(cell);
		return cell.data;
	}
	
	public Object removeLast(){
		if(isEmpty()){
			throw new NoSuchElementException("リストが空です");
		}
		
		DCell cell = head.prev;
		remove(cell);
		return cell.data;
	}
	
	public boolean isEmpty(){
		return head.next == head;
	}
	
	public String toString(){
		StringBuilder st = new StringBuilder();
		st.append("[ ");
		for(DCell p=head.next; p != head; p = p.next){
			st.append(p.data + " ");
		}
		st.append("]");
		return st.toString();
	}
}   

双方向であると同時に循環させているので、コンストラクタでhead.prevもheadを指すようにしています。

public class Main {
	public static void main(String[] args) {
		DLinkedList list = new DLinkedList();		
		list.insertFirst("a");
		list.insertLast("b");
		list.insertLast("c");
		System.out.println(list.toString());
		
		list.removeFirst();
		System.out.println(list.toString());
		
		list.removeLast();
		System.out.println(list.toString());
		
		list.removeFirst();
		System.out.println(list.toString());
		list.removeFirst();
	}
}

 

実行結果はこのようになりました。ちゃんと出来てますね。

今後リスト構造をうまく使いこなせるようにしないとね。

既にArrayList様やHashMap様には度々お世話になっておりますけど。