원형 연결리스트(CircularLinkedList)직접 구현

1. 원형 연결리스트(CircularLinkedList)란?

모든 노드가 원의 형태를 이루면서 연결되어 있는 리스트이다.

단방향 연결리스트처럼 머리와 꼬리를 가리키는 변수를 각각 두지 않아도, 하나의 변수만으로 머

리 또는 꼬리에 노드를 간단히 추가할 수 있다.  

위 그림을 보면 head변수없이 tail 변수만으로 new node를 마지막 꼬리에 추가하였고, 

new node는 다시 맨 앞의 노드를 가리키면서 원의 형태로 연결되어있다.

원형 연결리스트의 노드의 삽입, 조회, 삭제를 구현해보겠다.

2. 원형 연결리스트의 구현

package CircularLinkedList;
public class CircularLinkedListMain {
    static CircularLinkedList numbers = new CircularLinkedList();
    // 원형 연결 리스트의 생성
    static Object first;//데이터 조회를 위한 변수 선언1
    static Object next;//데이터 조회를 위한 변수 선언2
     
    public static void main(String[] args) {
        
         numbers.addFirst(20);//맨 앞에 추가 
         numbers.addFirst(10);
             System.out.println(numbers);//출력
         numbers.addLast(30);//맨 뒤에 추가
         numbers.addLast(40);
             System.out.println(numbers);
              
             getAllNode();//전체 데이터 조회
             
             remove(20);//리스트에서 20 삭제 
             
             getAllNode();
             
         System.out.println(numbers);
    }
    
    public static void getAllNode() {//전체 데이터 조회
         first = numbers.getFirst();
          
          if((int)first != 1) {
              System.out.println(first);//맨 앞 출력
              
              for(int i=0; i<numbers.size()-1; i++)
             {
                  next = numbers.getNext();//맨 앞 뒤로 쭉 출력
                  
                  if((int)next != 1) {
                      System.out.println(next);
                  }
             }
          }
     }
    
    public static void remove(int target) {//타겟에 해당하는 노드 삭제
        first = numbers.getFirst();
          
          if((int)first != 1) {
                  if((int)first == target) {//맨 앞의 데이터가 타겟이라면
                    numbers.remove();
                    return;//삭제되면 빠져나가자
                }
              for(int i=0; i<numbers.size()-1; i++)//전체 탐색
             {
                  next = numbers.getNext();
                  
                  if((int)next != 1) {
                      if((int)next == target) {//뒤의 값중에 타겟과 값이 일치하면
                          numbers.remove();//삭제 메소드 실행
                          return;//삭제되면 빠져나가자
                      }
                  }
             }
          }
    }
}

package CircularLinkedList;
public class CircularLinkedList {
   private Node tail;// 마지막 노드를 가리키는 필드,변수
   private Node cur;// 현재의 노드를 가리키는 변수
   private Node before;
   private Node temp;
   private int size = 0; //엘리먼트 갯수
   
   private class Node{
       
       private Object data;//데이터가 저장될 변수-실제 저장값
      
       private Node next;//다음 노드를 가리키는 변수,참조값
       
       public Node(Object input) {//객체생성 초기화
           this.data = input;
           this.next = null;//생성시는 미정
       }
       public String toString(){//노드의 값을 쉽게 출력위해
           return String.valueOf(this.data);
       }
   }
   public void addFirst(Object input){//머리에 추가
      
      Node newNode = new Node(input);//노드를 생성
       
      if(tail == null) 
      {
          tail = newNode;
          newNode.next = newNode;
      }
      else
      {
          newNode.next = tail.next;
          tail.next = newNode;
      }
       size++;
   }
   public void addLast(Object input){//꼬리에 추가
       if(size == 0){//리스트의 노드가 하나도 없다면 첫번째 노드를 추가하는 메소드를 사용.
           addFirst(input);
       } 
       else //기존 노드가 하나라도 있다면 
       {
               Node newNode = new Node(input);
           
            if(tail == null) 
            {
                tail = newNode;
                newNode.next = newNode;
            }
            else
            {
                newNode.next = tail.next;
                tail.next = newNode;
                tail = newNode;
            }
          
           size++;//엘리먼트 개수 1 증가
       }
   }
   public Object getFirst(){//첫번재 엘리먼트 값 조회
       if(tail == null)    // 저장된 노드가 없다면
            return 1;
 
        before = tail;
        cur = tail.next;
       return cur.data;
   }
   public Object getNext(){//다음 엘리먼트 값 조회
       if(tail == null)    // 저장된 노드가 없다면
            return 1;
 
        before = cur;
        cur = cur.next;
       return cur.data;
   }
  
   public String toString() {//리스트안에 데이터 전부 출력
       if(tail == null){//리스트에 데이터가 없다면
           return "[]";
       }       
       Node temp = tail.next;
       String str = "[";
       while(temp.next != tail.next){
           str += temp.data + ",";
           temp = temp.next;
       }
       str += temp.data;//마지막 노드를 출력결과에 포함
       return str+"]";
   }
   
   public Object remove(){
       temp = cur;
       Object returnData = temp.data;
       if(temp == tail) {// 삭제 대상을 tail이 가리킨다면
           if(tail == tail.next) // 그리고 마지막 남은 노드라면
               tail = null;
           else 
               tail = before;
       }
       before.next = cur.next;
       cur = before;
       size--;
       return returnData;
   }
   
   public int size(){//리스트가 가진 데이터의수
       return size;
   }
  }