[Java] Circular Linked List

✔️ 원형연결리스트(Circular Linked List)

• 마지막 노드가 첫 노드와 연결된 단일연결리스트
• 리스트가 empty가 아니면 어떤 노드도 null 레퍼런스를 가지고 있지 않으므로 프로그램에서 null 조건을 검사하지 않아도 되는 장점

💡 원형연결리스트의 노드 구조
마지막 노드의 레퍼런스가 저장된 last가 단일연결리스트의 head 역할을 함

1. 기본적인 원형연결리스트 클래스

import java.util.NoSuchElementException;

public class CircularLinkedList<E> {
    private static class Node<E> {
        private Node<E> last;
        private int size;

        public Node(E last, Object size) {
            last = null;
            size = 0;
        }
        private E element; // 항목 저장
        private Node<E> next; // Node 레퍼런스 저장
        // Node 생성자
        public Node(E e, Node<E> n) {
            element = e;
            next = n;
        }
        public E getElement() { return element; }
        public Node<E> getNext() { return next; }
        public void setNext(Node<E> n) { next = n; }
        public void CircularLinkedList() {}
        public int size() { return size; }
        public boolean isEmpty() { return size == 0; }
        // 마지막 노드 값 리턴
        public E last() {
            if(isEmpty()) return null;
            return last.getElement();
        }
      }
   }
}

last가 가리키는 노드의 다음에 새 노드 삽입

public void insert(E newItem) {
            Node newNode = new Node(newItem, null); // 새 노드 생성
            if(last == null) { // 리스트가 empty일 때
                newNode.setNext(newNode);
                last = newNode;
            }
            else { // 리스트가 empty가 아닐 때
                newNode.setNext(last.getNext()); // newNode의 다음 노드가 last가 가리키는 다음 노드가 됨
                last.setNext(newNode); // last가 가리키는 다음 노드가 newNode가 됨
            }
            size++;
}

last가 가리키는 노드의 다음 노드 삭제

public Node delete() {
            if(isEmpty()) throw new NoSuchElementException();
            Node x = last.getNext(); // x가 리스트의 첫 노드를 가리킴
            if(x == last) { // 리스트에 한 개의 노드만 있는 경우
                last = null;
            }
            else {
                last.setNext(x.getNext()); // last가 가리키는 노드의 다음 노드가 x의 다음 노드가 됨
                x.setNext(null); // x의 next를 null로 만듦
            }
            size--;
            return x;
}

---

✔️ 연결리스트 수행시간 비교

자료구조	i번째 요소 접근	값 탐색	삽입	삭제	비고
1차원 배열	O(1)	O(N)	O(N)	O(N)	정렬된 배열에서 탐색은 O(logN)
단일연결리스트	O(N)	O(1)	O(1)	O(1)
이중연결리스트	O(N)	O(1)	O(1)	O(1)	삽입 될 이전 노드의 레퍼런스가 주어진 경우
원형연결리스트	O(N)	O(1)	O(1)	O(1)