Lecture/자료구조/2011/프로그램 4.4

ListNode.java

public class ListNode {
    String  data;
    ListNode  link;
 
    public ListNode() {
        data = link = null;
    }
 
    public ListNode(String val) {
        data = val;
        link = null;
    }
 
    public ListNode(String val, ListNode p) {
        data = val;
        link = p;
    }
}

LinkedList.java

public class LinkedList{
    private ListNode  head;
 
    /**
     * 리스트의 맨 앞에 원소 x를 삽입
     */
    public void addFirstNode(String x) {
        ListNode newNode = new ListNode();
        newNode.data = x;
        newNode.link = head;
        head = newNode;
    }
 
    /**
     * 리스트에서 p가 가리키는 노드 다음에 원소 x를 삽입
     * 알고리즘 4.1의 Java 구현
     */
    public void insertNode(ListNode p, String x) {
        ListNode newNode = new ListNode();
        newNode.data = x;
 
        if (head == null) {      // 공백 리스트인 경우
            head = newNode;
            newNode.link = null;
        } else if (p == null) {  // p가 null이면 리스트의 첫 번째 노드로 삽입
            newNode.link = head;
            head = newNode;
        } else {                 // p가 가리키는 노드의 다음 노드로 삽입
            newNode.link = p.link;
            p.link = newNode;
        }
    }
 
    /**
     * list의 끝에 원소 x를 삽입
     * 알고리즘 4.2의 Java 구현
     */
    public void addLastNode(String x) {                      		
        ListNode newNode = new ListNode(); // 새로운 노드 생성
        newNode.data = x;
        newNode.link = null;
 
        if (head == null) {
            head = newNode;
            return;
        }
 
        ListNode p = head;         // p는 임시 순회 레퍼런스 변수
        while (p.link != null) {   // 마지막 노드를 탐색
            p = p.link;
        }
        p.link = newNode;          // 마지막 노드로 첨가
    }
 
    /**
     * p가 가리키는 노드의 다음 노드를 삭제
     * 알고리즘 4.3의 Java 구현
     */
    public void deleteNext(ListNode p) {
        if (head == null)    // head가 null이면 에러
            throw new NullPointerException();
        if (p == null)       // p가 null이면 첫 번째 노드 삭제
            head = head.link;
        else {
            ListNode q = p.link;
            if (q == null)   // 삭제할 노드가 없는 경우
                return;
            p.link = q.link;
        }
    }
 
    /**
     * 리스트의 원소를 역순으로 변환
     * 알고리즘 4.4의 Java 구현
     */
    public void reverse() {
        ListNode p = head;  // p는 역순으로 변환될 리스트
        ListNode q = null;  // q는 역순으로 변환될 노드
        ListNode r = null;
        while (p != null) {
            r = q;          // r은 역순으로 변환된 리스트
                            // r은 q, q는 p를 차례로 따라간다.
            q = p;
            p = p.link;
            q.link = r;     // q의 링크 방향을 바꾼다.
        }
        head = q;        
    }
 
    /**
     * 두 개의 리스트를 하나의 리스트로 연결
     * 알고리즘 4.5의 Java 구현
     */
    public LinkedList addList(LinkedList list) {
        if (head == null)
            head = list.head;
            return this;
        else if (list.head == null)
            return this;
        else {
            ListNode p = head;    // p는 임시 순회 포인터
            while (p.link != null)
                p = p.link;
            p.link = list.head;
            return this;
        }
    }
 
    /**
     * 단순 연결 리스트에서 원소 값이 x인 노드를 탐색
     * 알고리즘 4.6의 Java 구현
     */
    public ListNode searchNode(String x) {
        ListNode p = head;         // p는 임시 포인터
 
        while (p != null) {
            if (x.equals(p.data))  // 원소 값이 x인 노드를 발견
                return p;
            p = p.link;
        }
 
        return p;  // 원소 값이 x인 노드가 없는 경우 null을 반환
    }
 
 
    /**
     * 프로그램 4.2
     */
    public void deleteLastNode() {
        ListNode previousNode, currentNode;
 
        if (head == null)
            return;
 
        if (head.link == null) {
            head = null;
            return;
        } else {
            previousNode = head;
            currentNode = head.link;
            while (currentNode.link != null) {
                previousNode = currentNode;
                currentNode = currentNode.link;
            }
            previousNode.link = null;
        }
    }
 
    /**
     * 프로그램 4.3
     */
    public void printList() {
        ListNode p;
        System.out.print("(");
        p = head;
        while (p != null) {
            System.out.print(p.data);
            p = p.link;
            if (p != null) {
                System.out.print(", ");
            }
        }
    }
 
 
    public static void main(String args[]) {
        LinkedList L = new LinkedList();
        L.addLastNode(“Kim”);
        L.addLastNode(“Lee”);
        L.addLastNode(“Park”);
        L.printList();     	// (Kim, Lee, Park)가 프린트
        L.addLastNode(“Yoo”);   	// 원소 “Yoo”를 리스트 끝에 첨가
        L.printList();     	// (Kim, Lee, Park, Yoo)가 프린트
 
        L.deleteLastNode();     
        L.printList();     	// (Kim, Lee, Park)가 프린트
 
        L.reverse();
        L.printList();     	// (Park, Lee, Kim)이 프린트
    }
 
}