[211110] 교육 10일차

Linked List

class Node {
	int name = 0;
	Node next = null;
}
//
public class Test074 {
	public static void main( String[] args ) {
		Node head = new Node();
		Node tail = head;
//		
		Node tmp = new Node();
		tmp.name = 10;
		tmp.next = null;
//		
		tail.next = tmp;
		tail = tmp;
//		
		tmp = new Node();
		tmp.name = 20;
		tmp.next = null;
//
		tail.next = tmp;
		tail = tmp;
//		
		for( Node t = head.next ; t != null ; t = t.next ) {
			System.out.println( t.name );			
		}	
		// 가베지 콜렉션에 의해 삭제됨
		Node post = head;
		Node pre = head.next;
		while( pre != null ) {
			post.next = null;	
			post = pre;
			pre = pre.next;
		}
		post = null;
		tail = head;
	}
}

class Node {
	int name = 0;
	Node next = null;
	Node( int i, Node j ) {
		this.name = i;
		next = j;	//	this. 이 생략될 수 있다. 경우에 따라 ( 없으면 컴파일러가 알아서 붙여준다 )
	}
}
//
class XList 
{
	Node head = null;
	Node tail = null;
	XList() {
		head = new Node( 0, null );
		tail = head;
	}
	//	
	void add( int i ) {
		tail.next = new Node( i, null );
		tail = tail.next;
	}
	//
	void printAll() {
		for( Node t = head.next ; t != null ; t = t.next ) {
			System.out.println( t.name );
		}
	}
	//
	void deleteAll() {
		Node post = head;
		Node pre = head.next;
		while( pre != null ) {
			post.next = null;
			post = pre;
			pre = pre.next;
		}
		post = null;
		tail = head;
	}
}
//
public class Test079 {
	public static void main( String[] args ) {
		XList l = new XList();
		l.add( 10 );
		l.add( 20 );
		l.deleteAll();
		l.printAll();
	}
}

위의 그림은 add 에 대한 그림이고 아래의 그림은 delete에 대한 그림이다. ( 포인터의 이동을 잘 보자 )
this : 호출된 함수가 속해있는 인스턴스를 가리킨다.

---

Queue

class XList {
	Node head = null;
	Node tail = null;
// 위의 코드와 동일...
	int removeLikeQueue() {
		// 비어있을때는 동작하면 안된다.
		if( head.next == null ) {
			return -1;
		}
		Node post = head;
		Node pre = head.next;
		post.next = pre.next;
		pre.next = null;
		// 포인터의 == 는 같은 대상을 가리키면 true
		// tail == pre 가 되는 시점은 딱 하나 남았을때만 성립. 이때는 지우고 난 다음 tail 은 원점으로
		if( tail == pre ) {
			tail = head;
		}
		return pre.name;
	}
}

큐 : 먼저 들어간 것을 먼저 빼낸다. ( 선입선출 )

---

Stack

int removeLikeStack() {
	if( head.next == null ) {
		return -1;
	}
	Node post = head;
	Node pre = head.next;
	//	
	while( pre != tail ) {
		post = pre;
		pre = pre.next;
	}
	//	
	post.next = null;
	tail = post;
	return pre.name;
}

스택 : 나중에 들어간 것 부터 먼저 꺼낸다. ( 후입선출 )