원형 연결 리스트 특징, 정의, 장단점

원형 연결 리스트는 모든 노드가 원으로 연결되어 있는 리스트입니다.

첫 번째 노드와 마지막 노드가 서로 연결되어 원을 형성합니다. 끝에 NULL은 없습니다.

 

원형 단일 연결 리스트 

원형 단일 연결 리스트에서는 마지막 노드에 첫 번째 노드에 대한 포인터가 있습니다. 동일한 노드에 도달할 때까지 원형 단일 연결 리스트를 탐색합니다. 원형 단일 연결 리스트에서는 시작이나 끝이 없습니다. 노드 포인터에는 null 값이 없습니다.

원형 단일 연결 리스트 표현

public class Node {
    int data;
    Node next;
    
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

 

기본 원형 단일 연결 리스트

public class Node {
    int data;
    Node next;
    
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Node one = new Node(3);
Node two = new Node(4);
Node three = new Node(5);

one.next = two;
two.next = three;
three.next = one;

three에서 next 포인터를 one으로 가리키게 해서 원형 연결 리스트를 만들었습니다.

 

원형 이중 연결 리스트

원형 이중 연결 리스트에서는 마지막 노드 next가 첫번째 노드를 가리키고 첫 번째 노드 prev는 마지막 노드를 가리킵니다.

 

원형 이중 연결 리스트 표현

public class Node {
    int data;
    Node next;
    Node prev;
    
    public Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

기본 원형 이중 연결 리스트

public class Node {
    int data;
    Node next;
    
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Node one = new Node(3);
Node two = new Node(4);
Node three = new Node(5);

one.next = two;
one.prev = three;
two.next = three;
tow.prev = one;
three.next = one;
three.prev = two;

 

원형 연결 리스트의 장점

• 모든 노드가 시작점이 될 수 있습니다. 어느 지점에서 시작하여 전체 목록을 탐색할 수 있습니다. 처음 방문한 노드를 다시 방문할 때 중지하면 됩니다.
• 큐 구현에 유용합니다. 원형 연결 리스트를 사용하는 경우 front 및 rear에 대한 2개의 포인터를 유지할 필요가 없습니다.
• 원형 이중 연결 리스트같은 경우에는 피보나치 힙과 같은 고급 데이터 구조를 구현하는데 사용됩니다.

원형 연결 리스트의 단점

• 단일 연결 리스트보다 더 복잡합니다.
• 리스트를 뒤집는 것은 단일 또는 이중보다 더 복잡합니다.
• 무한 루프에 빠질 수 있습니다.
• 리스트의 끝 노드를 찾는게 어렵습니다.
• 개별 노드에 대한 직접적인 접근은 제공하지 않습니다.