[Computer Science] 원형연결리스트

• 마지막 노드와 첫번째 노드가 연결되어 링크를 따라 순회하면 이전 노드에 접근 가능
• 원형 연결 리스트는 마지막에 노드를 삽입하는 것이 곧 리스트의 첫번째에 노드를 삽입하는 것과 같은 의미를 가진다.

import java.util.Scanner;

public class CircularLinkedList {
	class Node {
		private int data;
		private Node next;

		public Node() {
			this.data = 0;
			this.next = null;
		}

		public Node(int data) {
			this.data = data;
			this.next = null;
		}

		public int getData() {
			return this.data;
		}

		public void setNext(Node node) {
			this.next = node;
		}

		public Node getNext() {
			return this.next;
		}
	}

	private Node tail;

	public CircularLinkedList() { // init
		tail = null;
	}

	// 삽입
	public void insertFront(int data) { // list의 앞에 삽입
		Node newNode = new Node(data); // 새로운 노드 생성

		if (tail == null) { // list가 비어있으면
			tail = newNode;
			newNode.setNext(newNode);
		} else { // list에 노드가 있으면
			newNode.setNext(tail.getNext()); // newNode.next = tail.next(첫노드)
			tail.setNext(newNode); // tail.next는 새로운 노드를 가리킨다
		}
	}

	public void insertLast(int data) { // list의 뒤에 삽입
		Node newNode = new Node(data); // 새로운 노드 생성

		if (tail == null) { // list가 비어있으면
			tail = newNode;
			newNode.setNext(newNode);
		} else { // list에 노드가 있으면
			newNode.setNext(tail.getNext()); // newNode.next = tail.next(첫노드)
			tail.setNext(newNode); // tail.next는 새로운 노드를 가리킨다
			tail = newNode; // newNode가 tail이 된다
		}
	}



	// 삭제
	public boolean deleteFront() { // list의 첫 노드 삭제
		if (tail == null) { // list가 비어있으면
			System.out.println("   No Data.");
			return false;
		} else { // list가 안 비어있으면
			Node delNode = tail.getNext(); // 삭제할 노드(첫 노드)

			if (delNode == tail) // 삭제할 노드가 마지막 노드일 때 (노드가 하나일 때)
				tail = null;
			else // 리스트에 2개 이상 노드가 있을 때
				tail.setNext(tail.getNext().getNext());
			return true;
		}
	}
}