Dev Diary.

public Iterator<T> iterator(){
	
	return new MyIterator();
}

private class MyIterator implements Iterator<T>{
	
	private Node<T> nextnode;
	
	public MyIterator() {
		nextnode = head;
	}
	
	public boolean hasNext() {
		return (nextnode != null);
	}
	public T next() {
		if(nextnode == null) {
			throw new NoSuchElementException();
		}
		
		T val = nextnode.data;
		nextnode = nextnode.next;
		return val;
	}
	public void remove() {
		
	}
}

기존 MySingleLinkedList 클래스에 이너클래스로 

MyIterator를 만들어주었다.

Node객체를 멤버로 가지고

생성자에서 head값을 넣어주고

다음 노드가 있는지 확인하는 메서드와

다임 노드의 데이터를 반환하는 메서드를 구현하였다.

연결리스트의 순회 : Iterator의 필요성

public 메서드들 만을 이용하여 연결리스트를 순회하려면?

Iterator

노드의 주소를 직접 사용자에게 제공하는 대신 그것을 private 멤버로

wrapping하고 있으면서 사용자가 필요로 하는 일을 해주는 public method를 

가진 Iterator 객체를 제공한다.

사용자가 연결리스트를 한방에 순차적으로 순회하기 위해서는

연결리스트의 전에 방문한 주소를 가지고있어야한다.

연결리스트의 노드의 주소를 직접 줄 수 없다 이유는

private 으로 지정되어있기때문이다.(Node)

그래서 그 주소를 private 멤버로 가지고 있으면서

그 주소가 가리키고 있는 노드의 데이터를 리턴해주고

자신은 한칸 앞으로 전진하는 Iterator 객체를 만들어

사용자에게 주므로 사용자는 Iterator를 이용하여 

순회 할 수 있다.

Iterator를 이용한 순회

MySingleLinkedList<String> aList = new MySingleLinkedList<String>();
aList.add("Some String");



Iterator<String>iter = aList.iterator();
	while(iter.hasNext()){
		String str = iter.next();
		//do something with str
}

java.util이 Iterator<E> 인터페이스를 정의한다.

MyLingkedList 클래스는 메서드 iterator() 제공

MySingleLinkedList<E> 클래스는 Iterator<E> 인터페이스를

 구현하는 하나의 클래스 inner 클래스로 가지며, iterator() 메서드는 

이 클래스의 객체를 생성하여 반환한다.

연결리스트에서의 Iterator

Iterator는 개념적으로는 연결리스트의 노드와 노드 사이를 가리킨다.

초기상태의 iterator는 첫 번째 노드의 앞 위치를 가리킨다.

next() 메서드는 한칸 전진하면서 방금 지나친 노드의 데이터를 반환

hasNext() 메서드는 다음 노드가 존재하면 true, 그렇지 않으면 false를 반환한다.

remove() 메서드는 가장 최근에 next() 메서드로 반환한 노드를 삭제한다.

객체지향 프로그래밍

Information Hiding

Data Encapsulation

Abstract Data Type 

본질적으로 비슷한 내용이다.

인터페이스와 구현의 분리가 가장 중요한 원칙이다.

연결리스트는 리스트 라는 추상적인 데이터 타입을 구현하는 

한가지 방법일 뿐이다. 

사용자는 리스트에 데이터를 삽입, 삭제, 검색할 수 있으면 된다.

그것의 구현에 대해서 세부적으로 알 필요는 없다.

인터페이스와 구현을 분리하면 코드의 모듈성이 증가하며,

코드의 유지/보수, 코드의 재사용이 용이해진다.

사용자는 Interface만 알면 되고

Implementation에 대해서는 알 필요도 없고

알 수도 없게 해야한다.

package section7;

import section6.Node;

public class MySingleLinkedList<T> {
	
	public Node<T> head;
	public int size = 0;
	
	public MySingleLinkedList() {
		head = null;
		size = 0;
	}
	

private static class Node<T> {
	
	public T data;
	public Node<T> next;
	
	public Node(T data){
		this.data = data;
		next = null;
	}
	
}
	
	private void addFirst(T item) {
		Node<T> newNode = new Node<T>(item);
		newNode.next = head;
		head = newNode;
		size++;
	}
	
	private void addAfter(Node<T> before, T item) {
		Node<T> temp = new Node<T>(item);
		temp.next = before.next;
		before.next = temp;
		size++;
	}
	
	
	private T removeFirst() { //delete
		if(head==null) {
			return null;
		}
		else {
			T temp = head.data;
			head = head.next;
			size--;
			return temp;
		}
	}
	
	private T removeAfter(Node<T> before) {
		if(before.next==null) {
			return null;
		}
		else {
			T temp = before.next.data;
			before.next = before.next.next;
			return temp;
		}
		
	}
	
	public int indexOf(T item) { //search
		Node<T> p = head;
		int index = 0;
		while(p != null) {
			if(p.data.equals(item)) {
				return index;
			}
			else {
				p = p.next;
				index++;
			}
		}
		return -1;
	}
	
	private Node<T> getNode(int index){
		if(index<0 || index>=size) {
			return null;
		}
		else {
			Node<T> p = head;
			for(int i=0; i<index; i++) {
				p =p.next;
			}
			return p;
		}
		
	}
	
	public T get(int index) {
		if(index<0 || index>=size) {
			return null;
		}
			return getNode(index).data;		
	}
	
	public void add(int index, T item) {
		if(index <0||index >size) {
			return;
		}
		if(index==0) {
			addFirst(item);
		}
		else {
		Node<T> q = getNode(index-1);
		addAfter(q, item);
		}
	}
	
	public T remove(int index) {
		if(index < 0 || index >= size) {
			return null;
		}
		if(index ==0) {
			return removeFirst();
		}
		Node<T> prev = getNode(index-1);
		return removeAfter(prev);
	}
	
	public T remove(T item) {
		Node<T> p = head;
		Node<T> q = null;
		while(p != null && !p.data.equals(item)) {
			q = p;
			p=p.next;
		}
		if(p==null)
			return null;
		if(q==null)
			return removeFirst();
		else
			return removeAfter(q);	
	}
	
	public int size() {
		return size;
	}
	
	public static void main(String[] args) {
		
	}

}

기존에 만들었던 연결리스트 클래스이다.

인터페이스와 구현의 분리를 위해 

이너 클래스로 Node 클래스를 내부에 생성하고

Node 클래스를 이용하는 메서드들을 private로

변경해주는 작업을 하였다.

인터페이스를 생성하여

T get(int index)

void add(int index, T item)

T remove(int index)

boolean remove(T item)

int indexOf(T item)

int size()

메서드를 정의할 것이다.

이번에는  T 타입 데이터와 같은 노드노드를

삭제하는 기능을 하는 메서드를 구현해보았다.

하지만 그 노드를 찾았다고 하더라도

그 전 노드의 주소를 알 수 없기때문에 

문제가 있었다.

삭제할 노드가 아니라 직전 노드의 주소가 필요하다.

	public T remove(T item) {
		Node<T> p = head;
		Node<T> q = null;
		while(p != null && !p.data.equals(item)) {
			q = p;
			p=p.next;
		}
		if(p==null)
			return null;
		if(q==null)
			return removeFirst();
		else
			return removeAfter(q);	
	}

그 문제를 해결한 코드이다.

항상 그 전 노드를 가리키는 참조변수를 만들어서

처리하는 코드이다.

만일  p가 null이라면 찾는 값이 존재하지 않기때문에

null을 리턴하고

첫번째 노드부터 값을 찾은 경우라면?

q가 null이다.

그때는 removeFirst로 삭제를 한다.

그렇지않다면 removeAfter로 삭제를 한다.

연결리스트의 노드들을 처음부터 순서대로 방문하는 것을 순회한다고 말한다.

indexOf 메서드는 입력된 데이터 item과 동일한 데이터를 저장한 노드를 

찾아서 그 노드번호를 반환한다. 그것을 위해서 연결리스트를 순회한다.

getNode는 입력으로 index를 받아서 

index번째 노드의 주소를 리턴하는 함수이다.

추가로 

이전에 만들었던 추가,삭제하는 메서드들을

하나로 통합하였다.

package section6;

public class MySingleLinkedList<T> {
	
	public Node<T> head;
	public int size = 0;
	
	public MySingleLinkedList() {
		head = null;
		size = 0;
	}
	
	public void addFirst(T item) {
		Node<T> newNode = new Node<T>(item);
		newNode.next = head;
		head = newNode;
		size++;
	}
	
	public void addAfter(Node<T> before, T item) {
		Node<T> temp = new Node<T>(item);
		temp.next = before.next;
		before.next = temp;
		size++;
	}
	
	
	public T removeFirst() { //delete
		if(head==null) {
			return null;
		}
		else {
			T temp = head.data;
			head = head.next;
			size--;
			return temp;
		}
	}
	
	public T removeAfter(Node<T> before) {
		if(before.next==null) {
			return null;
		}
		else {
			T temp = before.next.data;
			before.next = before.next.next;
			return temp;
		}
		
	}
	
	public int indexOf(T item) { //search
		Node<T> p = head;
		int index = 0;
		while(p != null) {
			if(p.data.equals(item)) {
				return index;
			}
			else {
				p = p.next;
				index++;
			}
		}
		return -1;
	}
	
	public Node<T> getNode(int index){
		if(index<0 || index>=size) {
			return null;
		}
		else {
			Node<T> p = head;
			for(int i=0; i<index; i++) {
				p =p.next;
			}
			return p;
		}
		
	}
	
	public T get(int index) {
		if(index<0 || index>=size) {
			return null;
		}
			return getNode(index).data;		
	}
	
	public void add(int index, T item) {
		if(index <0||index >size) {
			return;
		}
		if(index==0) {
			addFirst(item);
		}
		else {
		Node<T> q = getNode(index-1);
		addAfter(q, item);
		}
	}
	
	public T remove(int index) {
		if(index < 0 || index >= size) {
			return null;
		}
		if(index ==0) {
			return removeFirst();
		}
		Node<T> prev = getNode(index-1);
		return removeAfter(prev);
	}
	
	public static void main(String[] args) {
		
	}

}

특정 노드의 뒤에 넣는 기능과

특정 노드의 앞에 넣는 기능을 구현해보았다.

특정 노드의 뒤에 넣는 기능은  특정 노드가 

가리키는 주소를 새로운 노드의 참조변수에 넣고

특정노드의 참조변수에 새로운 노드의 주소를 넣어주면

된다.

하지만 특정 노드의 앞에 넣는 기능은 그리 간단한 것이

아니다. 왜냐하면 각 노드들은 다음 주소를 가리키는 참조변수만

존재하고 이전 노드의 주소는 가지고 있지 않기에

굳이 기능을 구현하려면 첫번째 노드부터 시작해서 특정 노드 전까지의 

노드를 찾는 방법이 있을 수 있다. 

또한 

특정 노드의 첫번째 노드를 삭제하는 기능과

특정 노드를 삭제하는 기능을 구현해보았다.

특정 노드의 첫번째 노드를 삭제하는 기능은

헤드가 널값이 아닐때 헤드에 저장된 값을

특정 노드의 다음노드를 가리키게 하면된다.

특정노드를 삭제하는 기능은 

특정 노드의 이전 노드가 필요하다.

실제로는 그 앞노드의 참조변수를 건드려야하기 때문이다.

이전노드의 참조변수에 다음다음노드를 가리키게하면 된다.

그 이전에 그다음 노드가 존재해야만 가능하다.

package section6;

public class MySingleLinkedList<T> {
	
	public Node<T> head;
	public int size = 0;
	
	public MySingleLinkedList() {
		head = null;
		size = 0;
	}
	
	public void addFirst(T item) {
		Node<T> newNode = new Node<T>(item);
		newNode.next = head;
		head = newNode;
		size++;
	}
	
	public void addAfter(Node<T> before, T item) {
		Node<T> temp = new Node<T>(item);
		temp.next = before.next;
		before.next = temp;
		size++;
	}
	
	
	public T removeFirst() { //delete
		if(head==null) {
			return null;
		}
		else {
			T temp = head.data;
			head = head.next;
			size--;
			return temp;
		}
	}
	
	public T removeAfter(Node<T> before) {
		if(before.next==null) {
			return null;
		}
		else {
			T temp = before.next.data;
			before.next = before.next.next;
			return temp;
		}
		
	}
	
	public T get(int index) {  //get
		return null;
	}
	
	public int indexOf(T item) { //search
		return -1;
	}
	
	public static void main(String[] args) {
		
	}

}

노드

각각의 노드는 데이터 필드와 하나 혹은 그 이상의

링크 필드로 구성

링크 필드는 다음노드를 참조

첫번째 노드의 주소는 따로 저장해야함

package section6;

public class Node<T> {
	
	public T data;
	public Node<T> next;
	
	public Node(T data){
		this.data = data;
		next = null;
	}
	
}

노드 클래스

T 타입의 데이터변수,

다음 노드의 주소값을 가지는 변수 

를 가진다.

package section6;

public class MySingleLinkedList<T> {
	
	public Node<T> head;
	public int size = 0;
	
	public MySingleLinkedList() {
		head = null;
		size = 0;
	}
	
	public void addFirst(T item) {
		Node<T> newNode = new Node<T>(item);
		newNode.next = head;
		head = newNode;
		size++;
	}
	
	public void add(int index, T item) { //insert
		
	}
	
	public void remove(int index) { //delete
		
	}
	
	public T get(int index) {  //get
		return null;
	}
	
	public int indexOf(T item) { //search
		return -1;
	}
	
	public static void main(String[] args) {
		
	}

}

연결리스트 클래스 

아직 전부 구현하지는 않았지만 

첫번째 노드를 가리키는 주소변수,

총 사이즈를 체크하는 변수와

노드들이 있을때 첫번째 노드에 새로운 노드를 추가하는

함수를 구현해보았다.

하지만 이 함수에는 큰 문제가 있다.

기존의 연결리스트의 크기가 0인경우, head가 null인

경우에도 문제가 없는지 확인해야한다.

리스트

기본적인 연산 : 삽입, 삭제, 검색 등

리스트를 구현하는 대표적인 두 가지 방법 : 배열, 연결리스트

배열의 단점

크기가 고정 - reallocation이 필요

리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 함

연결 리스트

다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하며,

길이의 제한이 없음

하지만 랜덤 액세스가 불가능

랜덤 액세스란 배열의 경우에는 배열의 10번째 데이터를 읽어야한다면

a[10] 하면 되지만 어떤 칸에 읽는데 걸리는 시간이 거의 동일하다.

연결리스트는 10번째 데이터를 읽고 싶다면 

첫번재 데이터부터 순서대로 가야만 한다.

어떤 데이터와 나의 다음데이터의 주소의 데이터 쌍을

노드라고 부른다.

첫번째 노드의 주소는 절대 잃어버려서는 안된다.

이전에 만들었던 스케줄러 프로그램을 

ArrayList를 사용하도록 수정해보았다. 

package chapter4;

import java.util.ArrayList;
import java.util.Scanner;

public class Scheduller {
	
	public ArrayList<Event> events = new ArrayList<>();
	private Scanner kb;
	
	public void processCommand() {
		
		kb = new Scanner(System.in);
		while(true) {
			System.out.print("$ ");
			String command = kb.next();
			if(command.equals("addevent")) {
				String type = kb.next();
				if(type.equalsIgnoreCase("oneday"))
					handleAddOneDayEvent();
				else if(type.equalsIgnoreCase("duration"))
					handleAddDurationEvent();
				else if(type.equalsIgnoreCase("deadline"))
					handleAddDeadlineEvent();
			}
			else if(command.equals("list")) {
				handleList();
				
			}
			else if(command.equals("show")) {
				handleshow();
			}
			else if(command.equals("exit")) {
				break;
			}
				
		}
		kb.close();
	}

	private void handleshow() {
		String dateString = kb.next();
		MyDate theDate = parseDateString(dateString);
		for (int i=0; i<events.size();i++) {
			if(events.get(i).isRelevent(theDate))
				System.out.println(events.get(i).toString());
		}
	}

	private void handleList() {
		for(Event ev : events)
			System.out.println("   "+events.get(i).toString());
		}
		
	}

	private void handleAddDeadlineEvent() {
	
	}

	private void handleAddDurationEvent() {
		// TODO Auto-generated method stub
		
	}

	private void handleAddOneDayEvent() {
		System.out.print("  when: ");
		String dateString = kb.next();
		System.out.print("  title: ");
		String title = kb.next();
		
		
		MyDate date = parseDateString(dateString);
		OnedayEvent ev = new OnedayEvent(title,date);
		System.out.println(ev.toString());
		addEvent(ev);
	}

	private void addEvent(Event ev) {
		events.add(ev);
	}

	private MyDate parseDateString(String dateString) {
		String[] tokens = dateString.split("/");
		
		int year = Integer.parseInt(tokens[0]);
		int month = Integer.parseInt(tokens[1]);
		int day = Integer.parseInt(tokens[2]);
		
		MyDate d = new MyDate(year,month,day);
		return d;
	}

	public static void main(String[] args) {
		
		Scheduller app = new Scheduller();
		app.processCommand();
		
	}

}

Generic한 리스트 클래스를 만들어보자.

리스트

여러 개의 데이터를 저장하고

임의의 위치에 새로운 데이터를 추가하거나

데이터의 삭제가 가능하고

임의의 위치의 데이터를 읽을 수 있고,

용량에 제한이 없는 

...

클래스 

사용 예

예를 들어 String들을 저장하려면

MyArrayList<String> myList = new MyArrayList<String>();

생성된 리스트에 String 추가

myList.add("Bashful");

myList.add("Awful");

myList.add("Jumpy");

추가한 순서대로 저장된다. 

myList.add(2, "Doc");

2번위치에 (배열의3번째칸) 에 추가하라 기존에있던 데이터를 한칸 씩 뒤로 밈

myList.remove(1);

1번위치 값을 삭제하고 빈 공간을 앞으로 땡겨온다.

myList.set(2,"Sneezy");

2번위치를 덮어쓰는 기능.

String dwarf = myList.get(2)

인덱스를 매개변수로 값을 리턴하는기능

int index = myList.indexOf("Sneezy");

인덱스 값을 리턴해준다.

없다면 -1 리턴

package section5;

import java.util.Arrays;

public class MyArrayList<T> {

	private static final int INIT_CAPACITY = 10;
	private T[] theData;
	private int size;
	private int capacity = INIT_CAPACITY;
	
	public MyArrayList() {
		theData = (T []) new Object [INIT_CAPACITY];
		size = 0;
	}
	
	public void add(int index, T anEntry) {
		if(index < 0 || index > size) {
			throw new ArrayIndexOutOfBoundsException(index);
			}
		if(size >= capacity){
			reallocate();
			}
		for(int i=size-1; i>=index; i--) {
			theData[i+1] = theData[i];
		}
		theData[index] =anEntry;
		size++;
	}
	
	private void reallocate() {
		capacity *= 2;
		theData = Arrays.copyOf(theData, capacity);
	}

	public void add(T anEntry) {
		add(size, anEntry);
	}
	public int size() {
		return size;
	}
	
	public int indexOf(T anEntry) {
		for(int i =0; i<size; i++) {
			if(theData[i].equals(anEntry)) {
				return i;
			}
		}
		return -1;
	}
	public T get(int index) {
		if(index <0 || index >= size) {
			throw new ArrayIndexOutOfBoundsException(index);
		}
		return theData[index];
	}
	
	public T set(int index, T newValue) {
		if(index <0 || index >= size) {
			throw new ArrayIndexOutOfBoundsException(index);
		}
		T oldValue = theData[index];
		theData[index] = newValue;
		return oldValue;
	}
	
	public T remove(int index) {
		if(index < 0|| index >= size) {
			throw new ArrayIndexOutOfBoundsException(index);
		}
		T returnValue = theData[index];
		for(int i = index+1; i<size; i++) {
			theData[i-1]=theData[i];
		}
		size--;
		return returnValue;
	}
	
	
	
}