[자료구조] 원형 연결 리스트(Circular Linked List) 구현

1. 코드

class CircularLinkedList {
    NodeBi head;
    NodeBi tail;
    
    CircularLinkedList(NodeBi node) {
        this.head = node;
        this.tail = node;
        node.next = this.head;
        node.prev = this.head;
    }
    
    public boolean isEmpty() {
        if(this.head == null) {
            return true;
        }
        return false;
    }

    // 데이터 추가
    // before_data가 null인 경우, 가장 끝에 추가
    // before_data에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
    public void addData(int data, Integer beforeData) {
        if(this.head == null) {
            NodeBi newNodeBi = new NodeBi(data, null, null);
            this.head = newNodeBi;
            this.tail = newNodeBi;
            newNodeBi.next = newNodeBi;
            newNodeBi.prev = newNodeBi;
        } else if(beforeData == null) { // 가장 끝에 데이터 추가
            NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
            this.tail.next = newNodeBi;
            this.head.prev = newNodeBi;
            this.tail = newNodeBi;
        } else {
            NodeBi cur = this.head;
            NodeBi prev = cur;
            do {
                if(cur.data == beforeData) {
                    if(cur == this.head) { // 가장 앞에 데이터 추가
                        NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
                        this.tail.next = newNodeBi;
                        this.head.prev = newNodeBi;
                        this.tail = newNodeBi;
                    } else { // 중간에 데이터 추가
                        NodeBi newNodeBi = new NodeBi(data, cur, prev);
                        prev.next = newNodeBi;
                        cur.next = newNodeBi;
                    }
                    break;
                }
                prev = cur;
                cur = cur.next;
            } while(cur != this.head)
        }
    }
    
    // 특정 값을 가진 노드 삭제
    public void removeData(int data) {
        if(this.isEmpty()) {
            System.our.println("List is Empty");
            return;
        }
        
        NodeBi cur = this.head;
        NodeBi prev = cur;
        
        while(cur != null) {
            if(cur.data == data) {
                if(cur == this.head && cur == this.tail) { // 데이터 한개인 경우
                    this.head = null;
                    this.tail = null;
                } else if(cur == this.head) { // 데이터가 가장 앞에 있는 경우
                    cur.next.prev = this.head.prev;
                    this.head = cur.next;
                    this.tail.next = this.head;
                } else if(cur == this.tail) { // 데이터가 가장 끝에 있는 경우
                    prev.next = this.tail.next;
                    this.tail = prev;
                    this.head.prev = this.tail;
                } else { // 데이터가 중간에 있는 경우
                    prev.next = cur.next;
                    cur.next.prev = prev;
                }
                break;
            }
            prev = cur;
            cur = cur.next;
        }
    }
    
    // 출력
    public void showData() {
        if(this.isEmpty()) {
            System.out.println("List is empty");
            return;
        }
        
        NodeBi cur = this.head;
        while (cur.next != this.head) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println(cur.data);
    }
}