[Data Structure] 자료구조 - 연결 리스트(Linked List) - 원형 연결 리스트(Circular Linked List)

a

2. 환영 연결 리스트

자 2번째는 환영 연결 리스트(Circular Linked List) 입니다!

개념: 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드(Head)를 

가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트

그림을 통해서 먼저 삽입, 삭제 연산을 알아보도록합시다!

이번에도 진짜사나이 친구들이 나옵니다!

삽입 연산

 

단순 연결 리스트랑 다르게 

형식이도 다음 사람의 이름을 가지고 있는 겁니다!

이젠 기차가 아니라

강강 수월래 라고 할수 있겟죠??

저렇게 셋이서 강강 수월래~

하고 있는데!!

헨리가 이번에도 끼어서 하고 싶다네요~

그래서 샘과 형식 사이에 끼려고 합니다!!!

 

이렇게 말이죠~

아 그럼 어떻게 해야 할까요????

헨리가 샘과 형식 중간에 끼어들었군요.

그러면 서로 참조하는 값을 바꿔줘야 겠죠???

1) 샘은 헨리가 뒤에 있다는걸 알아야하고!

2) 헨리는 뒤에 형식이 있다는 걸 알아야 합니다!!!

1) 부터 풀어보면. 아래처럼 샘이 헨리를 참조하게 되겠죠??

 

2)을 풀어보면.

아래와 같이 될겁니다!!!

 

자 이렇게 해서 삽입 연산이 이루어 집니다!!!

중간에 끼어드는 알고리즘은 아래와 같습니다!

 

 
/*
    * CL: 연결 리스트
    * pre: 앞 노드
    * x: 입력할 데이터 값
*/
insertMiddleNode(CL, pre, x) {
    new <- getNode();
    new.data <- x;
    
    if (CL == NULL) then {
        CL <- new;
        new.link <- null;
    } else {
        new.link <- pre.link;
        pre.link <- new;
    }
}
 

삭제 연산

이번에는 형식이가 하차 한다고 하더군요.

한번 해봅시다!

 

헨리가 아직 형식이를 가리키고 있습니다... 

형식이는 하차를 할것이기 때문에.

인수인계(?)로 헨리에게 

자신이 참조한 값을 넘겨줍니다!

 

위와 같이 넘겨주고선, 형식이는 이제 ByeBye~

 

 

위와 같이 형식이 삭제되고 헨리가 참조하는 값을 경석 으로 바꿨습니다!

자 알고리즘으로 한번 보시겠습니다!!

 

 
/*
    * CL: 연결 리스트
    * pre: 삭제 할 노드의 앞 노드
*/
deleteNode(CL, pre) {
    if (CL == NULL) then error;
    else {
        old <- pre.link;
        pre.link <- old.link;
        if (old == CL) then 
            CL <- old.link;
        free old;
    }
}

자 그럼, 간단한 예제를 통해 접해보도록 하죠!!!

클래스 다이어 그램부터 보시죠~

 

CircuitLinkedList.java

 

package circuit;
 
import single.ListNode;
 
public class CircuitLinkedList {
    private ListNode head;
 
    public CircuitLinkedList() {
        head = null;
    }
 
    public void insertFirstNode(String data) {
        ListNode newNode = new ListNode(data);
        ListNode tmp;
        if (head == null) {
            head = newNode;
            head.setLink(head); // 환형 연결 리스트 이므로 초기에 자기자신 참조
        } else {
            tmp = head;
            while (tmp.getLink() != head) {
                tmp = tmp.getLink();
            } // 다음 링크가 head이면
 
            newNode.setLink(tmp.getLink());
            tmp.setLink(newNode);
            head = newNode;
        }
    }
 
    // 중간 노드 삽입
    public void insertMiddleNode(ListNode pre, String data) {
        if (pre == null) {
            return;
        }
        ListNode newNode = new ListNode(data);
 
        if (head == null) {
            head = newNode;
            newNode.setLink(newNode);
        } else {
            newNode.setLink(pre.getLink());
            pre.setLink(newNode);
        }
    }
 
    // 마지막 노드에 삽입
    public void insertLastNode(String data) {
        ListNode newNode = new ListNode(data);
 
        // 리스트가 비어있으면 헤드로 지정
        if (head == null) {
            this.head = newNode;
            head.setLink(head);
        } else {
            ListNode tmp = head;
            while (tmp.getLink() != head) {
                // 마지막 원소일때까지 탐색
                tmp = tmp.getLink();
            }
            tmp.setLink(newNode);
            newNode.setLink(head);
        }
    }
 
    public void deleteNode(ListNode pre) {
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        } else {
            ListNode old = pre.getLink();
            pre.setLink(old.getLink());
            if (old == head)
                head = old.getLink();
        }
    }
 
    public void deleteLastNode() {
        ListNode pre, tmp;
 
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        }
 
        if (head.getLink() == head) {
            head = null;
        } else {
            pre = head;
            tmp = head.getLink();
 
            // 마지막 노드의 이전 노드의 링크가 널인 값인지 까지 탐색
            while (tmp.getLink() != head) {
                pre = tmp;
                tmp = tmp.getLink();
            }
 
            pre.setLink(head);
        }
    }
 
    public ListNode searchNode(String data) {
        ListNode tmp = this.head;
 
        while (tmp != null) {
            if (data == tmp.getData())
                return tmp;
            if (tmp.getLink() == head) {
                System.out.println("찾고자 하는 데이터 " + data + "가 없습니다.");
                return null;
            }
 
            tmp = tmp.getLink();
        }
 
        return tmp;
    }
 
    public void printList() {
        ListNode tmp = this.head;
        System.out.print("L = (");
 
        while (tmp != null) {
            System.out.print(tmp.getData());
            tmp = tmp.getLink();
            if (tmp == head)
                break;
            if (tmp != null) {
                System.out.print(", ");
            }
        }
 
        System.out.println(")");
    }
 
}
 

CircuitMain.java

 

 
package circuit;
 
import single.ListNode;
 
public class CircuitMain {
    public static void main(String[] args) {
        CircuitLinkedList CL = new CircuitLinkedList();
        
        System.out.println("(1) 삽입 연산 수행하기");
        CL.insertFirstNode("월");
        ListNode pre = CL.searchNode("월");
        CL.insertMiddleNode(pre, "화");
        CL.insertLastNode("수");
        CL.insertLastNode("목");
        CL.printList();
        
        System.out.println("(2) 삭제 연산 수행하기");
        pre = CL.searchNode("월");
        CL.deleteNode(pre);
        CL.deleteLastNode();
        CL.printList();
    }
}
 

결과는 아래와 같습니다!!