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

Fekim·2022년 1월 7일

자료구조

목록 보기

2/7

원형 연결리스트 (Circular linked list)

원형 연결리스트는 리스트의 마지막 노드가 첫번째 노드를 가리키게 하여 리스트를 원형으로 만든 연결리스트이다.

삽입 연산

마지막 노드의 링크를 첫번째 노드로 연결하는 부부만 제외하고는 단순 연결리스트에서의 연산과 같다.

마지막 노드 삽입 알고리즘

public void insertLastNode(String str)
{
	ListNode newNode = new ListNode(str);
	
	if(CL != null)
	{
		CL = newNode;		 
		newNode.link = CL;	
	}
	else
	{
		ListNode temp = new ListNode();
		temp = CL;
		while(temp.link != CL)
		{
			temp = temp.link;	 
		}
		newNode.link = temp.link;		
		temp.link = newNode;		
		}
	}

1. temp 노드를 생성한다.
2. temp 노드에 CL노드를 대입후, temp 노드를 한 노드씩 이동하여 CL노드 직전 노드에 도달시킨다.
3. 새로운 노드를 CL노드와 연결시킨다.
4. 새로운 노드와 temp 노드를 연결시킨다.

첫번째 노드 삽입 알고리즘

public void insertFirstNode(String str)
{
	ListNode newNode = new ListNode(str);
	if(CL == null)
	{	
		CL = newNode;
	}
	else
	{
		ListNode temp = CL;
		while(temp.link != CL)
		{
			temp = temp.link;
		}
		newNode.link = temp.link;
		temp.link = newNode;
		CL = newNode;
	}
}

1. temp 노드를 생성한다.
2. temp 노드에 CL노드를 대입후, temp 노드를 한 노드씩 이동하여 CL노드 직전 노드에 도달시킨다.
3. 새로운 노드를 CL노드와 연결시킨후, temp 노드를 새로운 노드와 연결시킨다.
4. 모든 노드는 이어졌고, 새로운 노드를 CL노드로 만들어, 첫 노드로 변경한다.

중간 노드 삽입 알고리즘

선형 연결리스트와 알고리즘이 동일하다.단순 연결리스트의 중간 노드 삽입 알고리즘 참조.

삭제 연산

마지막 노드 삭제 알고리즘

public void deleteLastNode()
{
	if(CL == null)
		return ;
	else
	{
		ListNode prev = CL;
		ListNode temp = CL.link;
		while(temp.link != CL)
		{
			prev = temp;
			temp = temp.link;
		}
		prev.link = temp.link;
	}
}

1) 삭제될 노드 temp, 그 뒤 노드 prev를 생성한다.
2) prev노드를 CL노드에, prev 다음 노드에 temp노드를 배치한다.
3) temp 노드를 CL노드 직전까지 가도록 순회시킨다.
4) prev노드를 CL노드에 연결시킨다.

첫번째 노드 삭제 알고리즘

void deleteFirstNode()
{
	if(CL == null)
		return ;
	else
	{
		ListNode temp = CL;
		while(temp.link != CL)
		{
			temp = temp.link;
		}
		ListNode old = temp.link;
		CL = old.link;
		temp.link = CL;
	}			
}

1) temp노드를 생성한다.
2) temp노드를 CL노드에 배치한다.
3) temp노드를 CL노드 직전노드까지 순회시킨다.
4) 삭제될노드 old노드를 생성한다.
5) old노드를 temp노드 앞에 배치한다.
6) CL노드를 old노드 앞에 배치한다.
7) temp노드를 CL에 연결시켜 old노드의 연결을 끊는다.
8) 최종적으로 old노드는 삭제된다.

중간 노드 삭제 알고리즘

void deleteMiddleNode(String str)
{
	if(CL == null)
		return ;
	else
	{
		ListNode prev = CL;
		ListNode temp = CL.link;
		while(temp.data != str)
		{
			prev = temp;
			temp = temp.link;
		}
		prev.link = temp.link;	
	}
}

1) 삭제될 노드 temp 노드와, 그 이전노드인 prev노드를 생성한다.
2) CL노드에 prev노드를 배치하고, 그 앞노드로 temp노드를 배치한다.
3) temp 노드를 삭제하려는 Object가 있는 노드까지 이동시킨다.
4) prev 노드를 원래 Object가 연결된 노드에 연결시킨다.

검색 알고리즘

ListNode searchNode(String str)
{
	if(CL == null)
		return null;
	else
	{
		ListNode temp = CL;
		while(temp.data != str)
		{	
			temp = temp.link;
		}
	return temp;
	}
}

출력 알고리즘

void printList()
	{
		if(CL == null)
			return ;
		else
		{
			ListNode temp = new ListNode();
			while(temp.link != CL)
			{
				System.out.println(temp.data);
				temp = temp.link;
			}
		}
	}