Copyright (c) 2015-, All Rights Reserved by Kwanghoon Choi
(아래 자바 프로그래밍 강의 교재의 내용을 자유롭게 이용하되 다른 웹 사이트 등을 통한 배포를 금합니다.)

5. 다른 형태의 리스트/트리 클래스

앞에서 우리는 리스트 클래스 List를 서브 클래스 NullList와 Pair에서 필요한 모든 메소드들을 가지고 있도록 정의했다. 즉, isNull, isPair, first, second, toString 메소드를 모두 List 클래스에서 선언하고 서브 클래스에서 적절히 재정의(오버라이딩)했다.

List 클래스를 정의하는 다른 방법으로, 두 서브 클래스가 공통으로 가지고 있는 메소드들만 List 클래스에 포함되도록 정의할 수 있다.

// 다른 버전의 List 클래스
abstract class List {
        public abstract boolean isNull();
        public abstract String toString();
}

class NullList extends List {
        // List 클래스의 공통 메소드
        public boolean isNull() {
                return true;
        }

        public String toString() {
                return "()";
        }
}

class Pair extends List {
        private int firstElem;
        private List secondElem;

        public Pair(int firstElem, List secondElem) {
                this.firstElem = firstElem;
                this.secondElem = secondElem;
        }

        public int first() {
                return this.firstElem;
        }

        public List second() {
                return this.secondElem;
        }

        // List 클래스의 공통 메소드
        public boolean isNull() {
        return false;
        }

        public String toString() {
                return "(" + firstElem + ", " + secondElem.toString() + ")";
        }
}

위의 List 클래스를 사용해서 다음과 같이 리스트 객체를 만들 수 있다. 아래의 예제는 이전 방식과 동일하다.

        List l1 = new NullList();    // 널 리스트
        List l2 = new Pair (3, l1);  // [ 3 ]
        List l3 = new Pair (2, l2);  // [ 2, 3 ]
        List l4 = new Pair (1, l3);  // [ 1, 2, 3 ]

        List l5 = new Pair (1,       // [ 1, 2, 3 ]
                    new Pair (2, 
                      new Pair (3, new NullList() ) ) );

List 객체를 다루는 연산들을 정의하자. 앞의 방식과 다른 형태의 코딩이 필요하다.

// print
        public static void print(List l) {
                System.out.print("[");
	
                while (true) {
                        if ( l.isNull() ) {
                                System.out.println("]");
                                break;
                        }
                        else {
                                Pair p = (Pair)l;   // 캐스팅 필요
                                System.out.print(
                                        p.first() 
                                        + (p.second().isNull() ? "" : ","));
                                l = p.second();     // cf.  l = l.second(); 
                        }
                }
        }
	
	
// length
        public static int length(List l) {
                int count;
		
                count = 0;
                while ( l.isNull() == false ) {   // cf.  l.isPair()
                        Pair p = (Pair)l;         // 새로 추가
                        count = count + 1;
                        l = p.second();           // cf.  l = l.second();
                }
			
                return count;
        }
	
// sum
        public static int sum(List l) {
                int sum;
		
                sum = 0;
                while ( l.isNull() == false ) {  // cf.  l.isPair()
                        Pair p = (Pair)l;        // 새로 추가
                        sum = sum + p.first();   // cf. sum = sum + l.first();
                        l = p.second();          // cf. l = l.second();
                }
		
                return sum;
        }
	
// concat
        public static List concat(List l1, List l2) {
                if ( l1.isNull() )
                        return l2;
                else {
                        Pair p1 = (Pair)l1;     // 새로 추가
                        return new Pair (p1.first(), concat(p1.second(), l2));
                                                // cf. l1.first() => p1.first()
                                                // cf. l1.second() => p1.second()
                }
        }
	
// reverse
        public static List reverse(List l) {
                if ( l.isNull() )
                        return l;
                else {
                        Pair p = (Pair)l;      // 새로 추가
                        return concat (
                                reverse (p.second()),   // cf. l.second()
                                new Pair( p.first(), new NullList()));   // cf. l.first()
                }
        }

이전 방식의 List 클래스를 사용한 print, length, sum, concat, reverse 메소드와 위의 새로운 방식의 List 클래스를 사용한 메소드들의 코드를 비교하면 서로 장단점이 있다.

이전 방식의 장점은 캐스팅 (Pair)를 사용할 필요가 없어서 코드가 더 짧다. 이전 방식의 단점은 리스트 변수 l이 사실 NullList 객체를 가리킬 때 l.first() 메소드를 호출하는 것을 허용하는 점이다.  두번째 방식은 이러한 잘못된 메소드 호출을 원천적으로 막을 수 있다는 장점이 있다. 반면 캐스팅을 통한 타입 변환이 반드시 필요하다.

마지막으로 List 클래스의 isNull이나 isPair와 같은 메소드는 Java의 instanceof 연산자를 사용한 코드로 대체가능하다. List l을 가정하고 l.isNull()은 l instanceof Null로 대체하거나, 또는 l instanceof Pair == false를 사용할 수도 있다.

abstract class List {
    public abstract String toString();

    public int length() {
       List l = this;
       int count = 0;
       while ( (l instanceof NullList) == false ) { // Pair 클래스 객체이면
           count = count + 1;
           Pair p = (Pair)l;  // 형변환 반드시 필요
           l = p.second();
       }
       return count;
   }
}

참고로, 위의 length 메소드를 List 클래스의 멤버 함수로 (객체지향적으로) 정의한 점도 앞의 length 메소드 예제 코드와의 차이점이다.

[연습문제] Tree 클래스, NullTree 클래스, BinTree 클래스를 위의 방식과 유사하게 다시 작성하시오.  즉, NullTree 클래스와 BinTree 클래스에서 공통으로 필요한 메소드만 Tree 클래스에서 선언한다. NullTree 클래스와 BinTree 클래스에서 이 메소드들을 재정의한다.

[연습문제] 앞의  연습문제에서 작성한 Tree, NullTree, BinTree 클래스들을 활용하여 트리 객체를 만드는 예제 코드를 작성하시오. 이전 방식과 차이점이 있는지 살펴보시오.

[연습문제] 앞의 연습문제에서 작성한 Tree, NullTree, BinTree 클래스들을 활용하여 트리를 다루는 연산(메소드) 들을 다시 작성하시오. 이전 방식과 차이점을 논의하시오.

- count, height, sum, preorder, inorder, postorder 메소드 작성