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

단순 연결 리스트
순차 리스트는 물리적인 순서와 논리적인 순서가 일치하지만, 연결 리스트의 경우 논리적인 순서는 일치하나 물리적인 순서가 같지 않는 것을 말한다.

( 값 / 주소)
이루어진 하나의 데이터를 노드라고 부른다.

(값 / 100번지 주소) -> ( 100번지 값 / 200번지 주소) -> (200번지 값 / NULL)
처럼 자료를 저장한다.


문제
단순연결리스트에서 다음 함수들을 구현하시오.
1. 단순 연결 리스트에서 삽입하는 연산을 수행하는 함수
2. 단순 연결 리스트에서 노드를 탐색하는 함수
3. 단순 연결 리스트에서 삭제 연산을 수행하는 함수
4. 모든 노드를 역순으로 저장하는 함수
사용자로 부터 값을 입력받는 것으로 진행하세요.

---

0. 구현하기 전 연결 리스트 구현하기.

---

하나의 노드는
(값, 주소) 를 가진다.
3개의 노드를 선언하고 3개를 모두 출력해보자.

값과 노드를 가지는 변수가 필요하다.
-> 구조체를 이용해야한다.

typedef struct Node {
	int value;
	struct Node* link;
}; Node;

(값은 정수형으로 하였다.)
링크는 다음 노드를 가리켜야한다.
여기까지는 쉽다.

이걸 main에서 어떻게 구현할 것인가?

// 해당 코드는 틀렸다.

#include<stdio.h>

typedef struct Node {
	int value;
	struct Node* link;
}; Node;


int main() {
	Node p, q;
	p.value = 1;
	q.value = 2;

	p.link = &q;
	q.link = NULL;


	printf("p의 값은 %d, q의 값은 %d", p.value, q.value);
}

이렇게 구현을 할 것인가?
이건 연결 리스트가 아니다.
연결리스트는
p의 값을 확인하고, p의 주소값을 보니 q를 가리키고 있다.
그래서 q로 가서 q의 값을 보고 q의 주소값이 a를 가리키고 있다.
그래서 a로 가서 a의 값을 보고 a의 주소값이 NULL을 가리키고 있으니 종료한다.

printf("p의 값은 %d, q의 값은 %d", p.value, q.value);

이 코드는 연결리스트로서 의미가 없는 코드라는 것이다.


밑의 printf를 살짝만 변경하자.

//해당 코드는 연결 리스트의 특징을 보여준다.

#include<stdio.h>

typedef struct Node {
	int value;
	struct Node* link;
}; Node;


int main() {
	Node p, q;
	p.value = 1;
	q.value = 2;

	p.link = &q;
	q.link = NULL;


	printf("p의 값은 %d, q의 값은 %d", p.value, p.link->value);
}

마지막 줄만 변경되었다.
p.link 의 value를 출력해라.

정상적으로 출력된다.
연결리스트의 특징을 보였지만 교재와 강의가 원하는 정답은 아니다.

정답은 이렇다.
후에 함수로 변수를 넘겨주어야 하기 때문에
노드를 포인터 형식으로 선언해보자.

// 해당 코드는 동작하지 않는다.
#include<stdio.h>

typedef struct Node {
	int value;
	struct Node* link;
}; Node;


int main() {
	Node *p, *q, *ptr;
	p->value = 3;
	p->link = NULL;

	q->value = 2;
	q->link = p;

	ptr->value = 1;
	ptr->link = q;

}

포인터 변수만 선언하면 동작하지 않는다.
메모리를 할당해줘야한다.

// 3개의 노드를 선언한 코드
#include<stdio.h>
#include<malloc.h>

typedef struct Node {
	int value;
	struct Node* link;
}; Node;


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

	p = (Node*)malloc(sizeof(Node));
	p->value = 3;
	p->link = NULL;

	q = (Node*)malloc(sizeof(Node));
	q->value = 2;
	q->link = p;

	ptr = (Node*)malloc(sizeof(Node));
	ptr->value = 1;
	ptr->link = q;

}

이렇게 완성된다.

그러면 p, q, ptr을 출력하는 함수를 작성해보자.

void printList(Node *ptr) { }

알고리즘을 생각해보자.
매개변수 ptr의 value 값을 출력하고
주소가 NULL 이 아니라면
printList 함수에 매개변수 ptr이 가리키는 주소를 넣으세요.
이렇게 하면 구현할 수 있을 것이다.

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

typedef struct Node {
	int value;
	struct Node* link;
}; Node;

void printList(Node* ptr) { 
	printf("value는 %d \n", ptr->value);
	if (ptr->link != NULL) {
		printList(ptr->link);
	}
}


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

	p = (Node*)malloc(sizeof(Node));
	p->value = 3;
	p->link = NULL;

	q = (Node*)malloc(sizeof(Node));
	q->value = 2;
	q->link = p;

	ptr = (Node*)malloc(sizeof(Node));
	ptr->value = 1;
	ptr->link = q;

	printList(ptr);

}

 

이를 구현하고 나서 한 가지 고민을 해보자.

void printList(Node *ptr) { }

우리는 나중에 삽입연산과 삭제연산을 구현할 예정이다.

그러면 ptr의 앞에 노드가 삽입되거나, ptr의 노드가 삭제되었다고 생각해보자.

그러면 해당 printList 함수로는 정상적으로 출력이 불가능해진다.

그래서 한가지 생각을 보자.
첫번째 노드를 가리키는 주소 변수를 하나 만들자

그럼 또 문제가 생긴다.
ptr의 주소는 어떻게 저장할 것인가?

Node의 주소를 가지는 변수를 구조체로 선언하자.

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

typedef struct Node {
	int value;
	struct Node* link;
}; Node;

typedef struct Start {
	Node* head;
}; Start;


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


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

	p = (Node*)malloc(sizeof(Node));
	p->value = 3;
	p->link = NULL;

	q = (Node*)malloc(sizeof(Node));
	q->value = 2;
	q->link = p;

	ptr = (Node*)malloc(sizeof(Node));
	ptr->value = 1;
	ptr->link = q;

	Start* L;
	L = (Start*)malloc(sizeof(Start));
	L->head = ptr;

	printList(L);

}

이제 연결리스트 구현을 마무리 하고, 문제로 들어가자.

---

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

---

우선 위에서 사용한 코드에서 main 함수는 지우자.
노드를 삽입하는 과정을 생각해보자.

(L) -> (1) (값 / 100번지 주소) -> (2)( 100번지 값 / 200번지 주소) -> (2) (200번지 값 / NULL) (3)
1, 2, 3 으로 나눠서 생각을 해야한다.
1. 맨앞에 삽입을 하는 경우
2. 중간에 삽입을 하는 경우
3. 마지막에 삽입을 하는 경우


우선 1번 과정을 고민해봐야한다.
(L) -> (1) (값 / 100번지 주소) -> ( 100번지 값 / 200번지 주소) -> (200번지 값 / NULL)
함수에 들어가야할 변수는 L(시작점)과 value 값이다.
우선 새로운 노드를 동적으로 할당 받아야한다.
그리고 그 노드에 value를 저장하고,
노드의 링크는 L을 가진다.
그리고 L에게는 새로만든 노드의 링크를 지정해준다.

한 번 구현을 해보자.
교재와 강의에 따르면
공백리스트를 만드는 함수
(아무것도 없는 경우에 L을 할당하고 L의 주소값을 지정해주는 함수)
전체메모리를 해제하는 함수가 필요하다고 한다.

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

typedef struct Node {
	int value;
	struct Node* link;
}; 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->link;
		if (p != NULL) printf(", ");
	}
	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->link;
		free(temp);
		temp = NULL;
	}
}


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


}

 

현재 엑세스 위반이 발생하고 있습니다.
이를 교재에 있는 함수로 변경했는데 정상작동합니다.
그래서 코드를 변경했습니다.


가장 처음에 구현한 것은 맨앞에 삽입하는 연산을 구현한 것이다.

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

// 노드
typedef struct Node {
	int value;
	struct Node* link;
}; 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->link;
		if (p != NULL) printf(", ");
	}
	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->link;
		free(temp);
		temp = NULL;
	}
}

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


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

	insertFirstNode(L, 3);
	insertFirstNode(L, 2);
	insertFirstNode(L, 1);

	printList(L);
	freeLinkedList(L);
}

main함수는 3, 2, 1 순으로 삽입을 하였고 결과는

1, 2, 3 으로 나타난다. 정상적으로 삽입이 된 것을 확인하였다.

(L) -> (값 / 100번지 주소) -> ( 100번지 값 / 200번지 주소) -> (200번지 값 / NULL) (3)
마지막에 노드를 삽입하는 것을 생각해보자.
우선 리스트에 마지막이 어디인지 알 수 있을까?
그러기 위해서는 함수내부에서 마지막 함수를 찾아내는 temp 변수가 필요할 것이다.

공백리스트라면 맨앞에 삽입됨과 동시에 맨뒤에 삽입되는 상황이다.
그러니 L이 newNode를 가리키게 하고, newNode는 NULL을 가리키게 하자.

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

// 노드
typedef struct Node {
	int value;
	struct Node* link;
}; 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->link;
		if (p != NULL) printf(", ");
	}
	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->link;
		free(temp);
		temp = NULL;
	}
}

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

// 맨뒤에 노드를 삽입하는 함수
void insertLastNode(Start* L, int Xvalue) {
	Node* newNode; 
	newNode = (Node*)malloc(sizeof(Node));
	newNode->value = Xvalue;

	Node* temp; // 우리는 맨뒤의 노드가 newNode를 가리키게 해야한다.
	newNode->link = NULL; // 맨뒤니까 가리키는게 없다.

	// 만약 공백리스트라면 시작점이 newNode를 가리키게 해라.
	if (L->head == NULL) {
		L->head = newNode;
		return;
	}
	
    // 시작점 주소를 카리키게 한 후 반복문을 돌려 맨뒤 가리키는 값을 newNode로 바꾼다.
	temp = L->head;
	while (temp->link != NULL)
		temp = temp->link;
	temp->link = newNode;
}



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

	insertLastNode(L, 1);   // 1 저장된다.
	insertFirstNode(L, 3);   // 3 1 저장된다.
	insertLastNode(L, 1);   // 3 1 1 저장된다.

	printList(L);
	freeLinkedList(L);

}

(L) -> (값 / 100번지 주소) -> (2) ( 100번지 값 / 200번지 주소) -> (200번지 값 / NULL)
중간에 노드를 삽입하는 함수를 만들어보자.
이를 구현하기 전에 먼저 탐색을 하는 함수를 만들어야한다.

---

2. 단순 연결 리스트에서 노드를 탐색하는 함수

---

value 값을 가지는 노드를 리턴하기.
(중복되는 경우는 일단 무시하고 구현하자.)
위에서 구현했던 temp를 활용하면 될 것이라 생각한다.

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

// 노드
typedef struct Node {
	int value;
	struct Node* link;
}; 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->link;
		if (p != NULL) printf(", ");
	}
	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->link;
		free(temp);
		temp = NULL;
	}
}

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

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

	Node* temp;
	newNode->link = NULL;

	if (L->head == NULL) {
		L->head = newNode;
		return;
	}

	temp = L->head;
	while (temp->link != NULL)
		temp = temp->link;
	temp->link = newNode;
}


Node* SearchNode(Start* L, int Xvalue) {
	Node* temp;
	temp = L->head;
	while (temp != NULL) {
		if (temp->value == Xvalue)
			return temp;
		else
			temp = temp->link;
	}

	return temp;
}




int main() {
	Start* L;
	Node* p;

	int sel;

	L = createLinkedList();

	insertLastNode(L, 1);
	insertFirstNode(L, 3);
	insertLastNode(L, 2);

	printList(L);

	printf("조회를 시작합니다. value를 입력하세요.");
	scanf("%d", &sel);
	fflush(stdin);

	p = SearchNode(L, sel);
	printf("가져온 노드의 값은 %d", p->value);
	freeLinkedList(L);

}

 

중간에 노드를 삽입하는 함수의 경우

리스트가 공백리스트인 경우가 있을 것이고
공백리스트가 아닌 경우가 있을 것이다.

공백리스트인 경우, 맨앞에 삽입됨과 동시에 맨뒤에 삽입되는 상황이다.
그러니 L이 newNode를 가리키게 하고, newNode는 NULL을 가리키게 하자.

공백리스트가 아닌경우
삽입하고 싶은 노드의 이전값을 가져와서
이전값이 가리키는 값을 newNode에게 주고
이전값이 가리키는 값은 newNode를 가리키고
newNode는 다음값을 가리키게 한다.

이전값을 가지게 해야하기 때문에 탐색하는 코드를 먼저 작성하였다.

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

// 노드
typedef struct Node {
	int value;
	struct Node* link;
}; 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->link;
		if (p != NULL) printf(", ");
	}
	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->link;
		free(temp);
		temp = NULL;
	}
}

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

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

	Node* temp;
	newNode->link = NULL;

	if (L->head == NULL) {
		L->head = newNode;
		return;
	}

	temp = L->head;
	while (temp->link != NULL)
		temp = temp->link;
	temp->link = newNode;
}

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

	if (L == NULL) {
		newNode->link = NULL;
		L->head = newNode;
	}

	else if (pre == NULL)
		L->head = newNode;

	else {
		newNode->link = pre->link;
		pre->link = newNode;
	}
}


Node* SearchNode(Start* L, int Xvalue) {
	Node* temp;
	temp = L->head;
	while (temp != NULL) {
		if (temp->value == Xvalue)
			return temp;
		else
			temp = temp->link;
	}

	return temp;
}




int main() {
	Start* L;
	Node* p;

	int sel;

	L = createLinkedList();

	insertLastNode(L, 1);
	insertFirstNode(L, 3);
	insertLastNode(L, 2);

	printList(L);

	printf("조회를 시작합니다. value를 입력하세요.");
	scanf("%d", &sel);

	p = SearchNode(L, sel);
	printf("가져온 노드의 값은 %d \n", p->value);

	printf("가져온 노드 뒤에 노드를 삽입합니다. \n");
	insertMiddleNode(L, p, 10);
	printList(L);
    freeLinkedList(L);

}

 

 

이제

 

 UI를 구현하고, 연결리스트의 삭제와 역순으로 나타내는 과정을 진행하도록 하겠습니다.

 

---

3. 들어가기 전 : UI 구현하기

---

내가 직접 리스트를 작성하고

1. 조회

2. 삽입

3. 삭제

4. 리스트를 비우기

5. 역순으로 보여주기

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

// 노드
typedef struct Node {
	int value;
	struct Node* link;
}; 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->link;
		if (p != NULL) printf(", ");
	}
	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->link;
		free(temp);
		temp = NULL;
	}
}

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

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

	Node* temp;
	newNode->link = NULL;

	if (L->head == NULL) {
		L->head = newNode;
		return;
	}

	temp = L->head;
	while (temp->link != NULL)
		temp = temp->link;
	temp->link = newNode;
}

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

	if (L == NULL) {
		newNode->link = NULL;
		L->head = newNode;
	}

	else if (pre == NULL)
		L->head = newNode;

	else {
		newNode->link = pre->link;
		pre->link = newNode;
	}
}


Node* SearchNode(Start* L, int Xvalue) {
	Node* temp;
	temp = L->head;
	while (temp != NULL) {
		if (temp->value == Xvalue)
			return temp;
		else
			temp = temp->link;
	}

	return temp;
}


void insertSituation(Start* L) {
	printList(L);
	printf("삽입할 위치는 1. 처음, 2. 중간, 3. 끝 ->");
	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;

	case 3:
		printf("처음에 삽입합니다. 삽입할 자리의 값을 입력하세요. -> ");
		scanf("%d", &insert);
		insertLastNode(L, insert);
		break;
	}
}



int main() {
	Start* L;

	int sel;

	L = createLinkedList();


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

	while (true) {
		printList(L);
		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:

			break;
		}
	}

	

}

지금까지 구현한

삽입, 리스트비우기를 우선적으로 구현하였다.

우리는 탐색하는 과정을 value가 겹치지 않는다 가정을 하고 만들었다. 

그렇기 때문에 탐색을 할 경우 가장 왼쪽에 위치한 값을 찾게 된다.

(이 부분은 삭제, 역순까지 구현을 완료한 후에 생각을 해보자.)

정상작동하는 것을 확인하였다.

 

---

3. 연결 자료형의 삭제를 구현하기

---

삭제를 구현하기 위해서 4가지를 생각해보자

1. 공백리스트인 경우 -> 삭제가 불가능 해야한다.

2. 리스트가 한 개인 경우 -> 리스트를 초기화시켜버리자.

3. 공백리스트가 아니고, 삭제할 리스트가 없다면 -> 삭제가 불가능 해야한다.

4. ~(1 && 2 && 3 ) 인 경우 삭제하고, 삭제한 노드의 주소를 이전 노드에게 주자.

 

 

문제는 4의 과정을 어떻게 진행할 것인가?

강의에서는 이렇게 이야기 한다.

노드 pre의 다음주소 pre.link를 포인터 old에 저장하여 포인터 old가 다음 노드를 가리키게 한다.

뭔소리야?

 

그러니까

우리는 삭제를 할 때 

시작점을 가리키는 변수와, 삭제하고 싶은 노드를 입력할 것이다.

(삭제하고 싶은 노드는 탐색으로 찾아야한다.)

 

그러면 삭제하고 싶은 노드의 이전 노드를 pre라 하고

삭제하고 싶은 노드를 old라고 했을 때

이전 노드(pre)가 가리키는 주소를 old가 가리키는주소로 하여 pre가 곧 old의 다음 노드를 가리키게 한다.

 

그러면 deleteNode를 작성해보자.

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

// 노드
typedef struct Node {
	int value;
	struct Node* link;
}; 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->link;
		if (p != NULL) printf(", ");
	}
	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->link;
		free(temp);
		temp = NULL;
	}
}

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

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

	Node* temp;
	newNode->link = NULL;

	if (L->head == NULL) {
		L->head = newNode;
		return;
	}

	temp = L->head;
	while (temp->link != NULL)
		temp = temp->link;
	temp->link = newNode;
}

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

	if (L == NULL) {
		newNode->link = NULL;
		L->head = newNode;
	}

	else if (pre == NULL)
		L->head = newNode;

	else {
		newNode->link = pre->link;
		pre->link = newNode;
	}
}


Node* SearchNode(Start* L, int Xvalue) {
	Node* temp;
	temp = L->head;
	while (temp != NULL) {
		if (temp->value == Xvalue)
			return temp;
		else
			temp = temp->link;
	}

	return temp;
}

void deleteNode(Start* L, Node* p) {
	// 이전의 값을 가지게 할 노드
	Node* pre;
	// 만약 공백리스트라면 
	if (L->head == NULL) {
		printf("삭제할 리스트가 없습니다.");
		return;
	}
	// 만약 리스트가 한개라면
	if (L->head->link == NULL) {
		freeLinkedList(L);
	}

	// 입력받은 노드가 없다면
	else if(p == NULL){
		printf("삭제할 리스트가 없습니다.");
		return;
	}

	// 위 3가지 경우가 아닌 경우
	else {
		pre = L->head;  // 우선 시작점을 주고
		while (pre->link != p) // 삭제할 노드를 가리킬때까지 돌자
			pre = pre->link;
		// 노드를 가리킨다면 다음 노드의 주소값을 받고, free 해주자.
		pre->link = p->link;
		free(p);
	}
}


void insertSituation(Start* L) {
	printList(L);
	printf("삽입할 위치는 1. 처음, 2. 중간, 3. 끝 ->");
	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;

	case 3:
		printf("처음에 삽입합니다. 삽입할 자리의 값을 입력하세요. -> ");
		scanf("%d", &insert);
		insertLastNode(L, insert);
		break;
	}
}


void deleteCal(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("----연결 리스트 구현하기----");

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

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

		case 2:
			deleteCal(L);
			break;

		case 3:
			freeLinkedList(L);
			break;

		case 4:

			break;
		}
	}

	

}

 

거의 다 왔다. 이제 잘 수 있다.

 

---

4. 역순으로 저장을 해버리고 싶다구요.

---

역순으로 저장을 하고 싶다.

어떤 방식을 사용해야 할까?

 

우리는 끝노드을 모른다. 그렇기 때문에

끝에 삽입을 할 때도 temp를 이용해 끝노드을 찾았다.

 

그러면 temp를 이용해 끝노드을 찾았다고 치자.

시작점(L)이 끝노드를 가리키게 한다.

 

그럼 C가 B를 가리키게 하는 것을 어떻게 구현할 것인가?

코드는 다음과 같다.

void reverseNode(Start* L) {
	Node* p;
	p = L->head;

	Node* q;
	q = NULL;

	Node* r;
	r = NULL;

	while (p != NULL) {
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}

	L->head = q;
}

코드의 설명은 아래와 같다.

(교재를 참고하였으나, 이걸 어캐 만들었는지 대단..)

 

 

결과적으로 이번 알고리즘 분석 문제의 정답은 다음과 같다.

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

// 노드
typedef struct Node {
	int value;
	struct Node* link;
}; 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->link;
		if (p != NULL) printf(", ");
	}
	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->link;
		free(temp);
		temp = NULL;
	}
}

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

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

	Node* temp;
	newNode->link = NULL;

	if (L->head == NULL) {
		L->head = newNode;
		return;
	}

	temp = L->head;
	while (temp->link != NULL)
		temp = temp->link;
	temp->link = newNode;
}

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

	if (L == NULL) {
		newNode->link = NULL;
		L->head = newNode;
	}

	else if (pre == NULL)
		L->head = newNode;

	else {
		newNode->link = pre->link;
		pre->link = newNode;
	}
}


Node* SearchNode(Start* L, int Xvalue) {
	Node* temp;
	temp = L->head;
	while (temp != NULL) {
		if (temp->value == Xvalue)
			return temp;
		else
			temp = temp->link;
	}

	return temp;
}

void deleteNode(Start* L, Node* p) {
	// 이전의 값을 가지게 할 노드
	Node* pre;
	// 만약 공백리스트라면 
	if (L->head == NULL) {
		printf("삭제할 리스트가 없습니다.");
		return;
	}
	// 만약 리스트가 한개라면
	if (L->head->link == NULL) {
		freeLinkedList(L);
	}

	// 입력받은 노드가 없다면
	else if(p == NULL){
		printf("삭제할 리스트가 없습니다.");
		return;
	}

	// 위 3가지 경우가 아닌 경우
	else {
		pre = L->head;  // 우선 시작점을 주고
		while (pre->link != p) // 삭제할 노드를 가리킬때까지 돌자
			pre = pre->link;
		// 노드를 가리킨다면 다음 노드의 주소값을 받고, free 해주자.
		pre->link = p->link;
		free(p);
	}
}




void insertSituation(Start* L) {
	printList(L);
	printf("삽입할 위치는 1. 처음, 2. 중간, 3. 끝 ->");
	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;

	case 3:
		printf("끝에 삽입합니다. 삽입할 자리의 값을 입력하세요. -> ");
		scanf("%d", &insert);
		insertLastNode(L, insert);
		break;
	}
}


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

void reverseNode(Start* L) {
	Node* preNode;
	preNode = L->head;

	Node* tempNode2;
	tempNode2 = NULL;

	Node* tempNode3;
	tempNode3 = NULL;

	while (preNode != NULL) {
		tempNode3 = tempNode2;
		tempNode2 = preNode;
		preNode = preNode->link;
		tempNode2->link = tempNode3;
	}

	L->head = tempNode2;
}



int main() {
	Start* L;

	int sel;

	L = createLinkedList();


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

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

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

		case 2:
			deleteCal(L);
			break;

		case 3:
			freeLinkedList(L);
			break;

		case 4:
			reverseNode(L);
			break;
		}
	}

	

}

 

---

단순연결리스트의 경우

각 노드가 다음 노드만을 가리키는 구조였다.

노드를 탐색하는 과정에서 바로 전에 있는 노드의 값을 알고 싶다면

 

단순연결리스트의 경우 처음부터 끝까지 탐색을 해야하지만

원형연결리스트를 사용할 경우

경우 지금 가리키고 있는 부분부터 한바퀴를 돌면 된다.

이 내용은 단순연결리스트와 크게 다른 부분이 없기 때문에

생략하도록 하겠다.

 

생각해보면 마지막 노드에 L(시작점)을 계속 링크로 저장해주면 결국 그게 원형리스트이기 때문

나중에 정말 시간이 많아지거나 실무에서 필요해진다면 도전하도록하겠다.

 

이것보다는 이중연결리스트를 한 번 만들어 보고 싶다는 생각

 

---

 

 

개인적으로 난이도가 어려운 것도 어려운 것이지만

혼자 만든다기 보다, 따라 만든 느낌이 강했습니다.

연결리스트를 구현만 하는 걸로도 꽤 난이도가 높았던거 같습니다.