[C언어] 이중 연결 리스트를 이용한 노드 삽입, 삭제 연산 구현

오늘은 이중 연결 리스트를 구현해보겠습니다

이중 연결 리스트는 연결 리스트가 양쪽으로 연결되어있는 리스트로 노드를 탐색,삽입,삭제하는데 매우 유용한편입니다.

이번 포스팅에서는 리스트의 특징을 적극적으로 할용하여 구현해보겠습니다.

실행 결과

---

 

구현 코드

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

typedef struct listNode {
	struct listNode* llink;
	char data[4];
	struct listNode* rlink;
}listNode;

typedef struct {
	listNode* head;
}linkedList_h;

linkedList_h* createLinkedList_h(void) {
	linkedList_h* DL;
	DL = (linkedList_h*)malloc(sizeof(linkedList_h));
	DL->head = NULL;
	return DL;
}

void printList(linkedList_h* DL) {
	listNode* temp;
	printf(" DL=( ");
	temp = DL->head;
	do {
		printf("%s", temp->data);
		temp = temp->rlink; //오른쪽 방향으로 탐색
		if (temp != NULL) printf(" -> ");
	} while (temp != DL->head);
	printf(" NULL )");
}

void insertFirstNode(linkedList_h* DL, char* x) {
	listNode* newNode;
	listNode* last;
	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);

	if (DL->head == NULL) { //DL이 공백 리스트인 경우
		DL->head = newNode;
		newNode->llink = newNode;
		newNode->rlink = newNode;
	}
	else { //공백 리스트가 아닌 경우
		last = DL->head->llink;
		newNode->rlink = DL->head;
		newNode->llink = last;
		last->rlink = newNode;
	}
}

void insertMiddleNode(linkedList_h* DL, listNode* pre, char* x) {
	listNode* newNode;
	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);
	
	pre->rlink->llink = newNode;
	newNode->rlink = pre->rlink;
	newNode->llink = pre;
	pre->rlink = newNode;
}

void insertLastNode(linkedList_h* DL, char* x) {
	listNode* newNode;
	listNode* last;
	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);

	last = DL->head->llink;
	newNode->rlink = last->rlink;
	newNode->llink = last;
	last->rlink = newNode;
	DL->head->llink = newNode;
}

void deleteNode(linkedList_h* DL, listNode* old) {
	old->llink->rlink = old->rlink;
	old->rlink->llink = old->llink;
	if (DL->head == old) { //old 노드가 첫 노드인 경우
		DL->head = old->rlink;
	}
	free(old);
}

listNode* searchNode(linkedList_h* DL, char* x) {
	listNode* temp;
	temp = DL->head;
	do {
		if (!strcmp(temp->data, x)) {
			return temp;			
		}
		else {
			temp = temp->rlink;
		}
	} while (temp != DL->head);
}

void main() {
	linkedList_h* DL;
	listNode* p;

	DL = createLinkedList_h();
	printf("\n 이중 연결 리스트 생성하기\n");

	printf("\n 제일 앞 노드에 [월]노드 삽입하기\n");
	insertFirstNode(DL, "월");
	printList(DL);

	printf("\n\n 가장 마지막 노드에 [금]노드 삽입하기\n");
	insertLastNode(DL, "금");
	printList(DL);

	printf("\n\n 가장 마지막 노드에 [일]노드 삽입하기\n");
	insertLastNode(DL, "일");
	printList(DL);

	printf("\n\n [월]노드 뒤에 [화]노드 삽입하기\n");
	p = searchNode(DL, "월");
	insertMiddleNode(DL, p, "화");
	printList(DL);

	printf("\n\n [화]노드 뒤에 [수]노드 삽입하기\n");
	p = searchNode(DL, "화");
	insertMiddleNode(DL, p, "수");
	printList(DL);

	printf("\n\n [수]노드 뒤에 [목]노드 삽입하기\n");
	p = searchNode(DL, "수");
	insertMiddleNode(DL, p, "목");
	printList(DL);

	printf("\n\n [금]노드 뒤에 [토]노드 삽입하기\n");
	p = searchNode(DL, "금");
	insertMiddleNode(DL, p, "토");
	printList(DL);

	printf("\n\n [수]노드 삭제하기\n");
	p = searchNode(DL, "수");
	deleteNode(DL, p);
	printList(DL);

	printf("\n\n [월]노드 삭제하기\n");
	p = searchNode(DL, "월");
	deleteNode(DL, p);
	printList(DL);
	
	printf("\n\n [금]노드 삭제하기\n");
	p = searchNode(DL, "금");
	deleteNode(DL, p);
	printList(DL);

	printf("\n\n [일]노드 삭제하기\n");
	p = searchNode(DL, "일");
	deleteNode(DL, p);
	printList(DL);
}