C로 만드는 자료구조-원형 연결 리스트

컴퓨터 공학/자료구조 2020. 8. 22. 21:42

원형 연결 리스트(Circular Linked List)란?

 기본적인 구조는 단순 연결 리스트와 똑같은 구조지만 맨 마지막 노드의 링크가 NULL값인 단순 연결 리스트와 다르게 원형 연결 리스트에서 맨 마지막 노드의 링크는 맨 처음 노드를 가리킨다. 따라서 노드끼리 연결된 형태가 원형을 이루고 순환구조라는 점에서 차이가 있다.  

그림과 같이 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리킨다.

 이때 노드가 딱 1개 존재하는 경우가 생길 수도 있는데 이때 그 노드는 첫 번째 이자 마지막 노드이기 때문에 그 노드의 링크는 자기 자신을 가리키게 된다.

원형 리스트의 장점

 만약 연결 리스트 위에서 어떠한 위치에 존재하는 노드의 이전에 위치하는 노드를 탐색한다고 가정해보자 단순 연결 리스트에서 현재 노드의 인덱스를 구해야 하고 항상 맨 처음 노드부터 탐색을 해야 한다. 하지만 원형 연결 리스트에서는 순환구조이기 때문에 현재 위치에 있는 노드에서 링크를 따라 계속 따라가다 보면 이전 노드의 도달할 수 있을 것이다.
 
 이때 어떻게 하면 어떠한 노드가 이전 노드임을 알 수 있을까? 링크를 사용하면 매우 간단하게 알 수 있다. 이전 노드의 링크가 현재 노드를 가리키기 때문에 다음 조건을 만족할 것 이다.

#pPreNode: 이전 노드
#pNode: 현재 노드
pPreNode-> pLink==pNode

따라서 현재 노드에서 링크를 따라 계속 이동하다가 위 조건에 맞으면 이전 노드이고 아니면 링크를 타고 다음 노드로 이동하면 된다.
 원형 연결 리스트는 맨 마지막 노드가 맨 처음의 노드와 연결되어 있는 순환구조이기 때문에 현재 노드 이전에 있는 노드 탐색을 편리하다.

원형 연결 리스트 구현

  원형 연결 리스트의 구현은 단순 연결 리스트와 기본적인 구조는 똑같다. 하지만 맨 마지막 노드와 맨 처음 노드가 연결되어 있어야 하기 때문에 노드 추가/제거할 때 몇 가지 신경 써줘야 할 부분이 있다. 자세한 설명은 함수 구현 부분에서 하겠다.

소스 파일의 구성은 다음과 같다.

파일 이름

내용

Circularlinkedlist.h

구조체 및 함수 선언

Circularlinkedlist.cpp

함수 구현

CircularLinkedListMain.cpp

main 함수 실행

1.Circularlinkedlist.h

#pragma once

#include<iostream>
#define TRUE 1
#define FALSE 0
using namespace std;
typedef struct CircularListNode {
	int data;
	struct CircularListNode* pLink;
};
typedef struct CircularList {
	int currentElementCount;
	CircularListNode headerNode;
};

CircularList* createCircularList();//연결 리스트 생성
int addCLElement(CircularList* pList, int position, CircularListNode element);//리스트에 원하는 위치에 자료 추가
int removeCLElement(CircularList* pList, int position);// 리스트에서 해당위치에 존재하는 자료 제거
CircularListNode* getCLElement(CircularList* pList, int position);//리스트에서 해당위치에 존재하는 자료 반환

void clearCircularList(CircularList* pList);//리스트 비우기
int getcircularListLength(CircularList* pList);// 리스트 길이 반환
void deleteCircularList(CircularList* pList);// 리스트 삭제
void displayCircularList(CircularList* pList);// 리스트에 저장되어 있는 원소 출력

 기본적인 틀은 단순 연결 리스트와 똑같다.
-CircularListNode는 CircularList에 저장될 노드를 의미하며 자료(data)와 링크(pLink)로 구성되어 있다.
-CircularList는 실질적인 원형 연결 리스트를 의미하며 현재 저장 중인 원소의 개수(currentElementCount)와 리스트의 기능 구현을 쉽게 하기 위한 더미(Dummy) 노드인 헤더 노드(headerNode)로 구성되어 있다.
추가적으로 #define을 이용해 TURE은 1, FALSE는 0 값으로 정의해주었다.

2.CircularList.cpp

- createCircularList()

CircularList* createCircularList() {
	CircularList *pReturn = NULL;
	pReturn = new CircularList;
	if (pReturn != NULL) {
		memset(pReturn, 0, sizeof(CircularList));
	}
	else {
		cout << "오류, 메모리 할당 createLinkedList()\n" << endl;
		return NULL;
	}
	return pReturn;
}

단순 연결 리스트와 똑같은 형식이다. CircularList에 대해 메모리를 할당하고 값을 0으로 준다.

- addCLElement()

 앞서 말했듯이 원형 연결 리스트에서 노드 추가는 단순 연결 리스트보다 복잡하다. 단순 연결 리스트에서는 노드를 추가할 때 나오는 경우의 수가 하나밖에 없지만 원형 연결 리스트에서는 아래와 같이 3가지 경우가 있다.

1. 첫 번째 자리 노드 추가이고 공백 리스트인 경우

2. 첫 번째 자리 노드 추가이고 공백 리스트가 아닌 경우

3. 첫 번째 자리 노드 추가가 아닌 경우

 위 3가지 경우를 분류하기 위해서 아래 순서도와 같은 방법을 사용할 것이다.

 

1번-첫 번째 자리 노드 추가이고 공백 리스트인 경우

가장 간단한 경우이다. 노드 추가를 하고 헤더 노드(headerNode)와 새로운 노드(pNewNode)를 연결해주고 새로운 노드의 링크를 자기 자신과 연결시켜주면 된다. 원형 연결 리스트에서 노드가 1개이면 그 노드는 맨 처음이자 마지막인 노드이기 때문에 자기 자신과 연결시켜 주어야 한다.

pList->headerNode.pLink = pNewNode;
pNewNode->pLink = pNewNode;

2번-첫 번째 자리 노드 추가이고 공백 리스트가 아닌 경우

 첫 번째 자리 노드 추가이지만 공백 리스트가 아닌 경우에는 노드 추가 이전에 첫 번째 노드와 마지막 노드가 이미 존재한다. 따라서 새로운 노드(pNewNode)를 추가할 때 새로운 노드는 마지막 노드(pLastNode)의 다음 노드이고 기존에 있던 첫 번째 노드를 가리키면 된다. 추가적으로 헤더 노드와도 새로 연결해주어야 한다.

pList->headerNode.pLink = pNewNode;
pNewNode->pLink = pLastNode->pLink;
pLastNode->pLink = pNewNode;

 이때 마지막 노드를 찾기 위해서 마지막 노드의 다음 노드가 첫 번째 노드라는 특성을 이용한다.

while (pLastNode->pLink!= pList->headerNode.pLink) {
          pLastNode = pLastNode->pLink; 
}

3번-첫 번째 자리 노드 추가 아닌 경우

 단순 연결 리스트에서의 노드 추가와 똑같은 방식을 이용하다. 추가하려는 위치 인덱스(position)
이전에 위치한 노드(pPreNode)를 찾고 링크를 재설정해주면 된다. 

pNewNode->pLink = pPreNode->pLink;
pPreNode->pLink = pNewNode;

코드 구현은 다음과 같다.

int addCLElement(CircularList* pList, int position, CircularListNode element) {
	int ret = FALSE;
	CircularListNode* pNewNode = NULL;
	CircularListNode* pLastNode = NULL;
	CircularListNode* pPreNode = NULL;
	if (pList != NULL) {
		if (position >= 0 && position <= pList->currentElementCount) {
			pNewNode = new CircularListNode;
			if (pNewNode == NULL) {
				cout << "메모리 할당 오류  pNewNode" << endl;
				return ret;
			}
			*pNewNode = element;
			pNewNode->pLink = NULL;
			
			if (position == 0) {
				if (pList->currentElementCount == 0) {
					pList->headerNode.pLink = pNewNode;
					pNewNode->pLink = pNewNode;
				
				}
				else {
					pLastNode = pList->headerNode.pLink;
					while (pLastNode->pLink != pList->headerNode.pLink) {
						pLastNode = pLastNode->pLink;
					}
					pList->headerNode.pLink = pNewNode;
					pNewNode->pLink = pLastNode->pLink;
					pLastNode->pLink = pNewNode;
				}
			}
			else {
				pPreNode = pList->headerNode.pLink;
				for (int i = 0; i < position - 1; i++) {
					pPreNode = pPreNode->pLink;
				}
				pNewNode->pLink = pPreNode->pLink;
				pPreNode->pLink = pNewNode;
			}
			pList->currentElementCount++;
			ret = TRUE;
		}
		else {
			cout << "위치 인덱스 오류" << endl;
		}
	}
	return ret;
}//리스트에 원하는 위치에 자료 추가

- removeCLElement()

 노드 추가와 똑같이 노드 제거에서도 원형 연결 리스트에서 3가지 경우의 수가 존재한다.

1. 첫 번째 자리 노드이고 마지막 노드인 경우

2. 첫 번째 자리 노드이고 마지막 노드가 아닌 경우

3. 첫 번째 자리 노드가 아닌 경우

 위 3가지 경우를 분류하기 위해서 아래 순서도와 같은 방법을 사용할 것이다.

 

1번-첫 번째 자리 노드이고 마지막 노드인 경우

 가장 간단한 경우이다. 첫 번째 이자 마지막 노드인 경우는 리스트에 삭제하려는 노드(pDelNode) 하나만 존재하는 경우이다. 이때 노드를 삭제하고 헤더 노드(headerNode)의 링크만 NULL값으로 초기화해주면 된다.

delete pDelNode;
pList->headerNode.pLink = NULL;

2번-첫 번째 자리 노드이고 마지막 노드가 아닌 경우

 기본적으로 노드가 2개 이상 존재하기 때문에  첫 번째 노드(pDelNode)를 제거하고 나서 마지막 노드(pLastNode)와 제거 후 첫 번째가 될 노드(pDelNode->pLink)를 연결해줘야 한다. 또한 헤더 노드의 링크도 새로 연결해주어야 한다.

pLastNode->pLink = pDelNode->pLink;
pList->headerNode.pLink = pDelNode->pLink;
delete pDelNode;

3번-첫 번째 자리 노드가 아닌 경우

단순 연결 리스트에서의 노드 제거와 유사하다. 가 하려는 위치 인덱스(position) 이전에 위치한 노드(pPreNode)를 찾고 링크를 재설정해주면 된다. 

pDelNode = pPreNode->pLink;
pPreNode->pLink = pDelNode->pLink;
headerNode.pLink = pDelNode->pLink;
delete pDelNode;

코드 구현은 다음과 같다.

int removeCLElement(CircularList* pList, int position) {
	int ret = FALSE;
	CircularListNode* pDelNode = NULL;
	CircularListNode* pLastNode = NULL;
	CircularListNode* pPreNode = NULL;
	if (pList != NULL) {
		if (position >= 0 && position < pList->currentElementCount) {
			if (position == 0) {
				pDelNode = pList->headerNode.pLink;
				if (pList->currentElementCount == 1) {
					delete pDelNode;
					pList->headerNode.pLink = NULL;
				}
				else {
					pLastNode = pList->headerNode.pLink;
					while (pLastNode->pLink != pList->headerNode.pLink) {
						pLastNode = pLastNode->pLink;
					}
					pLastNode->pLink = pDelNode->pLink;
					pList->headerNode.pLink = pDelNode->pLink;
					delete pDelNode;
				}
			}
			else {
				pPreNode = &(pList->headerNode);
				for (int i = 0; i < position - 1; i++) {
					pPreNode = pPreNode->pLink;
				}
				pDelNode = pPreNode->pLink;
				pPreNode->pLink = pDelNode->pLink;
				pList->headerNode.pLink = pDelNode->pLink;
				delete pDelNode;
			}
			pList->currentElementCount--;
			ret = TRUE;
		}
		else {
			cout << "위치 인덱스 오류" << endl;
		}
	}
	return ret;
}// 리스트에서 해당위치에 존재하는 자료 제거

 

나머지 함수 구현 코드는 다음과 같다.

CircularListNode* getCLElement(CircularList* pList, int position) {
	CircularListNode* pNode = NULL;
	if (pList != NULL) {
		if (position >= 0 && position < pList->currentElementCount) {
			pNode = &(pList->headerNode);
			for (int i = 0; i <= position; i++) {
				pNode = pNode->pLink;
			}
		}
	}
	return pNode;
}//리스트에서 해당위치에 존재하는 자료 반환

void clearCircularList(CircularList* pList) {
	if (pList != NULL) {
		while (pList->currentElementCount > 0) {
			removeCLElement(pList, 0);
		}
	}
}//리스트 비우기
int getcircularListLength(CircularList* pList) {
	int ret = 0;
	if (pList != NULL) {
		ret = pList->currentElementCount;
	}
	return ret;
}// 리스트 길이 반환
void deleteCircularList(CircularList* pList) {
	if (pList != NULL) {
		clearCircularList(pList);
		free(pList);
	}
}// 리스트 삭제
void displayCircularList(CircularList* pList) {
	if (pList != NULL) {
		cout << "현재 원소의 개수: " << pList->currentElementCount << endl;
		for (int i = 0; i < pList->currentElementCount; i++) {
			cout << getCLElement(pList, i)->data << '\t';
		}
	}
	else {
		cout << "원소가 존재하지 않습니다." << endl;
	}
	cout << endl;

}

3.CircularLinkedListMain.cpp

메인 함수 실행 코드는 다음과 같다.

#include "stdafx.h"
#include"circularlist.h"

int main()
{
	CircularList *pList = NULL;
	CircularListNode* pNode = NULL;
	CircularListNode node;

	pList = createCircularList();

	if (pList != NULL) {
		node.data = 1;
		addCLElement(pList, 0, node);
	

		node.data = 3;
		addCLElement(pList, 1, node);
		

		node.data = 5;
		addCLElement(pList, 0, node);
		displayCircularList(pList);

		removeCLElement(pList, 0);
		displayCircularList(pList);

		deleteCircularList(pList);
	}


	return 0;
}

실행결과는 다음과 같다.

728x90
반응형
저작자표시 비영리

'컴퓨터 공학 > 자료구조' 카테고리의 다른 글

C로 만드는 자료구조- Stack이란?  (0) 2020.08.29
C로 만드는 자료구조-이중 연결 리스트  (0) 2020.08.22
C로 만드는 자료구조-연결 리스트  (0) 2020.08.16
C로 만드는 자료구조-배열 리스트  (0) 2020.08.16
C로 만드는 자료구조-List란?  (0) 2020.08.15
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 라이프코리아트위터 공유하기
    • shared
  • 카카오스토리 공유하기

티스토리툴바