연습문제 05. 2 더미 노드 기반의 양방향 연결 리스트의 구현

이번 연습문제에서는 양방향 연결 리스트의 완전한 구현을 요구합니다. 이유는 앞서 구현한 양방향 연결 리스트를 모델로 하여 조금만 수정하고 조금만 보태면 완성할 수 있기 때문입니다.

 

더미 노드 기반의 양방향 연결 리스트의 특징은 다음과 같습니다.

• 양방향 연결 리스트다.
• 더미 노드가 리스트의 앞과 뒤에 각각 존재한다.
• 포인터 변수 head와 tail이 있어서 리스트의 앞과 뒤를 각각 가리킨다.

 

이 경우 꼬리에도 더미 노드가 존재함에 유의합니다. 그리고 구현 범위를 제한한다는 의미에서 헤더 파일의 일부를 제공합니다. 즉, 아래에서 보이는 구조체의 함수를 기반으로 양방향 연결 리스트를 구현하면 됩니다.

typedef struct Node
{
	Data 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);
void LInsert(List* plist, Data data);
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
Data LRemove(List* plist);
int LCount(List* plist);

앞서 구현한 양방향 연결 리스트에서는 새 노드를 머리에 추가했습니다. 따라서 이번에는 새 노드를 꼬리에 추가하는 방식으로 LInsert 함수를 구현하기로 합니다. 그리고 LRemove 함수의 선언이 추가되었는데, 이 함수의 기능은 앞서 수차례 경험했으니 별도의 설명이 필요하진 않을 것입니다. 그리고 프로그램을 완성한 다음에는 머리에 있는 더미 노드와 꼬리에 있는 더미 노드에 각각 어떠한 의미가 있는지 생각해보기 바랍니다. 

---

제가 작성한 코드는 아래의 '더보기'를 클릭하여 확인할 수 있습니다.

혹시 이해가 가지 않거나 추가 설명이 필요하다면 언제든지 물어보길 바랍니다.

//DBLinkedList.h 헤더 파일로 저장
#ifndef DB_LINKEDLIST_G
#define DB_LINKEDLIST_G

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct Node
{
	Data 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);
void LInsert(List* plist, Data data);
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
Data LRemove(List* plist);
int LCount(List* plist);

#endif

//DBLinkedList.c 소스 파일로 저장
#include "DBLinkedList.h"
#include <stdio.h>
#include <stdlib.h>

void ListInit(List* plist)
{
	plist->head = (Node*)malloc(sizeof(Node));
	plist->tail = (Node*)malloc(sizeof(Node));
	if (plist->head == NULL || plist->tail == NULL) exit(1);

	plist->head->next = plist->tail;
	plist->head->prev = NULL;
	plist->tail->next = NULL;
	plist->tail->prev = plist->head;

	plist->cur = NULL;
	plist->numOfData = 0;
}

void LInsert(List* plist, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL) exit(1);

	newNode->data = data;

	newNode->next = plist->tail;
	newNode->prev = plist->tail->prev;
	plist->tail->prev->next = newNode;
	plist->tail->prev = newNode;

	plist->numOfData++;
}

int LFirst(List* plist, Data* pdata)
{
	if (plist->head->next == plist->tail) return FALSE;

	plist->cur = plist->head->next;

	*pdata = plist->cur->data;
	return TRUE;
}

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

	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}

Data LRemove(List* plist)
{
	Node* delNode = plist->cur;
	Data delData = delNode->data;

	plist->cur = delNode->prev;
	plist->cur->next = delNode->next;
	delNode->next->prev = plist->cur;

	printf("%d을(를) 삭제합니다.\n", delData);
	free(delNode);
}

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

//main.c 소스 파일로 저장
#include "DBLinkedList.h"
#include <stdio.h>

int main(void)
{
	List list;
	int data;
	ListInit(&list);

	//8개 데이터 저장
	LInsert(&list, 1);
	LInsert(&list, 2);
	LInsert(&list, 3);
	LInsert(&list, 4);
	LInsert(&list, 5);
	LInsert(&list, 6);
	LInsert(&list, 7);
	LInsert(&list, 8);

	//저장된 데이터 출력
	if (LFirst(&list, &data))
	{
		printf("%d ", data);

		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}
	}
	printf("\n\n");

	//2의 배수 모두 삭제
	if (LFirst(&list, &data))
	{
		if (data % 2 == 0) LRemove(&list);
		while (LNext(&list, &data))
		{
			if (data % 2 == 0) LRemove(&list);
		}
	}
	printf("\n");

	//저장된 데이터 출력
	if (LFirst(&list, &data))
	{
		printf("%d ", data);

		while (LNext(&list, &data))
		{
			printf("%d ", data);
		}
	}
	printf("\n\n");

	//모든 데이터 삭제
	if (LFirst(&list, &data))
	{
		LRemove(&list);
		while (LNext(&list, &data))
		{
			LRemove(&list);
		}
	}
	printf("\n");
}

/*
실행결과

1 2 3 4 5 6 7 8

2을(를) 삭제합니다.
4을(를) 삭제합니다.
6을(를) 삭제합니다.
8을(를) 삭제합니다.

1 3 5 7

1을(를) 삭제합니다.
3을(를) 삭제합니다.
5을(를) 삭제합니다.
7을(를) 삭제합니다.

*/