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

Circular Linked List는 Singly Linked List(단일 연결 리스트)의 확장된 개념이다. 나는 단일 연결 리스트의 끝 원소(꼬리, tail)를 가장 앞 원소(머리, head)로 이어줌으로써 선형의 리스트가 둥글게 말리는 효과를 얻는다고 이해했다. 그래서 내가 이해한 바를 토대로 오늘 구현을 시작했다.

---

장점

효율적인 탐색 : 원형 연결 리스트의 어느 부분에서 시작하던, 모든 노드(원소)들을 탐색할 수 있다.

---

단점

메모리 사용량 : 마지막 노드(원소)가 처음 노드를 가리키기 때문에 약간의 메모리를 더 사용한다.

무한 루프 : 마지막 노드가 처음 노드를 가리키기 때문에 조건 등을 걸지 않고 탐색하면 무한 루프에 빠질 수 있다.

삭제 코드의 복잡성 :  head나 tail 노드의 경우, 삭제할 때 구현이 복잡하다.

 

단점이 더 많은 만큼, 특별한 경우가 아니라면 굳이 사용하지는 않을 것 같다.

---

기본 틀을 만들었다. 만들어둔 메서드들을 일부 수정하면서 원형 연결 리스트를 구현할 것이다. 아래 더 보기를 누르면 스켈레톤 코드가 나온다.

스켈레톤 코드

package LinkedList;

public class CircularLinkedList {
    class Node{
        int data;
        Node next;
        Node(int data) {
            this.data = data;
        }
        void setNext(Node next) {
            this.next = next;
        }
    }
    CircularLinkedList() {
        // 필요없음
    }
    int size;
    Node tail;
//    Node head; // -> tail.next와 같음. 그래서 굳이 필요없음

    //삽입
    // 오름차순으로 정렬되도록 삽입을 구현할 예정임. (tail이 가장 큰 수가 되도록)
    public void insert(int data) {
        insert(new Node(data));
    }
    
    public void insert(Node node) {

    }

    //삭제
    // 해당 data를 가진 노드를 삭제함.
    public void delete(int data) {
        delete(new Node(data));
    }
    // 노드의 data를 기준으로 노드를 삭제함.
    public void delete(Node node) {

    }

    //탐색
    public Node search(int index){
        Node node = tail.next; //==head
        int current = 0;
        while (current++ < index) {
            node = node.next;
        }
        return node;
    }

    //출력
    public void print() {
        Node node = tail.next;
        if (node == null) {
            return;
        }
        for (int i=0; i<size; i++) {
            System.out.printf("%d번째 노드 | %d\n", i+1, node.data);
            node = node.next;
        }
    }
}

---

insert method

삽입을 할 때의 경우를 떠올려보았다.

case 0 : 리스트가 비어있는 경우

case 1 : 리스트의 원소가 하나 이상인 경우

---

case 0 : 빈 리스트

tail도 null을 가리키고 있다. 새로 삽입하는 tail을 새로 넣으려는 노드로 가리킨다.

public void insert(Node node) {
    if (size == 0) {
        // 리스트 안에 원소(노드)가 하나도 없는 경우
        tail = node;
        size++;
        return;
    }
    . . .
}

---

case1 : 원소가 하나인 경우

맨 처음에 이 경우를 떠올리지 못해서 디버깅을 여럿 시도했다.

이렇게 구분하는 이유는 원소가 하나인 경우에는 tail.next = null이라서 tail.next로 head부터 선형탐색을 하던 중 필히nullPointException이 발생한다. 그래서 이 경우를 대비해서 따로 만들었다.

그리고 이 케이스에는 새로 넣는 노드가 기존 노드보다 더 큰 값인 경우에만 끝 노드 설정을 새로하도록 조건문을 넣었다. 그 외의 경우에는 tail은 고정이다.

public void insert(Node node) {
	. . .
        else if (size == 1){ //tail == head
            tail.next = node;
            node.next = tail;
            if (tail.data < node.data) {
                tail = node;
            }
            size++;
            return;
        }
	. . .
    }

---

case 2 : 원소가 하나 이상인 경우

이제부턴 이미 있는 원소랑 비교해가면서 새 노드가 제자리를 찾도록 해야 한다. 나는 오름차순으로 정렬토록 설계했다.

public void insert(Node node) {
		. . .
        Node current = tail.next;
        for (int i=0; i<size; i++) {
            if (current.data < node.data) {
                // 다음 노드랑 new node랑 비교해야지
                // 그런데 다음 노드가 null, 즉 current가 tail인 경우는 어떡해?
                if (i == size-1) {
                    // current가 tail인 경우.
                    tail = node;
                    node.next = current.next;
                    current.next = node;
                    size++;
                    return;
                } else if (current.next.data >= node.data) {
                    node.next = current.next;
                    current.next = node;
                    size++;
                    return;
                }
                // 그게 아니라면
                current = current.next;
            } else if (current.data >= node.data) {
                //위에서 작거나 같은 경우를 따져주었으므로 이곳에 들어오는 경우는 node가 head가 되는 경우이다.
                node.next = current;
                tail.next = node;
                size++;
                return;
            }
        }
    }

---

delete method

삭제할 때의 경우를 떠올려보았다.

case 0 : 리스트가 비어있는 경우

case 1 : 원소가 하나만 있는 경우

case 2 : 원소가 둘 이상인 경우

case 2-1 : 삭제하려는 원소가 첫 노드(head)인 경우

case 2-2 : 삭제하려는 원소가 중간에 있는 경우

case 2-3 : 삭제하려는 원소가 끝 노드(tail)인 경우

---

case2-2와 2-3은 동시에 처리했다. 선형 탐색으로 원하는 데이터를 head부터 찾기 때문에 아래와 같은 코드도 통한다.

다만, 이코드는 시간복잡도가 O(n)일 될 뿐만 아니라 원형 연결 리스트의 장점을 살리지 못한다.

public Node delete(Node target) {
        //case0 빈 리스트
        if (size == 0) {
            System.out.println("[This list is already empty]");
            return null;
        }
        //case1 원소가 하나만 존재
        else if (size == 1 && target.data == tail.data) {
            size--;
            tail = null;
            return target;
        }

        //case2 원소가 둘 이상 존재
        else {
            Node current = tail.next;
            //case2-1 삭제하려는 노드가 head인 경우
            if (target.data == tail.next.data) {
                tail.next = current.next;
                target.next = null;
                size--;
                return target;
            }
            // case2-2,3 삭제하려는 노드가 중간 또는 끝에 있는 경우
            // 탐색을 통해서 target을 찾는다.
            for (int i=0; i<size; i++) {
                if (current.next.data == target.data) {
                    current.next = current.next.next;
                    target.next = null;
                    size--;
                    return target;
                }
                current = current.next;
            }
        }
        System.out.println("해당 노드를 찾을 수 없습니다.");
        return null;
    }

 

---

완성된 원형 연결 리스트

아래 더 보기를 누르면 확인할 수 있음.

 

package LinkedList;

public class CircularLinkedList {
    class Node{
        int data;
        Node next;
        Node(int data) {
            this.data = data;
        }
        void setNext(Node next) {
            this.next = next;
        }
    }
    CircularLinkedList() {
        // 필요없음
    }
    int size = 0;
    Node tail;
//    Node head; // -> tail.next와 같음. 그래서 굳이 필요없음

    //삽입
    // 오름차순으로 정렬되도록 삽입을 구현할 예정임. (tail이 가장 큰 수가 되도록)
    public void insert(int data) {
        insert(new Node(data));
    }
    public void insert(Node node) {
        if (size == 0) {
            // 리스트 안에 원소(노드)가 하나도 없는 경우
            tail = node;
            size++;
            return;
        }


        else if (size == 1){ //tail == head
            tail.next = node;
            node.next = tail;
            if (tail.data < node.data) {
                tail = node;
            }
            size++;
            return;
        }

        Node current = tail.next;
        for (int i=0; i<size; i++) {
            if (current.data < node.data) {
                // 다음 노드랑 new node랑 비교해야지
                // 그런데 다음 노드가 null, 즉 current가 tail인 경우는 어떡해?
                if (i == size-1) {
                    // current가 tail인 경우.
                    tail = node;
                    node.next = current.next;
                    current.next = node;
                    size++;
                    return;
                } else if (current.next.data >= node.data) {
                    node.next = current.next;
                    current.next = node;
                    size++;
                    return;
                }
                // 그게 아니라면
                current = current.next;
            } else if (current.data >= node.data) {
                //위에서 작거나 같은 경우를 따져주었으므로 이곳에 들어오는 경우는 node가 head가 되는 경우이다.
                node.next = current;
                tail.next = node;
                size++;
                return;
            }
        }
    }

    //삭제
    // 해당 data를 가진 노드를 삭제함.
    public void delete(int data) {
        Node node = new Node(data);
        delete(node);
    }
    // 노드의 data를 기준으로 노드를 삭제함.
    public Node delete(Node target) {
        //case0 빈 리스트
        if (size == 0) {
            System.out.println("[This list is already empty]");
            return null;
        }
        //case1 원소가 하나만 존재
        else if (size == 1 && target.data == tail.data) {
            size--;
            tail = null;
            return target;
        }

        //case2 원소가 둘 이상 존재
        else {
            Node current = tail.next;
            //case2-1 삭제하려는 노드가 head인 경우
            if (target.data == tail.next.data) {
                tail.next = current.next;
                target.next = null;
                size--;
                return target;
            }
            // case2-2,3 삭제하려는 노드가 중간 또는 끝에 있는 경우
            // 탐색을 통해서 target을 찾는다.
            for (int i=0; i<size; i++) {
                if (current.next.data == target.data) {
                    current.next = current.next.next;
                    target.next = null;
                    size--;
                    return target;
                }
                current = current.next;
            }
        }
        System.out.println("해당 노드를 찾을 수 없습니다.");
        return null;
    }

    //탐색
    public Node search(int index){
        Node node = tail.next; //==head
        int current = 0;
        while (current++ < index) {
            node = node.next;
        }
        return node;
    }

    //출력
    public void print() {
        Node node = tail.next;
//        System.out.println(tail.data+" 이거 맞냐");
        if (node == null) {
            return;
        }
        for (int i=0; i<size; i++) {
            System.out.printf("%d번째 노드 | %d\n", i+1, node.data);
            node = node.next;
        }
    }
}

 

바로 아래는 input txt이고, 코드를 통해서 새 data를 insertion할때와 head, tail, 중간을 삭제할 때 모두 제대로 동작하는 것을 확인했다.

2 6 5 5 1 5 3 8 10

package LinkedList;

import java.io.*;

public class MainLinkedList {
    public static void main(String[] args) throws IOException {
        CircularLinkedList cl;
        BufferedReader br = new BufferedReader(new FileReader("C:\\Users\\user\\IdeaProjects\\testProject\\src\\LinkedList\\input.txt"));

        String str;
        String[] stringlist;
        int count = 0;
        while ((str = br.readLine()) != null) {
            stringlist = str.split(" ");
            cl = new CircularLinkedList();
            for (String s : stringlist) {
                cl.insert(Integer.parseInt(s));
//                System.out.println("= = = = = = = = = = = = = = = =");
            }
            cl.print();
            cl.delete(1);
            cl.delete(5);
            cl.delete(10);
            cl.delete(100);
            System.out.println("= = = = = = = = = = = = = = = =");
            cl.print();
        }
    }
}