🛠️ Circular Doubly LinkedList 실전 구현 강의 (JAVA)

Circular Doubly LinkedList 자료구조

• 기존 Doubly LinkedList의 첫번째 노드와 마지막 노드 끼리 서로 연결 시켜, 원형 리스트 처럼 구성한 자료 구조
• 이러한 순환 구조는 티비 채널을 순회하거나 오디오 플레이어와 같이 데이터를 순차적 방식으로 처리하다 마지막 요소를 만나면 다시 처음 요소로 되돌아가는 애플리케이션에서 사용된다.
• 단일 연결 리스트를 원형으로 연결한 Circular Singly linkedList도 있다.

---

Circular Doubly LinkedList 구현하기 (JAVA)

우선 양방향 이중 연결 리스트를 구현하기 앞서 먼저 Doubly LinkedList 자료구조 구현을 연습 해보고 오는 것을 권장한다. Circular Doubly LinkedList는 기존 LinkedList의 양끝을 연결하는 것이기 때문에 기본 '링크드' 리스트 골자는 같기 때문이다.

다만 양방향 이중 연결 리스트에 노드를 추가 및 삭제하는 과정에서 각 노드들의 링크 처리하는 내부 로직이 약간 변경되기 때문에 간단하더라도 이러한 알고리즘을 직접 체험 연습해 보는 것이 좋다.

앞으로 구현할 메서드들은 대부분 Doubly LinkedList 자료구조에서 구현한것과 겹치니 최대한 부가적인 설명은 생략하고 노드 순환 연결에 초점에 맞춰 연재할 것이다. 만일 자세한 Doubly LinkedList에 대한 구성을 학습하고 싶다면 위의 이전 포스팅을 참고하길 바란다.

[DS] 🧱 Doubly LinkedList 직접 구현 해보기 (JAVA)

---

기본 클래스 구조 정의하기

클래스 필드와 생성자 그리고 리스트에 쓰일 노드 클래스를 정의해준다.

노드 객체 모양

public class CircularDoublyLinkedList<E> {

    private Node<E> head; // 노드의 첫 부분을 가리키는 레퍼런스
    private Node<E> tail; // 노드의 끝 부분을 가리키는 레퍼런스

    private int size; // 리스트 요소 갯수

    // 생성자
    public CircularDoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // 노드 클래스
    private static class Node<E> {
        private E item; // Node에 담을 데이터
        private Node<E> next; // 다음 Node 객체를 가르키는 래퍼런스
        private Node<E> prev; // 이전 Node 객체를 가르키는 래퍼런스

        // 생성자 (이전 노드 포인트 | 데이터 | 다음 노드 포인트)
        Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.next = next;
            this.prev = prev;
        }
    }
    
    // ...
    
}

---

add 구현하기

자바의 LinkedList 클래스의 add 메서드 종류를 보면 다음과 같이 4가지가 존재한다.

• void addFirst(Object obj) : 첫번째 위치에 요소 추가
• void addLast(Objec obj) : 마지막 위치에 요소 추가
• boolean add(Object obj) : 마지막 위치에 요소 추가 (성공하면 true)
• void add(int index, Object element) : 지정된 위치에 요소 추가

이중에서 circular 연결 리스트를 위한 추가 작업을 진행할 메소드는 addFirst() 와 addLast() 이다. 왜냐하면 처음과 마지막 노드가 서로 원형으로 이어져있기 때문에, 중간 삽입 메서드는 기존 연결 리스트와 다를바 없기 때문이다. 만일 그 이외의 메서드 구현도 알고 싶다면, 이전 LinkedList 구현 포스팅을 참고하길 바란다.

 

addFirst 구현

public void addFirst(E value) {

    // 1. head와 tail을 임시 백업함
    Node<E> first = head;
    Node<E> last = tail;

    // 2. 새 노드를 추가 (이때 첫번째 노드니까 prev는 null이 되고 next는 head가 가리키는 노드가 되게 된다)
    Node<E> new_node = new Node<>(null, value, first);

    // 3. 노드를 추가하였으니 리스트 크기 증가
    size++;

    // 4. 첫번째 기준이 변경되었으니 head를 삽입된 새 노드로 참조하도록 업데이트
    head = new_node;

    if (first == null) {
        // 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우,
        tail = new_node; // tail도 첫째 노드를 바라보도록 업데이트

        // circular 처리
        new_node.next = new_node; // 추가 노드는 서로 자기 자신을 참조하게 됨
        new_node.prev = new_node;
    } else {
        // 6. 만일 빈 리스트가 아닐경우,
        first.prev = new_node; // 추가되기 이전 첫번째이었던 노드에서 prev를 새 노드로 참조하도록 업데이트

        // circular 처리
        last.next = new_node; // 마지막 노드의 next를 추가 노드를 바라보도록 참조
        new_node.prev = last; // 추가 노드(첫번째)의 prev를 마지막 노드를 바라보도록 참조
    }
}

다음은 빈 리스트에 최초의 삽입 과정을 그림으로 나타낸 것이다.

 

1. 먼저 빈 리스트가 다음과 같이 존재한다. (비어있으니까 head와 tail은 각각 null이다)

 

2. 첫번째 노드(head)와 마지막 노드(tail)을 각각 fisrt와 last 변수에 백업한다.

3. 그리고 새 노드를 추가한다. 이때 최초의 노드이기 때문에 next 와 prev 모두 null 이 된다.

 

4. head가 첫번째인 새 노드를 바라보도록 업데이트 한다.

5. 백업한 first 변수의 값이 null 이므로 이는 최초 삽입 과정이 되게 되어, tail도 새 노드를 바라보도록 업데이트 한다.

 

6. 마지막으로 circular 처리를 한다. 최초의 삽입 과정이니 하나의 노드는 결국 자기 자신을 참조하는 꼴이 되게 된다.

 

다음은 이미 요소가 여러개 들어있는 리스트에 삽입 과정을 그림으로 나타낸 것이다.

 

1. 다음과 같이 요소 3개가 존재하고 첫번째 요소와 마지막 요소가 서로 순환 참조하고 있다.

 

2. 첫번째 노드(head)와 마지막 노드(tail)을 각각 fisrt와 last 변수에 백업한다.

 

3. 새 노드를 추가한다. 이때 추가 노드의 next는 first를 가리키게 된다.

4. 그리고 head를 새 노드를 가리키도록 업데이트 한다.

 

4. first가 null이 아니니 최종적으로 다음과 같이 circular 처리를 한다.

5. 두번째가 된 노드(first)의 prev는 추가 노드에 연결

6. 마지막 노드(last)의 next는 추가 노드에 연결

7. 추가 노드의 prev는 마지막 노드(last)에 연결

 

addLast 구현

public void addLast(E value) {

    // 1. head와 tail을 임시 백업함
    Node<E> first = head;
    Node<E> last = tail;

    // 2. 새 노드를 추가 (이때 마지막 노드니까 next는 null이 되고 prev는 tail이 가리키는 노드가 되게 된다)
    Node<E> new_node = new Node<>(last, value, null);

    // 3. 노드를 추가하였으니 리스트 크기 증가
    size++;

    // 4. 마지막 노드 기준이 변경되었으니 tail을 삽입된 새 노드로 참조하도록 업데이트
    tail = new_node;

    if (last == null) {
        // 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우,
        head = new_node; // tail도 첫째 노드를 바라보도록 업데이트

        // circular 처리
        new_node.next = new_node; // 추가 노드는 서로 자기 자신을 참조하게 됨
        new_node.prev = new_node;
    } else {
        // 6. 만일 빈 리스트가 아닐경우,
        last.next = new_node; // 추가되기 이전 마지막이었던 노드에서 next를 새 노드로 참조하도록 업데이트

        // circular 처리
        new_node.next = first; // 추가 노드(마지막)의 next를 첫번째 노드를 바라보도록 참조
        first.prev = new_node; // 첫번째 노드의 prev를 추가 노드를 바라보도록 참조
    }
}

다음은 빈 리스트에 최초의 삽입 과정을 그림으로 나타낸 것이다.

 

1. 먼저 빈 리스트가 다음과 같이 존재한다. (비어있으니까 head와 tail은 각각 null이다)

 

2. 첫번째 노드(head)와 마지막 노드(tail)을 각각 fisrt와 last 변수에 백업한다.

3. 그리고 새 노드를 추가한다. 이때 최초의 노드이기 때문에 next 와 prev 모두 null 이 된다.

 

4. tail이 마지막인 새 노드를 바라보도록 업데이트 한다.

5. 백업한 last 변수의 값이 null 이므로 이는 최초 삽입 과정이 되게 되어, first도 새 노드를 바라보도록 업데이트 한다.

 

6. 마지막으로 circular 처리를 한다. 최초의 삽입 과정이니 하나의 노드는 결국 자기 자신을 참조하는 꼴이 되게 된다.

 

다음은 이미 요소가 여러개 들어있는 리스트에 삽입 과정을 그림으로 나타낸 것이다.

 

1. 다음과 같이 요소 3개가 존재하고 첫번째 요소와 마지막 요소가 서로 순환 참조하고 있다.

 

2. 첫번째 노드(head)와 마지막 노드(tail)을 각각 fisrt와 last 변수에 백업한다.

 

3. 새 노드를 추가한다. 이때 추가 노드의 prev는 last를 가리키게 된다.

4. 그리고 tail을 새 노드를 가리키도록 업데이트 한다.

 

4. last가 null이 아니니 최종적으로 다음과 같이 circular 처리를 한다.

5. 마지막 이전 노드(last)의 next는 추가 노드에 연결

6. 첫번째 노드(first)의 prev는 추가 노드에 연결

7. 추가 노드의 next는 첫번째 노드(first)에 연결

---

remove 구현하기

LinkedList의 remove 메서드에는 다음 다섯가지 있다.

• Object removeFirst() : 맨 앞 요소를 제거 (제거한 요소는 반환)
• Object remove() : 맨 앞 요소를 제거
• Object removeLast() : 맨 뒤 요소를 제거 
• Object remove(int index) : 인덱스 위치의 요소를 제거
• boolean remove(Object value) : 요소값이 일치하는 위치의 요소를 제거 (중복 요소값이 있을 경우 맨앞의 요소가 제거)

이중에서 우리가 구현할 메소드는 removeFirst() 와 removeLast() 이다. 중간 제거 과정은 내부에서 인덱스가 0이나 마지막 위치일 경우 removeFirst() 와 removeLast() 를 재활용하면 되기 때문에 기존 LinkedList 구현과 다를바 없다.

 

removeFirst 구현

public E removeFirst() {

    // 1. 만약 삭제할 요소가 아무것도 없으면 에러
    if (head == null) {
        throw new RuntimeException();
    }

    // 2. 삭제될 첫번째 요소의 데이터를 백업
    E returnValue = head.item;

    // 3. 두번째 노드를 임시 저장
    Node<E> first = head.next;

    // 4. 첫번째 노드의 내부 요소를 모두 삭제
    head.next = null;
    head.item = null;

    // 5. head가 다음 노드를 가리키도록 업데이트
    head = first;

    // 6. 요소가 삭제 되었으니 크기 감소
    size--;

    // 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, tail도 null 처리
    if (head == null) {
        tail = null;
    }

    // 8. 마지막으로 삭제된 요소를 반환
    return returnValue;
}

 

1. 반환할 삭제할 마지막 요소 데이터를 백업한다.

2. 마지막 요소가 삭제가 되면 마지막 이전 요소가 마지막이되기 때문에 변수 last에 저장해서 나중에 다루도록 한다.

3. 추후에 cicular 처리를 위해 첫번째 요소도 first에 저장해준다.

 

4. 마지막 노드의 모든 데이터를 null로 처리한다.

 

4. head의 포인트를 first 변수에 저장해두었던 두번째 노드(@200)으로 업데이트한다.

5. 리스트의 첫번째 노드가 된 first의 노드 prev를 마지막 노드(last)로 연결한다.

6. 리스트의 마지막 노드의 next를 first로 연결한다.

7. 아무것도 연결되지 않아 고아가 되버린 노드는 나중에 GC가 수거해 간다.

+ 만일 삭제할 요소가 리스트의 유일한 요소라면, 삭제할시 빈 리스트가 되므로 head와 tail을 null이 되도록 업데이트 해준다.

 

removeLast 구현

1. 반환할 삭제할 마지막 요소 데이터를 백업한다.

2. 마지막 요소가 삭제가 되면 마지막 이전(@200) 노드가 마지막이 되기 때문에 마지막 이전 요소를 변수 last에 저장해서 나중에 다루도록 한다.

 

3. 마지막 노드의 모든 데이터를 null로 처리한다.

 

4. tail의 포인트를 last 변수에 저장해두었던 마지막 노드(@200)으로 업데이트한다.

5. 리스트의 마지막 노드가 된 last의 노드 next를 첫번째 노드(first)로 연결한다.

6. 리스트의 첫번째 노드의 prev를 마지막 노드로 연결한다. 

7. 아무것도 연결되지 않아 고아가 되버린 노드는 나중에 GC가 수거해 간다.

+ 만일 삭제할 요소가 리스트의 유일한 요소라면, 삭제할시 빈 리스트가 되므로 head와 tail을 null이 되도록 업데이트 해준다.

---

toString 구현

마지막으로 링크드 리스트 요소들을 출력하기 위해 Object 클래스의 toString() 메소드를 오버라이딩 하자. 그리고 다음과 같이 직접 문자열 더하기 연산으로도 구현한다. 이때 주의해야 할 점은 Circular LinkedList는 노드간에 모두 참조가 되어 있기 때문에 next나 prev가 null 일 경우의 수는 사용 못한다. 따라서 리스트의 사이즈 까지 인덱스 순회로 구성해주어야 한다.

@Override
public String toString() {
    if(head == null) {
        return "[]";
    }

    Node<E> n = head;
    String result = "[";

    while(n.next != null) {
        result += n.item + ", ";
        n = n.next;
    }

    // n이 마지막일 경우 n.next가 null이니 루프문을 빠져나오게 되서 마지막 노드 삽입 처리를 해주어야 한다.
    result += n.item + "]"; 

    return result;
}

 

Circular LinkedList 커스텀 toString

기존 toString 처럼 단순히 배열 문자열을 콘솔에 출력하는 것이 아닌, 각 노드의 링크드 주소와 함께 연결 리스트의 전체 참조 요소들을 출력해주는 커스텀 toString() 메서드를 만들어 보았다.

왼쪽은 해당 리스트 원소 노드의 주소 해시값이며, [이전 노드 주소 | 노드 아이템값 | 다음 노드 주소] 식으로 요소를 출력한다. 만일 독자분들이 구축한 메서드가 정말로 링크 연결이 잘 동작되는지 확인해보고 싶다면 이 커스텀 메서드를 통해 한눈에 노드 참조를 확인할 수 있을 것이다.

public String toString2() {
    if (head == null) {
        return "[]";
    }

    Node<E> n = head;
    StringBuilder result = new StringBuilder();

    result.append("[\n");

    for(int i = 0; i< size; i++) {

        result.append("  Node@").append(String.format("%-10s", n.hashCode())).append("  →  ");

        if (n.prev != null) {
            result.append("[").append(n.prev.hashCode()).append(" | ");
        } else {
            result.append("[").append("null").append(" | ");
        }

        result.append(n.item).append(" | ");

        if (n.next != null) {
            result.append(n.next.hashCode()).append("]");
        } else {
            result.append("null").append("]");
        }

        result.append(", \n");

        n = n.next;
    }

    result.append("]");

    return result.toString();
}

public static void main(String[] args) {
    MyDoublyLinkedList<Number> list = new MyDoublyLinkedList<>();
    
    list.addLast(2);
    list.addFirst(1);
    list.addLast(3);
    list.add(2, 2.5);
    
    System.out.println(list.toString2());
}

---

Circular Doubly LinkedList 구현 전체 코드

public class CircularDoublyLinkedList<E> {

    private Node<E> head; // 노드의 첫 부분을 가리키는 레퍼런스
    private Node<E> tail; // 노드의 끝 부분을 가리키는 레퍼런스

    private int size; // 리스트 요소 갯수

    // 생성자
    public CircularDoublyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // inner static class
    private static class Node<E> {
        private E item; // Node에 담을 데이터
        private Node<E> next; // 다음 Node 객체를 가르키는 래퍼런스
        private Node<E> prev; // 이전 Node 객체를 가르키는 래퍼런스

        // 생성자 (이전 노드 포인트 | 데이터 | 다음 노드 포인트)
        Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.next = next;
            this.prev = prev;
        }
    }

    private Node<E> search(int index) {
        Node<E> n; // 반환할 노드

        if ((size / 2) > index) {
            // 1. 만일 인덱스가 시작에 가까우면, 순차 탐색
            n = head;
            for (int i = 0; i < index; i++) {
                n = n.next;
            }
        } else {
            // 2. 만일 인덱스가 끝에 가까우면, 역순 탐색
            n = tail;
            for (int i = size; i > index; i--) {
                n = n.prev;
            }
        }

        return n;
    }

    public void addFirst(E value) {

        // 1. head와 tail을 임시 백업함
        Node<E> first = head;
        Node<E> last = tail;

        // 2. 새 노드를 추가 (이때 첫번째 노드니까 prev는 null이 되고 next는 head가 가리키는 노드가 되게 된다)
        Node<E> new_node = new Node<>(null, value, first);

        // 3. 노드를 추가하였으니 리스트 크기 증가
        size++;

        // 4. 첫번째 기준이 변경되었으니 head를 삽입된 새 노드로 참조하도록 업데이트
        head = new_node;

        if (first == null) {
            // 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우,
            tail = new_node; // tail도 첫째 노드를 바라보도록 업데이트

            // circular 처리
            new_node.next = new_node; // 추가 노드는 서로 자기 자신을 참조하게 됨
            new_node.prev = new_node;
        } else {
            // 6. 만일 빈 리스트가 아닐경우,
            first.prev = new_node; // 추가되기 이전 첫번째이었던 노드에서 prev를 새 노드로 참조하도록 업데이트

            // circular 처리
            last.next = new_node; // 마지막 노드의 next를 추가 노드를 바라보도록 참조
            new_node.prev = last; // 추가 노드(첫번째)의 prev를 마지막 노드를 바라보도록 참조
        }
    }

    public void addLast(E value) {

        // 1. head와 tail을 임시 백업함
        Node<E> first = head;
        Node<E> last = tail;

        // 2. 새 노드를 추가 (이때 마지막 노드니까 next는 null이 되고 prev는 tail이 가리키는 노드가 되게 된다)
        Node<E> new_node = new Node<>(last, value, null);

        // 3. 노드를 추가하였으니 리스트 크기 증가
        size++;

        // 4. 마지막 노드 기준이 변경되었으니 tail을 삽입된 새 노드로 참조하도록 업데이트
        tail = new_node;

        if (last == null) {
            // 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우,
            head = new_node; // tail도 첫째 노드를 바라보도록 업데이트

            // circular 처리
            new_node.next = new_node; // 추가 노드는 서로 자기 자신을 참조하게 됨
            new_node.prev = new_node;
        } else {
            // 6. 만일 빈 리스트가 아닐경우,
            last.next = new_node; // 추가되기 이전 마지막이었던 노드에서 next를 새 노드로 참조하도록 업데이트

            // circular 처리
            first.prev = new_node; // 첫번째 노드의 prev를 추가 노드를 바라보도록 참조
            new_node.next = first; // 추가 노드(마지막)의 next를 첫번째 노드를 바라보도록 참조
        }
    }

    public boolean add(E value) {
        addLast(value);
        return true;
    }

    public void add(int index, E value) {
        // 1. 인덱스 범위 체크
        // 인덱스가 0보다 작거나 size 보다 클 경우 에러
        // (인덱스가 size보다 크면 마지막 요소 다음 빈공간의 다음 빈공간을 가리키는 거니까)
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        // 2. 추가하려는 index가 0이면 addFirst 호출
        if (index == 0) {
            addFirst(value);
            return;
        }

        // 3. 추가하려는 index가 size와 같으면 addLast 호출
        if (index == size) {
            addLast(value);
            return;
        }

        // 4. 추가하려는 위치의 다음 노드 얻기
        Node<E> next_node = search(index);

        // 5. 추가하려는 위치의 이전 노드 얻기
        Node<E> prev_node = next_node.prev;

        // 6. 새 노드 생성 (바로 이전 / 다음 노드와 연결됨)
        Node<E> new_node = new Node<>(prev_node, value, next_node);

        // 7. 노드를 추가하였으니 리스트 크기 증가
        size++;

        // 8. 이전 노드의 next를 새 노드에 연결
        prev_node.next = new_node;

        // 9. 다음 노드의 prev를 새 노드에 연결
        next_node.prev = new_node;
    }

    public E removeFirst() {

        // 1. 만약 삭제할 요소가 아무것도 없으면 에러
        if (head == null) {
            throw new NoSuchElementException();
        }

        // 2. 삭제될 첫번째 요소의 데이터를 백업
        E value = head.item;

        // 3. 두번째 노드와 마지막 노드를 임시 저장
        Node<E> first = head.next;
        Node<E> last = tail;

        // 4. 첫번째 노드의 내부 요소를 모두 삭제
        head.next = null;
        head.item = null;
        head.prev = null;

        // 5. 요소가 삭제 되었으니 크기 감소
        size--;

        // 6. head가 다음 노드를 가리키도록 업데이트
        head = first;

        if (first == null) {
            // 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, tail도 null 처리
            tail = null;
        } else {
            // 8. 만일 빈 리스트가 아닐경우, circular 처리
            first.prev = last; // 삭제되기 이전 두번째 이었던 first가 첫번째 노드가 되니 prev를 마지막 노드에 연결
            last.next = first; // 마지막 노드의 next도 첫번째 노드인 first에 연결
        }

        // 9. 마지막으로 삭제된 요소를 반환
        return value;
    }

    public E removeLast() {

        // 1. 만약 삭제할 요소가 아무것도 없으면 에러
        if (tail == null) {
            throw new NoSuchElementException();
        }

        // 2. 삭제될 마지막 요소의 데이터를 백업
        E value = tail.item;

        // 3. 마지막 노드의 이전 노드와 첫번째 노드를 임시 저장
        Node<E> last = tail.prev;
        Node<E> first = head;

        // 4. 마지막 노드의 내부 요소를 모두 삭제
        tail.item = null;
        tail.prev = null;
        tail.next = null;

        // 5. 요소가 삭제 되었으니 크기 감소
        size--;

        // 6. tail이 이전 노드를 가리키도록 업데이트
        tail = last;

        if (last == null) {
            // 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, head도 null 처리
            head = null;
        } else {
            // 8. 만일 빈 리스트가 아닐경우, circular 처리
            first.prev = last; // 삭제되기 이전 두번째 이었던 first가 첫번째 노드가 되니 prev를 마지막 노드에 연결
            last.next = first; // 마지막 노드의 next도 첫번째 노드인 first에 연결
        }

        // 9. 마지막으로 삭제된 요소를 반환
        return value;
    }

    @Override
    public String toString() {
        if (head == null) {
            return "[]";
        }

        Node<E> n = head;
        String result = "[";

        // circular 연결 리스트는 노드의 next가 끝이 없기 때문에 인덱스 사이즈로 순회하여야 한다.
        for (int i = 0; i < size; i++) {
            result += n.item + ", ";
            n = n.next;
        }

        // n이 마지막일 경우 n.next가 null이니 루프문을 빠져나오게 되서 마지막 노드 삽입 처리를 해주어야 한다.
        result += n.item + "]";

        return result;
    }

    public String toString2() {
        if (head == null) {
            return "[]";
        }

        Node<E> n = head;
        StringBuilder result = new StringBuilder();

        result.append("[\n");

        int i = 0;
        while (i < size) {
            i++;

            result.append("  Node@").append(String.format("%-10s", n.hashCode())).append("  →  ");

            if (n.prev != null) {
                result.append("[").append(n.prev.hashCode()).append(" | ");
            } else {
                result.append("[").append(n.prev).append(" | ");
            }

            result.append(n.item).append(" | ");

            if (n.next != null) {
                result.append(n.next.hashCode()).append("]");
            } else {
                result.append(n.next).append("]");
            }

            result.append(", \n");

            n = n.next;
        }

        result.append("]");

        return result.toString();
    }
}

마지막으로 내가 직접 짠 자료구조 클래스가 정상적으로 예외 없이 동작하는지 데이터 테스트를 잊지말자!

public static void main(String[] args) {

    CircularDoublyLinkedList<Number> list = new CircularDoublyLinkedList<>();

    list.addFirst(3);
    list.addFirst(2);
    list.addFirst(1);
    list.addLast(4);

    list.add(3, 3.5);
    list.add(1, 1.5);

    System.out.println(list.toString2());

    list.removeFirst();
    list.removeFirst();
    list.removeLast();

    System.out.println(list.toString2());
}

---

 # 참고자료

https://www.alphacodingskills.com/ds/circular-doubly-linked-list.php