원형 이중 연결 리스트

• 원형 리스트 : 연결 리스트의 꼬리 노드가 머리 노드를 가리키는 자료구조. 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조이다.
• 이중 연결 리스트 : 각 노드가 다음 노드에 대한 포인터와 앞쪽 노드에 대한 포인터를 가지고 있는 자료구조. 양방향 리스트라고도 한다.
• 원형 이중 연결 리스트는 이 두가지의 개념이 합해진 구조이다.
• 원형 이중 연결 리스트에서는 노드의 삽입과 삭제 처리를 원활하게 하도록 리스트의 머리에 계속 존재하는 더미 노드를 가진다.

//원형 이중 연결 리스트 클래스
 
public class DblLinkedList<E> {
 
    //노드
    class Node<E> {
        private E data;          //데이터
        private Node<E> prev;    //앞쪽 포인터(앞쪽 노드)
        private Node<E> next;    //뒤쪽 포인터(다음 노드)
        
        Node() {
            data = null;
            prev = next = this;
        }
        
        Node(E obj, Node<E> prev, Node<E> next) {
            data = obj;
            this.prev = prev;
            this.next = next;
        }
    }
    
    private Node<E> head;                //더미 노드
    private Node<E> crnt;                //선택 노드
    
    public DblLinkedList() {
        head = crnt = new Node<E>();    //더미 노드 생성(데이터를 갖지 않는 노드 1개 생성)
    }
    
    //리스트가 비어 있는가?(더미 노드만 있는가)
    public boolean isEmpty() {
        return head.next == head;
    }
    
    //노드를 검색
    public E search(E obj, Comparator<? super E> c) {
        Node<E> ptr = head.next;        //실질적인 머리 노드인 더미 노드의 다음 노드부터 검색 시작
        
        while (ptr != head) {
            if (c.compare(obj, ptr.data) == 0) {
                crnt = ptr;
                return ptr.data;        //검색 성공
            }
            ptr = ptr.next;             //다음 노드로
        }
        return null;                    //검색 실패
    }
    
    //선택 노드를 출력
    public void printCurrnetNode() {
        if (isEmpty()) {
            System.out.println("선택 노드가 없습니다.");
        } else {
            System.out.println(crnt.data);
        }
    }
    
    //모든 노드를 출력
    public void dump() {
        Node<E> ptr = head.next;        //더미 노드의 다음 노드
        
        while (ptr != head) {
            System.out.println(ptr.data);
            ptr = ptr.next;
        }
    }
    
    //모든 노드를 거꾸로 출력
    public void dumpReverse() {
        Node<E> ptr = head.prev;        //더미 노드의 앞쪽 노드(=꼬리 노드)
        
        while (ptr != head) {
            System.out.println(ptr.data);
            ptr = ptr.prev;
        }
    }
    
    //선택 노드를 하나 뒤쪽으로 이동
    public boolean next() {
        if (isEmpty() || crnt.next == head) {
            return false;
        }
        crnt = crnt.next;
        return true;
    }
    
    //선택 노드를 하나 앞쪽으로 이동
    public boolean prev() {
        if (isEmpty() || crnt.prev == head) {
            return false;
        }
        crnt = crnt.prev;
        return true;
    }
    
    //선택 노드의 바로 뒤에 노드를 삽입
    public void add(E obj) {
        Node<E> node = new Node<E>(obj, crnt, crnt.next);
        crnt.next = crnt.next.prev = node;        //새로 삽입한 노드를 가리키도록 업데이트
        crnt = node;
    }
    
    //머리에 노드 삽입
    public void addFirst(E obj) {
        crnt = head;                //더미 노드 head의 바로 뒤에 삽입
        add(obj);
    }
    
    //꼬리에 노드 삽입
    public void addLast(E obj) {
        crnt = head.prev;            //꼬리 노드 head.prev의 바로 뒤에 삽입
        add(obj);
    }
    
    //선택 노드를 삭제
    public void removeCurrentNode() {
        if (!isEmpty()) {
            crnt.prev.next = crnt.next;
            crnt.next.prev = crnt.prev;
            crnt = crnt.prev;
            if (crnt == head) crnt = head.next;
        }
    }
    
    //노드 p를 삭제
    public void remove(Node p) {
        Node<E> ptr = head.next;
        
        while (ptr != head) {
            if (ptr == p) {
                crnt = p;
                removeCurrentNode();
                break;
            }
            ptr = ptr.next;
        }
    }
    
    //머리 노드를 삭제
    public void removeFirst() {
        crnt = head.next;
        removeCurrentNode();
    }
    
    //꼬리 노드를 삭제
    public void removeLast() {
        crnt = head.prev;
        removeCurrentNode();
    }
    
    //모든 노드를 삭제
    public void clear() {
        while (!isEmpty()) {
            removeFirst();
        }
    }
    
    // comparator c에 의해 서로 같다고 보는 노드를 모두 삭제
    public void purge(Comparator<? super E> c) {
        Node<E> ptr = head.next;
 
        while (ptr.next != head) {
            int count = 0;
            Node<E> ptr2 = ptr;
            Node<E> pre = ptr;
 
            while (pre.next != head) {
                ptr2 = pre.next;
                if (c.compare(ptr.data, ptr2.data) == 0) {
                    pre.next = ptr2.next;
                    count++;
                } else {
                    pre = ptr2;
                }
            }
            if (count == 0) {
                ptr = ptr.next;
            } else {
                Node<E> temp = ptr;
                remove(ptr);
                ptr = temp.next;
            }
        }
        crnt = head;
    }
    
    //머리부터 n개 뒤 노드의 데이터에 대한 참조를 반환
    public E retrieve(int n) {
        Node<E> ptr = head.next;
        
        while (n >= 0 && ptr.next.next != head) {
            if (n-- == 0) {
                crnt = ptr;
                return ptr.data;
            }
            ptr = ptr.next;
        }
        return null;
    }
}