5. 연결 리스트 3

5-1. 원형 연결 리스트

 

* 원형 연결 리스트의 이해

원형 연결 리스트는 연결 리스트의 마지막 노드가 NULL을 가리키는 것이 아니라 첫 번째 노드를 가리킨다. 원형 연결 리스트에서 head 대신 tail을 사용하면 tail->next가 head이므로 연결 리스트의 머리와 꼬리 모두에 새로운 노드를 쉽게 추가할 수 있다.

원형 연결 리스트

* 원형 연결 리스트의 구현

#define TRUE 1
#define FALSE 0

typedef int LData;
typedef struct _node {
	LData data;
	struct _node* next;
}Node;
typedef struct _CLinkedList {
	Node* tail;
	Node* cur;
	Node* before;
	int numOfData;
}CList;
typedef CList List;

void LInit(List* plist) {
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}

void LInsertFront(List* plist, LData data) { // 머리에 노드를 추가
	Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
	newNode->data = data; // 새 노드에 데이터 저장
	if (plist->tail == NULL) { // 첫 번째 노드라면
		plist->tail = newNode; // tail이 새 노드를 가리키게 함
		newNode->next = newNode; // 새 노드가 자신을 가리키게 함
	}
	else { // 두 번째 이후
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
	}
	(plist->numOfData)++;
}

void LInsert(List* plist, LData data) { // 꼬리에 노드를 추가
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	if (plist->tail == NULL) { // LInsertFront와 공통
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else { 
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
		plist->tail = newNode;
	}
	(plist->numOfData)++;
}

int LFirst(List* plist, LData* pdata) {
	if (plist->tail == NULL)
		return FALSE;
	plist->before = plist->tail; // before가 꼬리를 가리키게 함
	plist->cur = plist->tail->next; // cur이 머리를 가리키게 함
	*pdata = plist->cur->data;
	return TRUE;
}

int LNext(List* plist, LData* pdata) {
	if (plist->tail == NULL)
		return FALSE;
	plist->before = plist->cur; // before가 다음 노드를 가리키게 함
	plist->cur = plist->cur->next; // cur이 다음 노드를 가라키게 함
	*pdata = plist->cur->data;
	return TRUE;
}

LData LRemove(List* plist) {
	Node* rpos = plist->cur;
	LData rdata = rpos->data;
	if (rpos == plist->tail) { // 삭제 대상이 tail이면
		if (plist->tail = plist->tail->next) // 그리고 마지막 남은 노드이면
			plist->tail = NULL;
		else
			plist->tail = plist->before;
	}
	plist->before->next = plist->cur->next;
	plist->cur = plist->tail->next;
	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

int LCount(List* plist) {
	return plist->numOfData;
}

 

5-2. 양방향 연결 리스트

 

* 양방향 연결 리스트의 이해

양방향 연결 리스트는 하나의 노드가 자신의 왼쪽과 오른쪽 노드를 동시에 가리키는 구조이다.

양방향 연결 리스트

* 더미 노드 기반의 양방향 연결 리스트의 구현

#define TRUE 1
#define FALSE 0

typedef int LData;
typedef struct _node {
	LData data;
	struct _node* next; // 오른쪽 노드를 가리키는 포인터 변수
	struct _node* prev; // 왼쪽 노드를 가리크는 포인터 변수
}Node;
typedef struct _dbLinkedList {
	Node* head;
	Node* tail; 
	Node* cur;
	int numOfData;
}DBLinkedList;
typedef DBLinkedList List;

void ListInit(List* plist)
{
	plist->head = (Node*)malloc(sizeof(Node));
	plist->tail = (Node*)malloc(sizeof(Node));
	plist->head->prev = NULL;
	plist->head->next = plist->tail;
	plist->tail->next = NULL;
	plist->tail->prev = plist->head;
	plist->numOfData = 0;
}

void LInsert(List* plist, LData data) // 꼬리에 노드를 추가함
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->prev = plist->tail->prev; 
	plist->tail->prev->next = newNode;
	newNode->next = plist->tail;
	plist->tail->prev = newNode;
	(plist->numOfData)++;
}

int LFirst(List* plist, LData* pdata)
{
	if (plist->head->next == plist->tail)
		return FALSE;
	plist->cur = plist->head->next;
	*pdata = plist->cur->data;
	return TRUE;
}

int LNext(List* plist, LData* pdata)
{
	if (plist->cur->next == plist->tail)
		return FALSE;
	plist->cur = plist->cur->next;
	*pdata = plist->cur->data;
	return TRUE;
}

int LPrevious(List* plist, LData* pdata) { 
	if (plist->cur->prev == plist->head)
		return FALSE;
	plist->cur = plist->cur->prev;
	*pdata = plist->cur->data;
	return TRUE;
}

LData LRemove(List* plist)
{
	Node* rpos = plist->cur;
	LData rdata = rpos->data;
	plist->cur->prev->next = plist->cur->next;
	plist->cur->next->prev = plist->cur->prev;
	plist->cur = plist->cur->prev;
	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

int LCount(List * plist)
{
	return plist->numOfData;
}