7. 이중 연결 리스트를 이용하여 삽입, 삭제, 탐색, 조회 구현하기

6. 단순 연결 리스트 삽입, 탐색, 삭제, 역순 구현 (tistory.com)

6. 단순 연결 리스트 삽입, 탐색, 삭제, 역순 구현

(이전의 글에서 연결리스트를 상세하게 설명했기 때문에 이 글은 설명의 비중을 조금 낮춰서 진행하겠습니다)

이중 연결 리스트란?

이전 시간에 다룬 연결리스트의 경우
L(시작점) -> (값 / 링크) -> (값 / NULL)
위와 같은 형식으로 자료를 저장했습니다.

문제를 풀면서
연결리스트를 역순으로 지정하는 경우
혹은 바로 뒤에 있는 정보를 읽어오고 싶은 경우 많은 문제가 있었습니다.

그 문제를 해결하기 위한 2가지 방법 중 하나가
원형 연결 리스트로 끝노드가 처음노드를 가리키게 합니다.

이번에 만들 이중 연결 리스트는
하나의 노드가 두 개의 주소를 가리킵니다.
(이전값링크 / 값 / 다음값링크)
이렇게 한 개의 노드가 됩니다.

문제
이중연결리스트에서 다음 함수들을 구현하시오.
1. 이중 연결 리스트에서 삽입하는 연산을 수행하는 함수
2. 이중 연결 리스트에서 노드를 탐색하는 함수
3. 이중 연결 리스트에서 삭제 연산을 수행하는 함수

4. 그림처럼 리스트를 하나씩 조회할 수 있도록 구현해보시오.

사용자로 부터 값을 입력받는 것으로 진행하세요.

(이전 장과 비슷한 흐름으로 진행합니다.)

---

0. 들어가기 전

---

이중연결리스트의 뼈대를 구현해봅시다.

구조체로 노드를 표현해봅시다.

typedef struct Node {
	struct Node* leftLink;
	int value;
	struct Node* rightLink;
}; Node;

구조체에 대한 설명은 위의 내용과 동일합니다.
이전의 주소를 가리키는 leftLink
값
다음의 주소를 가리키는 rightLink

완성된 코드를 보면서 이중 연결리스트의 동작을 확인해보겠습니다.

#include<stdio.h>
#include<malloc.h>

// Node의 정보를 저장하는 구조체
typedef struct Node {
	struct Node* leftLink;
	int value;
	struct Node* rightLink;
}; Node;


// 순서대로 출력하는 함수
void printList(Node* ptr) {
	printf("value는 %d \n", ptr->value);
	if (ptr->rightLink != NULL) {
		printList(ptr->rightLink);
	}
}

// 역으로 출력하는 함수
void reversePrintList(Node* ptr) {
	printf("value는 %d \n", ptr->value);
	if (ptr->leftLink != NULL) {
		reversePrintList(ptr->leftLink);
	}
}


int main() {
	Node *p, *q, *r;

	p = (Node*)malloc(sizeof(Node));
	q = (Node*)malloc(sizeof(Node));
	r = (Node*)malloc(sizeof(Node));

	p->value = 1;
	p->leftLink = NULL;
	p->rightLink = q;

	
	q->value = 2;
	q->leftLink = p;
	q->rightLink = r;


	r->value = 3;
	r->leftLink = q;
	r->rightLink = NULL;

	printf("리스트를 출력합니다 \n");
	printList(p);
	printf("\n역으로 출력합니다 \n");
	reversePrintList(r);

	
}

단순 연결 리스트에서 역으로 출력하고 싶었다면
상당히 복잡했습니다.
그러나 이중연결리스트에서는 그냥 printList 함수가 leftLink를 가리키게 변경하면 끝납니다.

위의 printList 함수를 수정하고
printList 함수, 공백 리스트를 만드는 함수, 리스트를 비우는 함수를 추가하여 진행합니다.

#include<stdio.h>
#include<malloc.h>

// 노드 구조체
typedef struct Node {
	struct Node* leftLink;
	int value;
	struct Node* rightLink;
}; Node;

// 시작점을 가리키는 구조체
typedef struct Start {
	Node* head;
}; Start;


// 연결 리스트를 출력하는 연산
// True = 정 / false = 역
void printList(Start* L, bool sel) {
	Node* p;
	printf("L = (");
	
    // 예외처리를 위해 선언
	if (L->head == NULL) {
		printf(") \n");
		return;
	}
	else {
		// 정
		if (sel == true) {
			p = L->head;
			while (p->rightLink != NULL) {
				printf("%d", p->value);
				p = p->rightLink;
				if (p != NULL) printf(", ");
			}
			printf("%d", p->value);  // 마지막 노드일때 null이라 마지막 value가 출력이 안됩니다. 
			// 그래서 pintf를 추가하긴 했는데, 아마 이는 깔끔한 방법이 아니라 생각됩니다.
			printf(") \n");
		}

		// 역
		if (sel == false) {
			p = L->head;
			while (p->rightLink != NULL) {
				p = p->rightLink;
			}

			while (p->leftLink != NULL) {
				printf("%d", p->value);
				p = p->leftLink;
				if (p != NULL) printf(", ");
			}
			printf("%d", p->value);
			printf(") \n");
		}
	}
	
}


Start* createLinkedList() {
	Start* L;
	L = (Start*)malloc(sizeof(Start));
	L->head = NULL;
	return L;
}

void freeLinkedList(Start* L) {
	Node* temp;
	while (L->head != NULL) {
		temp = L->head;
		L->head = L->head->rightLink;
		free(temp);
		temp = NULL;
	}
}



int main() {
	Node *p, *q, *r;
	Start* L;
	L = createLinkedList();

	p = (Node*)malloc(sizeof(Node));
	q = (Node*)malloc(sizeof(Node));
	r = (Node*)malloc(sizeof(Node));
	
	L->head = p;

	p->value = 1;
	p->leftLink = NULL;
	p->rightLink = q;

	
	q->value = 2;
	q->leftLink = p;
	q->rightLink = r;


	r->value = 3;
	r->leftLink = q;
	r->rightLink = NULL;

	printf("리스트를 출력합니다 \n");
	printList(L, true);
	printf("\n역으로 출력합니다 \n");
	printList(L, false);
}

이를 통해
알고리즘 구현을 시작하겠습니다.
이 코드를 기초로 시작합니다.

#include<stdio.h>
#include<malloc.h>

// 노드 구조체
typedef struct Node {
	struct Node* leftLink;
	int value;
	struct Node* rightLink;
}; Node;

// 시작점을 가리키는 구조체
typedef struct Start {
	Node* head;
}; Start;


// 연결 리스트를 출력하는 연산
// True = 정 / false = 역
void printList(Start* L, bool sel) {
	Node* p;
	printf("L = (");
	
    // 예외처리를 위해 선언
	if (L->head == NULL) {
		printf(") \n");
		return;
	}
	else {
		// 정
		if (sel == true) {
			p = L->head;
			while (p->rightLink != NULL) {
				printf("%d", p->value);
				p = p->rightLink;
				if (p != NULL) printf(", ");
			}
			printf("%d", p->value);  // 마지막 노드일때 null이라 마지막 value가 출력이 안됩니다. 
			// 그래서 pintf를 추가하긴 했는데, 아마 이는 깔끔한 방법이 아니라 생각됩니다.
			printf(") \n");
		}

		// 역
		if (sel == false) {
			p = L->head;
			while (p->rightLink != NULL) {
				p = p->rightLink;
			}

			while (p->leftLink != NULL) {
				printf("%d", p->value);
				p = p->leftLink;
				if (p != NULL) printf(", ");
			}
			printf("%d", p->value);
			printf(") \n");
		}
	}
	
}


Start* createLinkedList() {
	Start* L;
	L = (Start*)malloc(sizeof(Start));
	L->head = NULL;
	return L;
}

void freeLinkedList(Start* L) {
	Node* temp;
	while (L->head != NULL) {
		temp = L->head;
		L->head = L->head->rightLink;
		free(temp);
		temp = NULL;
	}
}



int main() {
	Start* L;
	L = createLinkedList();


}

---

1. 이중 연결 리스트에서 삽입하는 연산을 수행하는 함수

---

이중 연결 리스트에 삽입하는 알고리즘을 생각해보자.
간단하게 생각해서
(1) (NULL / 값 / B) (2)-> ( A / 값 / NULL) (3)

(1) 맨처음에 삽입한다고 생각해보자.
( / 값 / )
L(시작점)의 링크는 오른쪽 링크에 들어가고
왼쪽 링크는 NULL이 된다.


(2)중간에 노드를 삽입하자.
삽입하는 노드를 C라하자
( / 값 / )
A노드의 오른쪽링크(B)를 C의 오른쪽에 삽입하자
B노드의 왼쪽링크(A)를 C의 왼쪽에 삽입하자.
(A / 값 / B)

(3) 맨끝에 삽입한다고 생각해보자.
( / 값 / )
이전 노드의 링크는 왼쪽 링크에 들어가고
오른쪽 링크는 NULL이 된다.
(그러나 이 알고리즘은 필요없을 것이다.)


우선 (1) 맨 처음에 노드를 삽입하는 함수이다.

// 해당 함수는 치명적인 오류가 있다.
void insertFirstNode(Start *L, int Xvalue) {
	Node* newNode;  // 노드를 하나 생성하고 할당 받는다.
	newNode = (Node*)malloc(sizeof(Node));
	newNode->value = Xvalue; // 값과 링크를 지정하고
	newNode->rightLink = L->head;
	newNode->leftLink = L->head;
	L->head = newNode; // 시작점은 지금 만든노드를 가리키게한다.
}


 --- 생략 ---
 
 int main() {
	Start* L;
	L = createLinkedList();

	int insert;

	printf("처음에 삽입합니다. 값을 입력하세요 -> ");
	scanf("%d", &insert);
	insertFirstNode(L, insert);

	printList(L, true);
}

이전의 단순 연결리스트 함수에서 링크를 지정하는 부분만 수정했다.

그러나 중간에 오류를 발견했다
(사실은 계속 진행하다가 막혔다)

위의 함수로만 값을 채워나가면 leftLink는 제대로 된 값이 저장되지 않는 것이다.

그러니 함수를 수정했다.

처음에 생성을 하면
다음 노드의 왼쪽링크와 L(시작점)은 newNode를 가리켜야 하고
newNode의 왼쪽링크는 NULL을 오른쪽은 newNode를 가리켜야합니다.
그래서 다음과 같이 코드를 전체적으로 수정합니다.

void printList(Start* L) {
	Node* p;
	printf("L = (");
	p = L->head;
	while (p != NULL) {
		printf("%d", p->value);
		p = p->rightLink;
		if (p != NULL) printf(", ");
	}
	printf(") \n");
}

void reversePrintList(Start* L) {
	Node* p;
	printf("L = (");
	p = L->head;
	while (p->rightLink != NULL) {
		p = p->rightLink;
	}

	while (p->leftLink != NULL) {
		printf("%d", p->value);
		p = p->leftLink;
		if (p != NULL) printf(", ");
	}
	printf("%d", p->value);
	printf(") \n");
}

printList의 경우 문제를 찾기위해 함수를 분할하였음.

void insertFirstNode(Start* L, int Xvalue) {
		Node* newNode;  // 노드를 하나 생성하고 할당 받는다.
		newNode = (Node*)malloc(sizeof(Node));
		newNode->value = Xvalue; // 값과 링크를 지정하고
		
		if (L->head == NULL) {
			newNode->rightLink = NULL;
			newNode->leftLink = NULL;
		}
		else {
			newNode->rightLink = L->head;
			newNode->leftLink = NULL;
			L->head->leftLink = newNode;
		}
		L->head = newNode; // 시작점은 지금 만든노드를 가리키게한다.
}

위 그림판의 그림처럼 코드를 수정한 것인데 (내 1시간..)
공백리스트라면 -> 새로운 노드는 왼쪽링크, 오른쪽링크 모두 NULL을 가져야한다.
근데, 처음에 삽입하는 경우라면
다음 노드의 왼쪽 링크는 새로운 노드를 카리키고
새로운 노드의 왼쪽은 NULL , 오른쪽은 기존의 노드를 가리키게 변경했다.


(2)중간에 노드를 삽입하자는 경우를 구현하기 전
우리는 노드를 탐색하는 함수를 먼저 구현해야한다.

---

2. 노드를 탐색하는 함수를 구현하자.
단순연결리스트와 비슷하게 흘러간다.
temp를 시작점부터 끝노드까지 돌리고 같은 값을 가지는 노드를 반환한다.
(중복되는 노드 문제는 나중에 생각해보자)

// 값을 가지는 노드를 탐색하여 리턴한다.
Node* SearchNode(Start* L, int Xvalue) {
	Node* temp;
	temp = L->head;
	while (temp != NULL) {
		if (temp->value == Xvalue)
			return temp;
		else
			temp = temp->rightLink;
	}

	return temp;
}

---

다시 돌아왔다.
중간에 삽입하는 경우의 코드이다.

void insertMiddleNode(Start* L, Node* pre, int Xvalue) {
	Node* newNode;
	newNode = (Node*)malloc(sizeof(Node));
	newNode->value = Xvalue;

	// 공백리스트일 경우
	if (L == NULL) {
		newNode->rightLink = NULL;
		newNode->leftLink = NULL;
		L->head = newNode;
	}

	// pre의 R링크가 NULL이여도 상관없다. (끝에 넣는 것이여도 문제 없다)
	else {
		newNode->rightLink = pre->rightLink;
		pre->rightLink = newNode;
		newNode -> leftLink = pre;
		// 중간에 삽입되는 경우라면 다음 노드의 왼쪽은 삽입되는 노드를 가리켜야한다.
		if (newNode->rightLink != NULL)
			newNode->rightLink->leftLink = newNode;
	}
}

-- 중간 생략 --

int main() {
	Start* L;
	L = createLinkedList();

	int insert;

	printf("처음에 삽입합니다. 값을 입력하세요 -> ");
	scanf("%d", &insert);
	insertFirstNode(L, insert);
	printList(L, true);

	printf("처음에 삽입합니다. 값을 입력하세요 -> ");
	scanf("%d", &insert);
	insertFirstNode(L, insert);
	printList(L, true);

	printf("중간에 삽입합니다. 삽입하고 싶은 위치의 값을 입력하세요 -> ");
	scanf("%d", &insert);
	
	Node* p;
	p = SearchNode(L, insert);
	printf("노드 뒤에 삽입합니다. 값을 입력하세요. -> ");
	scanf("%d", &insert);
	insertMiddleNode(L, p, insert);
	printList(L, true);
	
}

공백리스트일 경우 첫번째 함수를 만든다.

마지막에도 잘 삽입되는 모습이다.

그러나 현재 문제는 값의 크기가 겹치지 않는다는 가정하에 진행되는 것이다.
( 이 부분은 나중에 시간이 생긴다면 수정해보도록하겠다.)

---

3. 삭제를 구현하기 전 UI를 구현하자.

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>

// 노드 구조체
typedef struct Node {
	struct Node* leftLink;
	int value;
	struct Node* rightLink;
}; Node;

// 시작점을 가리키는 구조체
typedef struct Start {
	Node* head;
}; Start;


// 연결 리스트를 출력하는 연산
void printList(Start* L) {
	Node* p;
	printf("L = (");
	p = L->head;
	while (p != NULL) {
		printf("%d", p->value);
		p = p->rightLink;
		if (p != NULL) printf(", ");
	}
	printf(") \n");
}


void reversePrintList(Start* L) {
	Node* p;
	printf("L = (");
	p = L->head;
	while (p->rightLink != NULL) {
		p = p->rightLink;
	}

	while (p->leftLink != NULL) {
		printf("%d", p->value);
		p = p->leftLink;
		if (p != NULL) printf(", ");
	}
	printf("%d", p->value);
	printf(") \n");
}
		


Start* createLinkedList() {
	Start* L;
	L = (Start*)malloc(sizeof(Start));
	L->head = NULL;
	return L;
}

void freeLinkedList(Start* L) {
	Node* temp;
	while (L->head != NULL) {
		temp = L->head;
		L->head = L->head->rightLink;
		free(temp);
		temp = NULL;
	}
}


void insertFirstNode(Start* L, int Xvalue) {
		Node* newNode;  // 노드를 하나 생성하고 할당 받는다.
		newNode = (Node*)malloc(sizeof(Node));
		newNode->value = Xvalue; // 값과 링크를 지정하고
		
		if (L->head == NULL) {
			newNode->rightLink = NULL;
			newNode->leftLink = NULL;
		}
		else {
			newNode->rightLink = L->head;
			newNode->leftLink = NULL;
			L->head->leftLink = newNode;
		}
		L->head = newNode; // 시작점은 지금 만든노드를 가리키게한다.
}

// 값을 가지는 노드를 탐색하여 리턴한다.
Node* SearchNode(Start* L, int Xvalue) {
	Node* temp;
	temp = L->head;
	while (temp != NULL) {
		if (temp->value == Xvalue)
			return temp;
		else
			temp = temp->rightLink;
	}

	return temp;
}



void insertMiddleNode(Start* L, Node* pre, int Xvalue) {
	Node* newNode;
	newNode = (Node*)malloc(sizeof(Node));
	newNode->value = Xvalue;

	// 공백리스트일 경우
	if (L == NULL) {
		newNode->rightLink = NULL;
		newNode->leftLink = NULL;
		L->head = newNode;
	}

	// pre의 R링크가 NULL이여도 상관없다. (끝에 넣는 것이여도 문제 없다)
	else {
		newNode->rightLink = pre->rightLink;
		pre->rightLink = newNode;
		newNode -> leftLink = pre;
		// 중간에 삽입되는 경우라면 다음 노드의 왼쪽은 삽입되는 노드를 가리켜야한다.
		if (newNode->rightLink != NULL)
			newNode->rightLink->leftLink = newNode;
	}
}


void insertSituation(Start* L) {
	printList(L, true);
	printf("삽입할 위치는 1. 처음, 2. 중간 혹은 끝 ->");
	int sel1, insert;
	Node* p;
	scanf("%d", &sel1);
	switch (sel1) {
	case 1:
		printf("처음에 삽입합니다. 값을 입력하세요 -> ");
		scanf("%d", &insert);
		insertFirstNode(L, insert);
		break;

	case 2:
		printf("중간 혹은 끝에 삽입합니다. 원하는 지점의 값을 입력하세요 -> ");
		scanf("%d", &insert);
		p = SearchNode(L, insert);
		printf("노드 뒤에 삽입합니다. 값을 입력하세요. -> ");
		scanf("%d", &insert);
		insertMiddleNode(L, p, insert);
		break;
	}
}




int main() {
	Start* L;

	int sel;
	L = createLinkedList();


	printf("----연결 리스트 구현하기----\n");

	while (true) {
		printList(L, true);
		printf("원하는 작업을 선택하세요. 1. 삽입, 2. 삭제, 3. 리스트를 비우기, 4. 역순으로 출력하기 ->");
		scanf("%d", &sel);

		switch (sel) {
		case 1:
			insertSituation(L);
			break;

		case 2:

			break;

		case 3:
			freeLinkedList(L);
			break;

		case 4:
			printf("역순으로 출력합니다.");
			printList(L, false);
			printf("\n");
			break;
		}
	}



}

3. 역순으로 저장하기는 이중연결에서 의미가 없으므로 역으로 출력을 하는거로 하겠다.
단순 연결 리스트와 다르게 이중연결리스트는 이미 이전의 노드로 가는 주소를 알고 있기 때문에 따로 저장을 할 필요가 없다고 생각된다.

---

4. 삭제를 구현하기

---

생각을 해보자.
(1) (NULL / 값 / B) -> (2)( A / 값 / C) -> (3)(B/ 값 / NULL)
(1) 처음 값을 삭제하고 싶다.
삭제를 한다 -> L이 B노드를 가리키게 하고
B노드의 왼쪽링크는 NULL을 가리킨다.

(2) 중간 값을 삭제하고 싶다.
삭제를 한다 -> A노드 (전노드)의 오른쪽 링크가 C를 가리키게 한다.
C의 왼쪽 링크는 A를 가리킨다.

(3) 마지막 값을 삭제하고 싶다.
삭제를 한다 -> B노드 (전노드)의 오른쪽 링크가 NULL을 가리키게 한다.

합쳐 생각해보면
삭제할 노드의 rightLink가 NULL이 아니라면
삭제할 노드의 lefhtLink를 다음의 노드에게 준다.

삭제할 노드의 rightLink를 이전의 노드에게 준다.
-> right 노드가 NULL이건 아니건 상관없다.

// 이중 연결 리스트에서 old 노드를 삭제하는 연산
void deleteNode(Start* L, Node* p) {
	//공백리스트라면 리턴
	if (L->head == NULL) {
		printf("삭제할 리스트가 없습니다.");
		return;
	}

	// 만약 리스트가 한개라면
	if (L->head->rightLink == NULL) {
		freeLinkedList(L);
	}

	//리스트가 없다면 리턴
	else if (p == NULL) {
		printf("삭제할 리스트가 없습니다.");
		return;
	}

	else {
		p->leftLink->rightLink = p->rightLink;
		if (p->rightLink != NULL) {
			p->rightLink->leftLink = p->leftLink;
		}
		free(p);
	}
}

삭제를 담당하는 코드이다.

완성된 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>

// 노드 구조체
typedef struct Node {
	struct Node* leftLink;
	int value;
	struct Node* rightLink;
}; Node;

// 시작점을 가리키는 구조체
typedef struct Start {
	Node* head;
}; Start;


// 연결 리스트를 출력하는 연산
void printList(Start* L) {
	Node* p;
	printf("L = (");
	p = L->head;
	while (p != NULL) {
		printf("%d", p->value);
		p = p->rightLink;
		if (p != NULL) printf(", ");
	}
	printf(") \n");
}


void reversePrintList(Start* L) {
	Node* p;
	printf("L = (");
	p = L->head;
	while (p->rightLink != NULL) {
		p = p->rightLink;
	}

	while (p->leftLink != NULL) {
		printf("%d", p->value);
		p = p->leftLink;
		if (p != NULL) printf(", ");
	}
	printf("%d", p->value);
	printf(") \n");
}






Start* createLinkedList() {
	Start* L;
	L = (Start*)malloc(sizeof(Start));
	L->head = NULL;
	return L;
}

void freeLinkedList(Start* L) {
	Node* temp;
	while (L->head != NULL) {
		temp = L->head;
		L->head = L->head->rightLink;
		free(temp);
		temp = NULL;
	}
}


void insertFirstNode(Start* L, int Xvalue) {
		Node* newNode;  // 노드를 하나 생성하고 할당 받는다.
		newNode = (Node*)malloc(sizeof(Node));
		newNode->value = Xvalue; // 값과 링크를 지정하고
		
		if (L->head == NULL) {
			newNode->rightLink = NULL;
			newNode->leftLink = NULL;
		}
		else {
			newNode->rightLink = L->head;
			newNode->leftLink = NULL;
			L->head->leftLink = newNode;
		}
		L->head = newNode; // 시작점은 지금 만든노드를 가리키게한다.
}


// 값을 가지는 노드를 탐색하여 리턴한다.
Node* SearchNode(Start* L, int Xvalue) {
	Node* temp;
	temp = L->head;
	while (temp != NULL) {
		if (temp->value == Xvalue)
			return temp;
		else
			temp = temp->rightLink;
	}

	return temp;
}



void insertMiddleNode(Start* L, Node* pre, int Xvalue) {
	Node* newNode;
	newNode = (Node*)malloc(sizeof(Node));
	newNode->value = Xvalue;

	// 공백리스트일 경우
	if (L == NULL) {
		newNode->rightLink = NULL;
		newNode->leftLink = NULL;
		L->head = newNode;
	}

	// pre의 R링크가 NULL이여도 상관없다. (끝에 넣는 것이여도 문제 없다)
	else {
		newNode->rightLink = pre->rightLink;
		pre->rightLink = newNode;
		newNode->leftLink = pre;
		// 중간에 삽입되는 경우라면 다음 노드의 왼쪽은 삽입되는 노드를 가리켜야한다.
		if (newNode->rightLink != NULL)
			newNode->rightLink->leftLink = newNode;
	}
}

// 이중 연결 리스트에서 old 노드를 삭제하는 연산
void deleteNode(Start* L, Node* p) {
	//공백리스트라면 리턴
	if (L->head == NULL) {
		printf("삭제할 리스트가 없습니다.");
		return;
	}

	// 만약 리스트가 한개라면
	if (L->head->rightLink == NULL) {
		freeLinkedList(L);
	}

	//리스트가 없다면 리턴
	else if (p == NULL) {
		printf("삭제할 리스트가 없습니다.");
		return;
	}

	else {
		p->leftLink->rightLink = p->rightLink;
		if (p->rightLink != NULL) {
			p->rightLink->leftLink = p->leftLink;
		}
		free(p);
	}
}



void insertSituation(Start* L) {
	printList(L);
	printf("삽입할 위치는 1. 처음, 2. 중간 혹은 끝 ->");
	int sel1, insert;
	Node* p;
	scanf("%d", &sel1);
	switch (sel1) {
	case 1:
		printf("처음에 삽입합니다. 값을 입력하세요 -> ");
		scanf("%d", &insert);
		insertFirstNode(L, insert);
		break;

	case 2:
		printf("중간 혹은 끝에 삽입합니다. 원하는 지점의 값을 입력하세요 -> ");
		scanf("%d", &insert);
		p = SearchNode(L, insert);
		printf("노드 뒤에 삽입합니다. 값을 입력하세요. -> ");
		scanf("%d", &insert);
		insertMiddleNode(L, p, insert);
		break;
	}
}

void deleteSituation(Start* L) {
	int insert;
	Node* p;
	printList(L);
	printf("삭제할 value를 입력하세요. ->");
	scanf("%d", &insert);
	p = SearchNode(L, insert);
	deleteNode(L, p);
}


int main() {
	Start* L;

	int sel;
	L = createLinkedList();


	printf("----연결 리스트 구현하기----\n");

	while (true) {
		printList(L);
		printf("원하는 작업을 선택하세요. 1. 삽입, 2. 삭제, 3. 리스트를 비우기, 4. 역순으로 출력하기 ->");
		scanf("%d", &sel);

		switch (sel) {
		case 1:
			insertSituation(L);
			break;

		case 2:
			deleteSituation(L);
			break;

		case 3:
			freeLinkedList(L);
			break;

		case 4:
			printf("역순으로 출력합니다.");
			reversePrintList(L);
			printf("\n");
			break;
		}
	}



}

---

추가적으로
이중 연결 리스트의 장점을 보기 좋은 상황을 하나 구현해보자.

5. (값) 이전 (1) , 다음 (2)
로 하나씩 값을 보는 것을 구현해보자.

void wantSee(Start* L) {
	Node* p;
	int count = 1;
	bool sel;
	p = L->head;

	printf("조회를 시작합니다. \n");
	while (true) {
		printf("\n%d번째 값 = %d \n", count, p->value);
		printf("0.이전 , 1. 다음");

		scanf("%d", &sel);
		if (sel == 0) {
			if (p->leftLink == NULL)
				printf("왼쪽 끝입니다.\n");
			else {
				p = p->leftLink;
				count++;
			}
		}

		if (sel == 1) {
			if (p->rightLink == NULL)
				printf("오른쪽 끝입니다.\n");
			else {
				p = p->rightLink;
				count++;
			}
			
		}
	
	}
}

그러면 전체적으로 구현된 코드를 다시 한 번 올리면서 문제풀이를 마무리한다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>

// 노드 구조체
typedef struct Node {
	struct Node* leftLink;
	int value;
	struct Node* rightLink;
}; Node;

// 시작점을 가리키는 구조체
typedef struct Start {
	Node* head;
}; Start;


// 연결 리스트를 출력하는 연산
void printList(Start* L) {
	Node* p;
	printf("L = (");
	p = L->head;
	while (p != NULL) {
		printf("%d", p->value);
		p = p->rightLink;
		if (p != NULL) printf(", ");
	}
	printf(") \n");
}


void reversePrintList(Start* L) {
	Node* p;
	printf("L = (");
	p = L->head;
	while (p->rightLink != NULL) {
		p = p->rightLink;
	}

	while (p->leftLink != NULL) {
		printf("%d", p->value);
		p = p->leftLink;
		if (p != NULL) printf(", ");
	}
	printf("%d", p->value);
	printf(") \n");
}






Start* createLinkedList() {
	Start* L;
	L = (Start*)malloc(sizeof(Start));
	L->head = NULL;
	return L;
}

void freeLinkedList(Start* L) {
	Node* temp;
	while (L->head != NULL) {
		temp = L->head;
		L->head = L->head->rightLink;
		free(temp);
		temp = NULL;
	}
}


void insertFirstNode(Start* L, int Xvalue) {
		Node* newNode;  // 노드를 하나 생성하고 할당 받는다.
		newNode = (Node*)malloc(sizeof(Node));
		newNode->value = Xvalue; // 값과 링크를 지정하고
		
		if (L->head == NULL) {
			newNode->rightLink = NULL;
			newNode->leftLink = NULL;
		}
		else {
			newNode->rightLink = L->head;
			newNode->leftLink = NULL;
			L->head->leftLink = newNode;
		}
		L->head = newNode; // 시작점은 지금 만든노드를 가리키게한다.
}


// 값을 가지는 노드를 탐색하여 리턴한다.
Node* SearchNode(Start* L, int Xvalue) {
	Node* temp;
	temp = L->head;
	while (temp != NULL) {
		if (temp->value == Xvalue)
			return temp;
		else
			temp = temp->rightLink;
	}

	return temp;
}



void insertMiddleNode(Start* L, Node* pre, int Xvalue) {
	Node* newNode;
	newNode = (Node*)malloc(sizeof(Node));
	newNode->value = Xvalue;

	// 공백리스트일 경우
	if (L == NULL) {
		newNode->rightLink = NULL;
		newNode->leftLink = NULL;
		L->head = newNode;
	}

	// pre의 R링크가 NULL이여도 상관없다. (끝에 넣는 것이여도 문제 없다)
	else {
		newNode->rightLink = pre->rightLink;
		pre->rightLink = newNode;
		newNode->leftLink = pre;
		// 중간에 삽입되는 경우라면 다음 노드의 왼쪽은 삽입되는 노드를 가리켜야한다.
		if (newNode->rightLink != NULL)
			newNode->rightLink->leftLink = newNode;
	}
}

// 이중 연결 리스트에서 old 노드를 삭제하는 연산
void deleteNode(Start* L, Node* p) {
	//공백리스트라면 리턴
	if (L->head == NULL) {
		printf("삭제할 리스트가 없습니다.");
		return;
	}

	// 만약 리스트가 한개라면
	if (L->head->rightLink == NULL) {
		freeLinkedList(L);
	}

	//리스트가 없다면 리턴
	else if (p == NULL) {
		printf("삭제할 리스트가 없습니다.");
		return;
	}

	else {
		p->leftLink->rightLink = p->rightLink;
		if (p->rightLink != NULL) {
			p->rightLink->leftLink = p->leftLink;
		}
		free(p);
	}
}



void insertSituation(Start* L) {
	printList(L);
	printf("삽입할 위치는 1. 처음, 2. 중간 혹은 끝 ->");
	int sel1, insert;
	Node* p;
	scanf("%d", &sel1);
	switch (sel1) {
	case 1:
		printf("처음에 삽입합니다. 값을 입력하세요 -> ");
		scanf("%d", &insert);
		insertFirstNode(L, insert);
		break;

	case 2:
		printf("중간 혹은 끝에 삽입합니다. 원하는 지점의 값을 입력하세요 -> ");
		scanf("%d", &insert);
		p = SearchNode(L, insert);
		printf("노드 뒤에 삽입합니다. 값을 입력하세요. -> ");
		scanf("%d", &insert);
		insertMiddleNode(L, p, insert);
		break;
	}
}

void deleteSituation(Start* L) {
	int insert;
	Node* p;
	printList(L);
	printf("삭제할 value를 입력하세요. ->");
	scanf("%d", &insert);
	p = SearchNode(L, insert);
	deleteNode(L, p);
}

void wantSee(Start* L) {
	Node* p;
	int count = 1;
	bool sel;
	p = L->head;

	printf("조회를 시작합니다. \n");
	while (true) {
		printf("\n%d번째 값 = %d \n", count, p->value);
		printf("0.이전 , 1. 다음");

		scanf("%d", &sel);
		if (sel == 0) {
			if (p->leftLink == NULL)
				printf("왼쪽 끝입니다.\n");
			else {
				p = p->leftLink;
				count++;
			}
		}

		if (sel == 1) {
			if (p->rightLink == NULL)
				printf("오른쪽 끝입니다.\n");
			else {
				p = p->rightLink;
				count++;
			}
			
		}
	
	}
}


int main() {
	Start* L;

	int sel;
	L = createLinkedList();


	printf("----연결 리스트 구현하기----\n");

	while (true) {
		printList(L);
		printf("원하는 작업을 선택하세요. 1. 삽입, 2. 삭제, 3. 리스트를 비우기, 4. 역순으로 출력하기, 5 조회 ->");
		scanf("%d", &sel);

		switch (sel) {
		case 1:
			insertSituation(L);
			break;

		case 2:
			deleteSituation(L);
			break;

		case 3:
			freeLinkedList(L);
			break;

		case 4:
			printf("역순으로 출력합니다.");
			reversePrintList(L);
			printf("\n");
			break;

		case 5:
			wantSee(L);
			break;
		}
	}



}

---

저번시간에 연결리스트로 힘들었더니
이번에는 쉽게쉽게 풀었다.
중간에 오류났을때 교재에다가 내가 원하는 내용을 추가하는 거라
교재의 코드를 정확히 적어도 오류가 발생해서
던지고 싶었는데 결국 찾았음.