[자료구조] LinkedCollection 클래스

AbstractCollection 클래스 

import java.util.Collection;
import java.util.Iterator;

public abstract class AbstractCollection implements Collection {

	protected AbstractCollection() {
	}

	@Override
	public boolean add(Object object) {
		// TODO Auto-generated method stub
		throw new UnsupportedOperationException();
	}



	@Override
	public void clear() {
		// TODO Auto-generated method stub
		for (Iterator it = iterator(); it.hasNext();) {
			it.next();
			it.remove();
		}

	}

	@Override
	public boolean contains(Object object) {
		// TODO Auto-generated method stub
		Iterator it = iterator();
		if (object == null)
			while (it.hasNext()) {
				if (it.next() == null)
					return true;
			}
		else
			while (it.hasNext())
				if (object.equals(it.next()))
					return true;
		return false;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return (size() == 0);
	}

	@Override
	public abstract Iterator iterator();

	@Override
	public boolean remove(Object object) {
		// TODO Auto-generated method stub
		Iterator it = iterator();
		if (object == null)
			while (it.hasNext()) {
				if (it.next() == null) {
					it.remove();
					return true;
				}
			}
		else
			while (it.hasNext())
				if (object.equals(it.next())) {
					it.remove();
					return true;
				}
		return false;
	}

	public abstract int size();

	public String toString() {
		if (isEmpty())
			return "[]";
		Iterator it = iterator();
		StringBuffer buf = new StringBuffer("[" + it.next());
		while (it.hasNext())
			buf.append("," + it.next());
		return (buf + "]");
	}

}

LinkedCollection 클래스

import java.util.Iterator;

public abstract class LinkedCollection extends AbstractCollection {
	private static class Node {
		Object object;
		Node prev, next;

		Node() {
			prev = next = this;
		}

		Node(Object o, Node p, Node n) {
			object = o;
			prev = p;
			next = n;
		}
	}

	private int size;
	private Node head = new Node(); // dummy head node

	public boolean add(Object object) {
		head.prev = head.prev.next = new Node(object, head.prev, head);
		++size;
		return true; // no object is rejected
	} // 이해하기 힘들었다 ㅋㅋㅋㅋ

	public Iterator iterator() {
		return new Iterator() { // anonymous inner class
			private Node cursor = head.next; // current element node
			private boolean okToRemove = false;

			public boolean hasNext() {
				return cursor != head;
			}

			public Object next() {
				if (cursor == head)
					throw new RuntimeException();
				okToRemove = true;
				Object object = cursor.object;
				cursor = cursor.next;
				return object;
			}

			public void remove() {
				if (!okToRemove)
					throw new IllegalStateException();
				cursor.prev = cursor.prev.prev;
				cursor.prev.next = cursor;
				--size;
				okToRemove = false; // must call next() again before remove();
			}
		};
	}

	public int size() {
		return size;
	}

}

LinkedCollection 클래스의 add메소드를 이해하는데 꽤나 애를 먹었다 ㅋㅋㅋ 뭔가 계속 머릿속에서 재귀를 도는 느낌이랄까? 

new Node(object, head.prev, head)

이 부분에서 head.prev을 Node의 prev으로 가지고, head를 Node의 next로 갖는 node를 생성했다고 이해하자. 그리고 그러한 Node를 head.prev.next로 잡는다. 그리고 다시 이 노드를 head의 prev로 이어주면 된다. 글 다시 쓰면서 또 다시 이해하게 되었다. 처음 배울때는 다소 헷갈릴 수 있는 부분인것 같다.