[Java] 원형 연결 리스트(CircularLinkedList) 구현하기

1. CircularLinkedList란?

원형 연결 리스트

• LinkedList는 리스트의 맨 끝에 데이터를 입력/삭제시 head부터 끝까지 이동해야 하므로 O(n)의 시간이 든다.
• CircularLinkedList는 맨 끝의 노드가 헤드 노드를 참조하도록 하여 시간을 단축한다.
• tail에는 유효한 값이 들어갈 수 있지만 tail.next는 item에 null값을 유지한다.

2. CircularLinkedList 구현하기

구현할 내용은 아래와 같다.

• add (int i, E x) - i번째 인덱스에 원소 x를 입력한다.
• append (E x) - 배열 리스트의 끝에 원소 x를 입력한다.
• remove (int i) - i번째 원소를 삭제한다.
• removeItem (E x) - 배열 리스트에서 원소 x를 삭제한다. 중복 원소가 있을 경우 먼저 나오는 원소를 삭제한다.
• get (int i) - i번째 원소를 리턴한다.
• set (int i, E x) - i번째 인덱스의 원소를 x로 교체한다.
• len() - 배열 리스트의 원소 개수를 리턴한다.
• isEmpty() - 배열 리스트가 비었는지 여부를 boolean으로 리턴한다.
• clear() - 인덱스를 비운다.
• indexOf(E x) - 배열 리스트 원소 x의 인덱스를 리턴한다. 중복 원소가 있을 경우 먼저 나오는 원소 인덱스를 리턴한다.
• printAll() - 배열 리스트의 모든 원소를 리턴한다.

 

1) 노드 클래스

public class Node<E> {

	public E item;
	public Node<E> next;
	
	public Node (E newItem) {
		item = newItem;
		next = null;
	}
	
	public Node (E newItem, Node<E> nextNode) {
		item = newItem;
		next = nextNode;
	}
}

• item 변수에 데이터를 저장한다.
• next 변수에 다음 노드를 저장한다. next는 다음 노드의 위치를 가리키는 포인터가 된다.
• 첫 번째 생성자는 데이터를 입력받아 데이터를 item에 저장하고, 포인터 값은 null로 저장한다.
• 두 번째 생성자는 데이터와 다음 노드를 입력받아 데이터를 item에 저장하고, 포인터 값에 다음 노드를 저장한다.

2) 인터페이스

public interface ListInterface<E>{
	
	public void add(int i, E x); 
	
	public void append (E x); 
	
	public void remove (int i); 
	
	public void removeItem (E x); 
	
	public E get(int i); 
	
	public void set(int i, E x);
	
	public int len();
	
	public boolean isEmpty(); 
	
	public void clear(); 
	
	public int IndexOf (E x); 
    
	public void printAll ();
	
}

 

3) CircularLinkedList 클래스

- 필드 영역

	//필드 영역
	private Node<E> tail;
	private int size;

• tail 변수에 tail로 설정할 노드를 저장한다.
• size 변수에 원형 연결 리스트의 크기를 저장한다.

- 생성자 영역

	//생성자 영역
	public CircularLinkedList() {
		size = 0;
		tail = new Node(-1);
		tail.next=tail;
	}

• 초기 원형 연결 리스트의 크기는 0이다.
• 초기 tail의 저장 데이터는 -1이며, 다음 노드로 자기 자신을 참조한다.

-메서드 영역

<getNode 메서드 구현>

public Node<E> getNode (int i) {
		if (i>size||i<-1) throw new IllegalArgumentException();
		Node<E> currNode = tail.next; 
		for (int j=0; j<=i; j++) {
			currNode=currNode.next;
		}
		return currNode;
	}

• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우 ( -1일 경우 더미헤드를 반환)
• 변수 currNode에 head(tail.next) 노드를 저장한다.
• 입력받은 인덱스까지 for문으로 원형 연결 리스트를 순회한 뒤 currNode를 리턴한다.

<add 메서드 구현>

	@Override
	public void add(int i, E x) {
		if (i>size||i<0) throw new IllegalArgumentException();
		Node<E> prevNode = getNode(i-1);
		Node<E> currNode = new Node(x,prevNode.next);
		prevNode.next=currNode;
		
		if (i==size) {
			tail = currNode;
		}
		
		size++;
	}

• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우
• 변수 prevNode에 입력받은 인덱스 전 노드를 저장한다.
• 변수 currNode에 item이 x고 next로 prevNode의 다음 노드를 참조하는 새 노드를 만들어 저장한다.
• prevNode가 next로 currNode를 참조하게 한다.
• 만약 원형 연결 리스트의 끝부분에 currNode를 저장하는 것이라면 tail을 currNode로 교체한다.
• size 변수를 1 증가시킨다.

<append 메서드 구현>

	public void append(Object x) {
		Node<E> prevNode = tail;
		Node<E> newNode = new Node(x,prevNode.next);
		tail.next=newNode;
		tail = newNode;
		size++;
	}

• 변수 prevNode에 tail 노드를 저장한다. 마지막 자리에 덧붙일 것이므로 현재의 tail이 새로운 노드의 이전 노드가 된다.
• newNode에 item이 x고 tail.next(head)를 next로 참조하는 새 노드를 만든다. 
• 기존 tail노드가 next로 newNode를 참조하게 한다.
• newNode가 tail이 된다.
• size 변수를 1 증가시킨다.

<remove 메서드 구현 - 단일 연결 리스트와 동일>

	@Override
	public void remove(int i) {
		if (i>size-1||i<0) throw new IllegalArgumentException();
		Node<E> prevNode = getNode(i-1);
		prevNode.next=getNode(i+1);
		size--;
	}

• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우
• 변수 prevNode에 입력받은 인덱스의 이전 인덱스 노드를 저장한다.
• prevNode가 다음 노드로 i번째 노드를 생략하고 i+1번째 노드를 참조하게 한다.

<removeItem 메서드 구현>

	@Override
	public void removeItem(E x) {
		
		Node<E> currNode = tail.next;
		Node<E> prevNode;
		
		for (int i=0; i<size; i++) {
		
			prevNode = currNode;
			currNode = currNode.next;
			
			if(currNode.item.equals(x)) {
				prevNode.next=currNode.next;
				size--;
				return;
			}
			
		}
		
	}

• for문으로 연결 리스트를 순회한다.
• currNode의 데이터가 x와 일치하면 prevNode가 next값으로 currNode를 생략하고 currNode.next를 참조하게 한다.

<get, set, len, isEmpty 메서드 구현>

	@Override
	public E get(int i) {
		if (i>size-1||i<0) throw new IllegalArgumentException();
		return getNode(i).item;
	}
	
	@Override
	public void set(int i, E x) {
		if (i>size-1||i<0) throw new IllegalArgumentException();
		Node<E> currNode = getNode(i);
		currNode.item=x;
	}
	
	@Override
	public int len() {
		return size;
	}
	
	@Override
	public boolean isEmpty() {
		return (size==0);
	}

• get - 입력받은 인덱스에 해당하는 값을 리턴한다.
• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우
• set - 입력받은 인덱스에 해당하는 값을 입력받은 값으로 교체한다.
• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우
• len - size 변수를 리턴한다.
• isEmpty - size==0 여부를 리턴한다.

<clear 메서드 구현>

@Override
	public void clear() {
		size=0;
		tail=new Node(-1);
		tail.next=tail;
	}

• size 변수를 0으로 초기화한다.
• tail 변수를 item 값이 -1인 새 노드로 초기화한다.
• tail 변수가 다음 노드로 자기 자신을 참조하게 한다. (tail.next==head)

<IndexOf 메서드 구현>

@Override
	public int IndexOf(E x) {
		int idx=-1;
		
		Node<E> currNode = tail.next;
		
		for (int i=0; i<size; i++) {
			currNode=currNode.next;
			
			if (currNode.item.equals(x)) {
				idx=i;
				break;
			}
		}
		return idx;
	}

• for문으로 원형 연결 리스트를 순회하며 노드를 변수 currNode에 저장한다.
• currNode.item과 입력받은 x를 비교한다.
• currNode.item==x일때의 인덱스를 리턴한다.
• 만약 x와 같은 값이 없으면 -1를 리턴한다.

<printAll 메서드 구현>

	@Override
	public void printAll() {
		
		Node<E> currNode = tail.next;
		
		for (int i=0; i<size; i++) {
			currNode=currNode.next;
			System.out.print(currNode.item+" ");
		}
		
		System.out.println();
		
	}

• for문으로 원형 연결 리스트를 순회하며 노드를 변수 currNode에 저장한다.
• 매 순회마다 currNode.item을 출력한다.

 

cf) 개인적으로 tail, tail.next, head의 구분이 어려웠어서 따로 정리하였다.

처음 CircularLinkedList를 생성하면 이 상태이다. tail 노드가 있고 이 노드는 next로 자기 자신을 참조한다. 개념상 tail.next가 head이므로 tail==tail.next==head가 된다.

값 100을 append하면 위와 같은 상태가 된다. newNode가 기존 tail.next(=tail)를 참조하고, 기존 tail이 newNode를 참조하며 tail 자리에 newNode가 들어간다. 

값 200을 append하면 위와 같은 상태가 된다. newNode가 기존 tail.next을 참조하고, 기존 tail(100)이 newNode를 참조하며 tail자리에 newNode가 들어간다.

** 기존 tail.next는 head이므로 newNode는 항상 head를 참조하는 것이 된다.

 

- 전체 코드

public class CircularLinkedList<E> implements ListInterface<E> {


		//필드 영역
		private Node<E> tail;
		private int size;
		
		//생성자 영역
		public CircularLinkedList() {
			size = 0;
			tail = new Node(-1);
			tail.next=tail;
		}
		//메서드 영역
		
		public Node<E> getNode (int i) {
			if (i>size-1||i<-1) throw new IllegalArgumentException();
			Node<E> currNode = tail.next; 
			for (int j=0; j<=i; j++) {
				currNode=currNode.next;
			}
			return currNode;
		}
		
		@Override
		public void add(int i, E x) {
			if (i>size||i<0) throw new IllegalArgumentException();
			Node<E> prevNode = getNode(i-1);
			Node<E> currNode = new Node(x,prevNode.next);
			prevNode.next=currNode;
			
			if (i==size) {
				tail = currNode;
			}
			
			size++;
		}
		
		@Override
		public void append(E x) {
			Node<E> prevNode = tail;
			Node<E> newNode = new Node(x,prevNode.next);
			tail.next=newNode;
			tail = newNode;
			size++;
			
		}
		
		@Override
		public void remove(int i) {
			if (i>size-1||i<0) throw new IllegalArgumentException();
			Node<E> prevNode = getNode(i-1);
			prevNode.next=getNode(i+1);
			size--;
		}
		
		@Override
		public void removeItem(E x) {
			
			Node<E> currNode = tail.next;
			Node<E> prevNode;
			
			for (int i=0; i<size; i++) {
			
				prevNode = currNode;
				currNode = currNode.next;
				
				if(currNode.item.equals(x)) {
					prevNode.next=currNode.next;
					size--;
					return;
				}
				
			}
			
		}
		
		@Override
		public E get(int i) {
			if (i>size-1||i<0) throw new IllegalArgumentException();
			return getNode(i).item;
		}
		
		@Override
		public void set(int i, E x) {
			if (i>size-1||i<0) throw new IllegalArgumentException();
			Node<E> currNode = getNode(i);
			currNode.item=x;
		}
		
		@Override
		public int len() {
			return size;
		}
		
		@Override
		public boolean isEmpty() {
			return (size==0);
		}
		
		@Override
		public void clear() {
			size=0;
			tail= new Node(-1);
			tail.next=tail;
		}
		
		@Override
		public int IndexOf(E x) {
			int idx=-1;
			
			Node<E> currNode = tail.next;
			
			for (int i=0; i<size; i++) {
				currNode=currNode.next;
				
				if (currNode.item.equals(x)) {
					idx=i;
					break;
				}
			}
			return idx;
		}
		
		@Override
		public void printAll() {
			
			Node<E> currNode = tail.next;
			
			for (int i=0; i<size; i++) {
				currNode=currNode.next;
				System.out.print(currNode.item+" ");
			}
			
			System.out.println();
			
		}
	}

 

3) 결과 확인하기

<코드>

public class Test {
	public static void main(String[] args) {

	CircularLinkedList<Integer> lst = new CircularLinkedList<>();
	
	lst.add(0, 100);
	
	lst.add(1, 200);
	
	lst.add(2, 300);
	
	lst.append(400);
	
	lst.printAll();
	
	//100,200,300,400을 차례로 입력하고 출력합니다.
	
	lst.remove(0);
	
	lst.printAll();
	
	lst.removeItem(400);
	
	lst.printAll();
	
	//0번째 인덱스의 값과 내용물이 400인 값을 삭제하고 출력합니다.
	
	lst.IndexOf(300);
	
	//300의 인덱스를 출력합니다.
	
	System.out.println(lst.isEmpty());
	System.out.println(lst.len());
	
	//lst가 비었는지 여부와 lst의 길이를 출력합니다.
	
	System.out.println(lst.get(0));
	
	//인덱스 0의 값을 출력합니다.
	
	lst.set(0, 1000);
	
	lst.printAll();
	
	//인덱스 0의 값을 1000으로 바꾸고 출력합니다.
	
	}
}

<결과>

정상적으로 출력된다.