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

원형 연결 리스트는 이중 연결 리스트에서 마지막 노드가 첫번째 노드를 가리킨 것이다.

즉, 마지막 노드와 첫번째 노드가 연결되어 있어서 순회가 가능하다.

마지막 노드에서 첫번째 노드로 다시 돌아오는 과정이 이중 연결 리스트보다 간단하다.

 

원형 연결 리스트 구현

1. 노드 클래스 구현

class Node{
    private String data;
    public Node nextNode;
    public Node preNode;

    public Node(String data) {
        this.data = data;
        this.nextNode = null;
        this.preNode = null;
    }

    public String getData() {
        return this.data;
    }
}

 

2. 원형 연결 리스트 클래스 구현

class CircularLinkedList {
    private Node head;
    private Node tail;

	public void insertNode(String data) {...}	// 노드 삽입 메서드
    public void deleteNode(String data) {...}	// 노드 삭제 메서드
    public Node searchNode(String data) {...}	// 노드 검색 메서드
}

 

3. 노드 삽입 메서드 구현

public void insertNode(String data) {
	Node newNode = new Node(data);
    if (head == null) {
	    head = newNode;
        tail = newNode;
        tail.nextNode = head;
    }else{
        tail.nextNode = newNode;
        newNode.nextNode = head;
        tail = newNode;
    }
}

 

4. 노드 삭제 메서드 구현

public void deleteNode(String data) {
    Node currNode = head;
    Node preNode = head.preNode;
    Node nextNode = head.nextNode;

    if(data.equals(currNode.getData())){
        head = nextNode;
        head.preNode = null;
        tail.nextNode = head;
        currNode.nextNode = null;
    }else{
    	while(currNode.nextNode != this.head){
        	if (data.equals(currNode.getData())) {
            	if (currNode == this.tail) {
                	preNode.nextNode = head;
                    currNode.nextNode = null;
                    this.tail = preNode;
                } else {
                    preNode.nextNode = currNode.nextNode;
                    nextNode.preNode = preNode;
                    currNode.preNode = null;
                    currNode.nextNode = null;
                } break;
                }else{
                    preNode = currNode;
                    currNode = currNode.nextNode;
                }
            }
        }
    }
}

 

5. 노드 검색 메서드

public Node searchNode(String data) {
	Node tempNode = this.head;
    while (tempNode.nextNode != this.head) {
	    if (data.equals(tempNode.getData())) {
        	return tempNode;
        } else {
            tempNode = tempNode.nextNode;
        }
    }
    return tempNode;
}