[자료구조] 04. 원형 연결 리스트

원형 연결 리스트는 마지막 노드의 다음 노드가 첫 노드로 연결된 단순 연결 리스트이다.

마지막 노드의 레퍼런스가 저장된 last 가, head 가 되기도 한다.

한쪽 방향으로만 연결된 단순 연결 리스트로 구현되기 때문에, 반대 방향으로 노드를 방문하기는 쉽지 않다.

여러 사람이 차례로 돌아가며 진행되는 게임이나, 컴퓨터에서 cpu 시간을 분할하여 작업을 할당하는 운영체제 등에도 사용된다.

또는 이항 힙, 피보나치 힙과 같은 우선순위 큐를 구현할 때 사용되기도 한다.

 

노드 및 생성자 등의 경우는 단순 연결 리스트와 동일하다.

public class Node<E>
{
	private E value;
	protected Node<E> next;
	
	public Node(E value, Node<E> next)
	{
		this.value = value;
		this.next = next;
	}
	
	public E getValue() { return value; }
	public Node<E> getNext() { return next; }
	public void setValue(E value) { this.value = value; }
	public void setNext(Node<E> next) { this.next = next; }
}

 

삽입 연산

리스트가 비어있을 때와 아닐 때를 구분해준다. 비어 있다면 tail 자기 자신이 스스로를 가리키게 이어준다.

public void insert(E item)
{
	Node<E> newNode = new Node<E>(item, null);
	if(tail == null)
	{
		newNode.setNext(newNode);
		tail = newNode;
	}
	else
	{
		newNode.setNext(tail.getNext());
		tail.setNext(newNode);
	}
	size++;
}

 

삭제 연산

역시 마찬가지로 리스트가 비었을 때를 구분한다. 삭제한 노드를 반환해준다.

public Node<E> delete()
{
	if(size == 0) throw new NoSuchElementException();
	Node<E> temp = tail.getNext();
	if(temp == tail) tail = null;
	else
	{
		tail.setNext(temp.getNext());
		temp.setNext(null);
	}
	size--;
	return temp;
}

 

수행시간

삽입이나 삭제 연산은 다른 연결리스트들과 마찬가지로 O(1) 의 시간에 수행된다.

탐색 연산 역시 tail 부터 순차적으로 접근해야 하기 때문에 O(N) 이다.