3:56

1. CircularDoublyLinkedList란?

• 단일 방향 연결 리스트와 다르게 어떤 노드를 한 번 지나도 반대 방향으로 돌아갈 수 있다.
• 마지막 노드의 next 값이 헤드 노드를 가리키고 헤드 노드의 prev 값이 마지막 노드를 가리킨다.

2. CircularDoublyLinkedList 구현하기

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

• 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 BidirectionalNode<E> {
	
	public BidirectionalNode<E> prev;
	public E item;
	public BidirectionalNode<E> next;
	
	public BidirectionalNode() {
		prev=next=null;
		item=null;
	}
	
	public BidirectionalNode (E newItem) {
		prev=next=null;
		item = newItem;
	}
	
	public BidirectionalNode (BidirectionalNode<E> prevNode, E newItem, BidirectionalNode<E> nextNode) {
		prev = prevNode;
		item = newItem;
		next = nextNode;
	}
}

• prev 변수에 해당 노드의 이전 노드를 저장한다.
• item 변수에 해당 노드에 입력할 데이터 값을 저장한다.
• next 변수에 해당 노드의 다음 노드를 저장한다.
• 첫 번째 생성자 - 클래스 호출 시 입력값이 없으면 prev, next, item 변수를 모두 null로 저장한다.
• 두 번째 생성자 - 클래스 호출 시 노드에 저장할 데이터를 입력받아 item 변수에 저장한다.
• 세 번째 생성자 - 클래스 호출 시 이전 노드, 저장할 값, 다음 노드를 입력받아 각각 prev, item, next 변수에 저장한다.

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) CircularDoublyLinkedList 클래스

- 필드 영역

//필드 영역
	private BidirectionalNode<E> head;
	private int size;

• 더미 헤드를 저장할 head 변수를 선언한다.
• 원형 양방향 연결 리스트의 원소 개수를 저장할 size 변수를 선언한다.

- 생성자 영역

//생성자 영역
	public CircularDoublyLinkedList() {
	head = new BidirectionalNode<>(null);
	head.next = head.prev = head;
	}

• head 변수에 item 값이 null인 노드를 입력합니다.
• 처음 원형 양방향 연결 리스트가 생성 되었을 때 head 노드는  next와 prev로 자기 자신을 참조합니다.

- 메서드 영역

<getNode 메서드 구현>

public BidirectionalNode<E> getNode (int i) {
		if (i>size||i<-1) throw new IllegalArgumentException();
		BidirectionalNode<E> currNode = head;
		
		if (i<size/2) {
			for (int j=0; j<=i; j++) {
				currNode=currNode.next;
			}
		} else {
				for (int j=size-1; j>=i; j--) {
					currNode=currNode.prev;
				}
			}
		return currNode;
	}

• 예외처리 - 입력받은 인덱스가 범위를 벗어나는 경우 (-1일 경우 더미헤드를 반환)
• currNode 변수에 head 노드를 저장한다.
• 입력 받은 인덱스가 앞쪽에 있으면 head 노드부터 입력 받은 인덱스까지 next로 이동하고 currNode를 리턴한다.
• 입력 받은 인덱스가 뒷쪽에 있으면 head 노드부터 입력 받은 인덱스까지 prev로 이동하고 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 변수에 입력 받은 인덱스의 이전 인덱스 노드를 저장한다.
• prevNode는 새로 들어올 노드의 이전 노드가 될 것이다.
• nextNode 변수에 입력 받은 인덱스의 노드를 저장한다.
• nextNode는 새로 들어올 노드의 다음 노드가 될 것이다.
• newNode 변수에 입력 받은 데이터를 item 값으로 하고 prevNode를 이전 노드, nextNode를 다음 노드로 하는 노드를 저장한다.
• prevNode의 다음 노드를 newNode로, nextNode의 이전 노드를 newNode로 갱신해준다.
• size 변수를 1 증가시킨다.

<append 메서드 구현>

@Override
	public void append(E x) {
		
		BidirectionalNode<E> prevNode = getNode(size-1);
		BidirectionalNode<E> newNode = new BidirectionalNode<>(prevNode,x,head);
		
		prevNode.next=newNode;
		head.prev=newNode;
		
		size++;
		
	}

• prevNode에 현재 원형 양방향 연결 리스트의 마지막 인덱스 노드를 저장한다.
• NewNode 변수에 prevNode를 이전 노드로 하고 head 노드를 다음 노드로 하며 입력 받은 데이터를 item 값으로 하는 노드를 저장한다.
• prevNode의 다음 노드를 newNode로 저장한다.
• head 노드의 이전 도르르 newNode로 저장한다.
• size 변수를 1 증가시킨다.

<remove 메서드 구현>

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

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

<removeItem 메서드 구현>

@Override
	public void removeItem(E x) {

		BidirectionalNode<E> currNode = head;
		
		
		for (int i=0; i<size; i++) {
			
			currNode=currNode.next;
			
			if (currNode.item.equals(x)) {
				
				currNode.prev.next=currNode.next;
				currNode.next.prev=currNode.prev;
				
				break;
			}
		}
		
		size--;
		
	}

• currNode 변수에 head 노드를 저장한다.
• 0부터 마지막 인덱스까지 순회하면서 입력받은 x와 item 값이 같은 노드가 있는지 검사한다.
• currNode와 x 값이 일치하면 해당 노드의 이전 노드가 next로 currNode를 생략하고 그 다음 노드를 참조하게 한다. 해당 노드의 다음 노드는 prev 값으로 currNode를 생략하고 그 이전 노드를 참조하게 한다.
• size 변수를 1 감소시킨다.

<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();
		getNode(i).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;
		head.next=head;
		head.prev=head;
		
	}

• size 변수를 0으로 초기화한다.
• head 노드가 next, prev로 자기 자신을 참조하게 한다.

<indexOf 메서드 구현>

@Override
	public int IndexOf(E x) {
		
		int idx = -1;
		BidirectionalNode<E> currNode = head;
		
		
		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() {
		
		BidirectionalNode<E> currNode = head;
		
		for (int i=0; i<size; i++) {
			currNode=currNode.next;
			System.out.print(currNode.item+" ");
		}
		
		System.out.println();
		
	}

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

- 전체 코드

public class CircularDoublyLinkedList<E> implements ListInterface<E>{
	
	//필드 영역
	private BidirectionalNode<E> head;
	private int size;
	
	//생성자 영역
	public CircularDoublyLinkedList() {
	head = new BidirectionalNode<>(null);
	head.next = head.prev = head;
	}
	
	//메서드 영역
	public BidirectionalNode<E> getNode (int i) {
		if (i>size||i<-1) throw new IllegalArgumentException();
		BidirectionalNode<E> currNode = head;
		
		if (i<size/2) {
			for (int j=0; j<=i; j++) {
				currNode=currNode.next;
			}
		} else {
				for (int j=size-1; j>=i; j--) {
					currNode=currNode.prev;
				}
			}
		return currNode;
	}
	
	@Override
	public void add(int i, E x) {
		if (i>size||i<0) throw new IllegalArgumentException();
		
		BidirectionalNode<E> prevNode = getNode(i-1);
		BidirectionalNode<E> nextNode = getNode(i);
		BidirectionalNode<E> newNode = new BidirectionalNode<>(prevNode,x,nextNode);
		
		prevNode.next=newNode;
		nextNode.prev=newNode;
		
		size++;
	}

	@Override
	public void append(E x) {
		
		BidirectionalNode<E> prevNode = getNode(size-1);
		BidirectionalNode<E> newNode = new BidirectionalNode<>(prevNode,x,head);
		
		prevNode.next=newNode;
		head.prev=newNode;
		
		size++;
		
	}

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

	@Override
	public void removeItem(E x) {

		BidirectionalNode<E> currNode = head;
		
		
		for (int i=0; i<size; i++) {
			
			currNode=currNode.next;
			
			if (currNode.item.equals(x)) {
				
				currNode.prev.next=currNode.next;
				currNode.next.prev=currNode.prev;
				
				break;
			}
		}
		
		size--;
		
	}

	@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();
		getNode(i).item=x;
		
	}

	@Override
	public int len() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

	@Override
	public void clear() {
		
		size=0;
		head.next=head;
		head.prev=head;
		
	}

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

	@Override
	public void printAll() {
		
		BidirectionalNode<E> currNode = head;
		
		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으로 바꾸고 출력합니다.
	
	}
}

<결과>

정상적으로 출력된다.