Lecture/자료구조/2011/4.5 원형 연결 리스트

교과서에 있는 방법

public class CircularLinkedList {
    private ListNode head;
 
    public CircularLinkedList() {
        head = null;
    }
 
    /**
     * 원형 연결 리스트의 처음에 노드를 삽입한다.
     * @param p 삽입하고자 하는 노드
     */
    public void insertFront(ListNode p) {
        if (head == null) {
            head = p;
            p.link = head;
        } else {
            p.link = head.link;
            head.link = p;
        }
    }
 
    /**
     * 원형 연결 리스트의 마지막에 노드를 삽입한다.
     * @param p 삽입하고자 하는 노드
     */
    public void insertLast(ListNode p) {
        if (head == null) {
            head = p;
            p.link = head;
        } else {
            p.link = head.link;
            head.link = p;
            head = p;
        }
    }
 
    /**
     * 리스트의 길이를 반한하는 메소드
     * @return 리스트의 길이
     */
    public int length() {
        if (head == null)
            return 0;
 
        int length = 1;
        ListNode p = head.link;
        while (p != head) {
            length++;
            p = p.link;
        }
        return length;
    }
}

개선한 방법

public class CircularLinkedList {
    private ListNode head;
    private int length;
 
    public CircularLinkedList() {
        head = null;
        length = 0;
    }
 
    /**
     * 원형 연결 리스트의 처음에 노드를 삽입한다.
     * @param p 삽입하고자 하는 노드
     */
    public void insertFront(ListNode p) {
        if (head == null) {
            head = p;
            p.link = head;
        } else {
            p.link = head.link;
            head.link = p;
        }
        length++;
    }
 
    /**
     * 원형 연결 리스트의 마지막에 노드를 삽입한다.
     * @param p 삽입하고자 하는 노드
     */
    public void insertLast(ListNode p) {
        insertFront(p);
        head = p;
    }
 
    /**
     * 리스트의 길이를 반한하는 메소드
     * @return 리스트의 길이
     */
    public int length() {
        return length;
    }
}