C언어 이중 연결 리스트

Source Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 이중 연결 리스트의 노드 구조를 구조체로 정의
typedef struct listNode
{
	char name[50]; // 이름 저장
	char phone[50];// 전화번호 저장

	struct listNode* llink; // 노드의 이전노드를 가리킴 (왼쪽 링크필드)
	struct listNode* rlink; // 노드의 다음노드를 가리킴 (오른쪽 링크필드)
} listNode;

// 리스트 시작을 나타내는 head 노드를 구조체로 정의
typedef struct
{
	listNode* head; // listNode구조체의 멤버로 구조체 포인터 변수 head 선언 
} linkedList_h;


// 공백 이중 연결 리스트를 생성하는 연산 (초기화)
//linkedList_h 형으로 반환, 생성만 하는 함수이므로 매개변수는 없다.
linkedList_h* createLinkedList_h(void)
{
	linkedList_h* L; //listNode_h의 포인터변수 L 선언 

	L = (linkedList_h*)malloc(sizeof(linkedList_h)); // 헤드 노드 할당
	L->head = NULL; // 공백 리스트이므로 NULL로 설정

	return L; //L 값 반환
}

//연결 리스트의 전체 메모리를 해제하는 연산 
//linkedList_h* L의 값을 불러온다. 해제만하는 연산이므로 반환값 없다.
void freeLinkedList_h(linkedList_h* L)
{
	listNode* p; //루프변수 리스트의 노드를 하나씩 옮겨가면서 다음노드를 가리킨다.

	while (L->head != NULL) //공백리스트가 아닐 경우
	{
		p = L->head; //p는 리스트의 첫번째 노드를 가리킨다.
		L->head = L->head->rlink; //p에 p의 다음노드를 저장하여서
		free(p);  //메모리 해제한다. (이것을 while로 반복)
	}
}


//listNode에 새로운 노드를 생성하는 함수
//listNode의 새노드에 a,b를 삽입하고 생성한 새 노드 주소를 반환한다.
listNode* createNode(char* a, char* b)
{
	listNode* newNode; //listNode의 포인터변수 newNode선언 

	newNode = (listNode*)malloc(sizeof(listNode)); //값을 삽입할 새 노드 할당

	strcpy(newNode->name, a); //newNode의 name 필드에 입력받아온 a값 저장  
	strcpy(newNode->phone, b);//newNode의 phone 필드에 입력받아온 b값 저장  

	newNode->llink = NULL; //링크값은 비어있으므로 NULL값으로 초기화
	newNode->rlink = NULL;

	return newNode; //생성한 새 노드 주소를 반환 
}


//노드 삽입하는 함수
//linkedList_h 연결리스트 L에 a,b를 삽입한다. 삽입만 하므로 반환값 없다.
void insertNode(linkedList_h* L, char* a, char* b)
{
	listNode* newNode, * pre; //newNode:새로운 노드 변수, pre 리스트 노드 변수
	int comp; //비교값을 위한 변수

	newNode = createNode(a, b); //newNode는 createNode함수를 호출하여 만든다.

	//새노드를 리스트에연결

	if (L->head == NULL) //공백리스트인경우
	{
		L->head = newNode;//새노드가 맨앞노드(리스트의 시작노드)가 된다.
	}


	else  //현재 리스트가 공백이 아닌 경우 
	{
		pre = L->head; //pre는 맨앞노드를 가리킨다. 

		comp = strcmp(pre->name, newNode->name); //pre의 name부분과  newNode의 name부분을 비교한다.

		if (comp == 0) 	// 이미 첫 번째 노드에 추가가 된 이름인 경우 (일치한다면 strcmp 값 0 반환하므로 comp==0사용)
		{
			printf("이미 추가된 이름입니다.\n");
			free(newNode); //이미 있는 값이므로 입력하지 않고 메모리 해제시킨다.
			return; //리턴값 없다.
		}

		else if (comp > 0) // 맨 앞쪽에 추가를 해야 하는 경우(불일치한다면 strcmp 값 1 반환하므로 comp>0사용)
		{
			newNode->rlink = L->head; //newNode의 rlink에 L->head 주소값을저장하여  L->head와 연결되게 한다.
			newNode->rlink->llink = newNode; //newNode의 다음노드의 llink에 newNode의 주소값을 저장하여 newNode와 연결되게 한다.
			L->head = newNode; // L->head에 newNode값을 저장한다. 새로운 L->head
		}

		else // 맨 앞에 추가하는 경우가 아닌 경우
		{

			// 순회를 하면서 원소를 추가할 곳을 찾는다.
			while (pre->rlink != NULL)
			{
				pre = pre->rlink;  //pre를 다음노드로 옮겨가며 순회할곳 찾는다.

				comp = strcmp(pre->name, newNode->name);  //pre의 name부분과  newNode의 name부분을 비교한다.

				if (comp == 0) // 이미 추가된 이름인 경우
				{
					printf("이미 추가된 이름입니다.\n");
					free(newNode);//이미 있는 값이므로 입력하지 않고 메모리 해제시킨다.
					return;//리턴값 없다.
				}
				if (comp > 0)
					break;
			}
			// 맨 마지막에 추가를 하는 경우가 아닌 경우
			//중간에 삽입하는 경우

			if (comp > 0)
			{
				pre = pre->llink;
			}
			//pre:삽입되는 newNode의 이전노드

			newNode->rlink = pre->rlink; //newNode의 rlink에 pre의 rlink가 가리키고 있는 주소값(newNode의 다음노드주소값)을 저장하여 newNode의 다음노드에 연결한다.
			newNode->llink = pre;  //newNode의 llink에 pre값을 저장하여 pre와 연결되게 한다.


			if (newNode->rlink != NULL)// newNode 다음에 노드가 있을 경우
			{
				newNode->rlink->llink = newNode; //newNode의 다음노드에 newNode의 주소값을 저장하여 서로 연결되게 한다.
			}
			newNode->llink->rlink = newNode;
		}
	}
}

// 노드를 삭제하는 함수
//linkedList_h* L에서 입력된 old값을 삭제한다.삭제만 이루어지므로 반환값은 없다.
void deleteNode(linkedList_h* L, listNode* old)
{
	if (L->head == NULL)
		return; // 공백 리스트인 경우, 삭제 연산 중단, 반환값 없음
	else if (old == NULL)
		return; // 삭제할 노드가 없는 경우, 삭제 연산 중단 , 반환값 없음

	// old가 맨 앞인 경우 
	if (L->head == old)
	{
		L->head = L->head->rlink; // 첫번째 노드일 경우 head를 교체한다 
		if (L->head != NULL)
			L->head->llink = NULL; //리스트 시작 포인터를 null로 설정.
	}
	// old가 맨 앞이 아닌 경우( old의 다음 노드가 존재하는 경우)
	else
	{
		//old의 이전노드(왼쪽) 연결
		old->llink->rlink = old->rlink; //old->llink->rlink에 old의 rlink를 넣어야한다.
										//old가 삭제될때 old의 이전노드 rlink에 old의 rlink가 가리키는 주소(old의 다음노드주소)를 저장해야 리스트가 연결이 된다.
		//old의 다음노드(오른쪽) 연결
		if (old->rlink != NULL) //old의 다음노드가 존재할때
		{
			old->rlink->llink = old->llink; //old->rlink->llink에  old->llink를 넣어야 한다.
											//old가 삭제될때 old의 다음노드 llink에 old의 llink가 가리키는 주소(old의 이전노드주소)를 저장해야 리스트가 연결이 된다.
		}
	}
	free(old); //삭제한 old의 메모리를 해제한다.
}

// 노드를 검색하는 함수
//linkedList_h* L에서 입력된 a값을 찾는다. 찾았다면 찾은 a의 listNode*에서의 주소값을 반환한다.
listNode* searchNode(linkedList_h* L, char* a)
{
	listNode* p;//루프변수 리스트의 노드를 하나씩 옮겨가면서 다음노드를 가리킨다

	p = L->head;//첫번째노드
	while (p != NULL)  //공백리스트가 아니라면 실행
	{
		if (strcmp(p->name, a) == 0)//p의 name의 값과 a에 입력된 값을 비교한다.0이면 일치한다는 것.
			return p; //찾는 이름이라면 p값 반환
		p = p->rlink; //if조건에 맞지 않다면 다음 노드로 옮겨간다.
	}

	return p;//찾은 p값 반환한다. 공백리스트에는 반환값이 없다.
}

// 주어진 링크드 리스트를 전부 출력하는 함수
 //L은 널아님 linkedList_h* L의 값을 불러와 출력한다. printf함수로 출력만하므로 반환값은 없다.
void printList(linkedList_h* L)
{
	listNode* p; //루프변수 리스트의 노드를 하나씩 옮겨가면서 다음노드를 가리킨다

	p = L->head; //p는 첫번째 노드를 가리킴

	if (p == NULL)  //p가 공백리스트인 경우
	{
		printf("저장된 값이 없다.\n\n");
	}
	while (p != NULL) //공백리스트가 아니라면 while문으로 반복하며 모두 출력한다.  
	{
		printf("이름 : %s 번호 : %s\n", p->name, p->phone); //리스트에 있는 이름과 번호를 출력한다.
		p = p->rlink;  //다음 노드로 옮겨간다.
	}
}


//main 함수
int main()
{
	linkedList_h* L; //헤드노드
	listNode* p; //리스트의 노드변수 


	L = createLinkedList_h(); //헤드노드 초기화 L->head가 NULL인 상태 (L은 NULL 아님)
	int num;//메뉴판 선택할때 쓰이는 정수형 변수
	char a[50], b[50]; //이름과 번호를 넣을 배열 50개의 전화번호부 저장 가능

	while (1) //무한반복
	{
		printf("**************menu*******************\n");
		printf("1.삽입 2.출력 3.삭제 4.검색 5.끝 \n*************************************\n");
		scanf("%d", &num); //num의 값을 받아온다.

		if (num == 5)
			break; //5를 누르면 끝

		switch (num)
		{
		case 1:
			printf("삽입할 이름과 번호를 입력하시오.\n");
			scanf(" %s %s", a, b);
			insertNode(L, a, b); //insertNode함수를 사용하여 리스트L에 scanf로 받아온 a,b를 삽입한다.
			break;
		case 2:
			printList(L);//printList함수를 사용하여 리스트L을 출력한다.
			break;
		case 3:
			printf("삭제할 이름을 입력하시오.\n");
			scanf(" %s", a);
			p = searchNode(L, a); //L에서 a가 가리키는 포인터가 p가 나오면 p를삭제 
								 //삭제할 이름을 찾아내야 하므로 리스트 노드 p에 searchNode함수를 사용하여 삭제할 값을 찾는다. 
			if (p) //찾는 이름이 맞다면 
				deleteNode(L, p); //deletNode함수를 이용해서 삭제한다.
			else
				printf("삭제할 이름이 없다.\n");
			break;
		case 4:
			printf("검색할 이름을 입력하시오.\n");
			scanf(" %s", a);
			p = searchNode(L, a); //searchNode함수를 사용하여 리스트L에서 scanf로 입력받은 a값을 찾는다
			if (p == NULL)
				printf("찾는 데이터가 없습니다.\n");
			else
				printf("[%s]를 찾았습니다. 번호: %s\n", p->name, p->phone);
			break;
		}

	}
	freeLinkedList_h(L); //리스트의 메모리를 해제한다.
	return 0;
}

 

실행 결과