이중 연결리스트(Doubly linked list)
지난 시간에 알아본 단일 연결리스트는 단방향으로 연결되어 있었다.
이번 시간에 구현해 볼 이중 연결리스트는 단일 연결리스트의 단점인 단방향의 흐름을 보완하여 양방향으로 움직일 수 있다.
장점 : prev노드가 있어 한 노드가 다음 노드와 이전 노드를 모두 접근할 수 있다. 삽입, 삭제 연산 시 선행 노드에 대한 정보가 필요없다.
단점 : 이전 노드를 지정해줘야 하므로 변수를 추가해줘야 한다. 따라서 메모리를 더 많이 사용하고 구현이 복잡하다.
이중 연결리스트의 구조
next를 통해 단 방향으로만 연결되어 있던 단일 연결리스트와는 달리 prev를 추가하여 자신의 이전 노드와 연결할 수 있다.
이중 연결리스트 구현
head rear노드 생성
먼저 노드의 시작과 끝을 가리킬 head노드와 rear노드를 선언해야 한다.
이해를 쉽게 하기 위해 전역변수로 선언하였다.
노드 생성
노드의 생성은 먼저 newNode에 동적할당을 해준다.
data값을 입력하여 newNode->value값에 저장하고 newNode->next와 newNode->prev를 NULL로 초기화 시켜준 뒤 생성해준 newNode의 주소값을 반환하여준다.
노드 맨 앞 추가
먼저 newNode에 동적할당을 해준 뒤 만약 노드가 없다면 head와 rear을 newNode에 연결 후 return하여 준다. 만약 노드가 있다면 newNode->next를 head를 가리키게 하고 head의 head->prev를 newNode와 연결시켜준다. 그리고 head는 이제 newNode를 가리키게 한다.
노드 맨 뒤 추가
맨 앞 추가와 동일하지만 rear->next에 newNode를 추가하고 newNode->prev에 마지막 노드였던 rear노드를 연결한다. 그리고 rear은 다시 마지막에 들어온 newNode를 가리키게 한다.
노드 n번째 삽입
이해를 위해 몇 가지 케이스를 분류하여 보았다.
1. 먼저 head가 NULL이면 리스트 생성 전이므로 종료한다.
그리고 삽입할 순서를 입력받는다. 노드의 개수보다 큰 값이거나 0이하의 순서는 없으므로 유효성 체크를 해준다.
만약 n이 1이라면 위에 맨 앞 삽입과 동일하다.
맨 앞에 newNode를 추가해주고 head는 newNode를 가리키게 한다.맨 마지막에 추가하는 것은 맨 뒤 삽입과 동일하다.
마지막 노드의 next를 newNode와 연결하여주고 rear은 newNode를 가리키게 한다.가장 일반적인 경우다 맨 앞도 맨 뒤도 아닌 중간 삽입은 맨 앞부터 n번째 노드까지 이동한 후 연결하여 준다. 이 때 연결 순서에 주의해야 한다.
노드 삭제
삭제할 데이터를 입력 받는다.
만약 노드가 생성 전이면 바로 return해준다.
removeNode에 head노드를 연결하고 순회하면서 삭제할 데이터를 탐색한다. 만약 삭제할 데이터를 찾았다면
삭제할 이전 노드와 삭제할 다음 노드를 연결하여 준다. 그리고 return한다. 만약 찾지 못하였다면 계속 순회하며 삭제할 데이터를 탐색한다.
노드 출력
노드를 순회하면서 출력한다.
노드 해제
프로그램 종료 시 동적할당 한 노드들을 해제한다.
앞에서는 노드 추가, 삽입, 탐색, 삭제의 기본적인 것들만 소개하였고 여러가지 기능들은 전체 코드에 구현하여 보았다.
전체 코드
#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)
//연결리스트 체크할 부분
//1. head == NULL.
//2. 노드가 하나인 경우
//3. 일반적인 경우
//4. 검사할 노드가 마지막인 경우
typedef struct doubleList {
int value;
struct doubleList* next;
struct doubleList* prev;
}DNode;
DNode* head = NULL; // 첫 번째 노드의 주소를 저장하는 포인터(8byte)
DNode* rear = NULL;
DNode* create_node();
void insert_front_node();
void insert_rear_node();
void display();
void remove_first_node();
int get_node_count();
void insert_sort_node();
void remove_value_node();
void insert_nth_node();
void reverse();
void print_nth_node();
void memory_free();
void print_rear_nth_node();
DNode* create_node() {
DNode* newNode = (DNode*)malloc(sizeof(DNode));
printf("정수 입력 : ");
scanf("%d", &newNode->value);
while (getchar() != '\n');
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
void insert_front_node() {
DNode* newNode = create_node();
if (head == NULL) {
head = newNode;
rear = newNode;
return;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
printf("노드 맨 앞 삽입. 생성된 역순으로 삽입.\n");
return;
}
void insert_rear_node() { //시간 복잡도 O(N) -> O(1)로 바꾸기 위해 rear노드 추가
DNode* newNode = create_node();
DNode* curNode = head;
if (head == NULL) {
head = newNode;
rear = newNode;
printf("노드 맨 뒤 삽입(O(1))첫 번째 노드 삽입\n");
return;
}
rear->next = newNode;
newNode->prev = rear;
rear = newNode;
}
void display() {
DNode* curNode = head;
if (head == NULL) {
printf("연결리스트 생성 전입니다.\n");
return;
}
printf("\n\ndoublyl linked list : ");
while (curNode->next != NULL) {
printf("%d => ", curNode->value);
curNode = curNode->next;
}
printf("%d", curNode->value);
}
void remove_first_node() {
DNode* delNode = head;
if (head == NULL) {
return;
}
head = head->next;
printf("%d노드 삭제\n", delNode->value);
free(delNode);
if (head != NULL) {
head->prev = NULL;
}
}
int get_node_count() {
int cnt = 0;
DNode* curNode = head;
while (curNode) {
curNode = curNode->next;
cnt++;
}
return cnt;
}
void insert_sort_node() {
DNode* curNode = head;
DNode* newNode = create_node();
if (head == NULL) {
head = newNode;
rear = newNode;
printf("[정렬삽입]case 1.노드가 비어있는 경우\n");
}
if (newNode->value < head->value) {
newNode->next = head;
head->prev = newNode;
head = newNode;
printf("[정렬삽입]case 2. 가장 작은 값 삽입한 경우\n");
return;
}
while (curNode->next != NULL) {
curNode = curNode->next;
if (newNode->value < curNode->value) { //newNode부터 연결하지 않으면 값이 엉킴
newNode->prev = curNode->prev;
newNode->next = curNode;
curNode->prev->next = newNode;
curNode->prev = newNode;
printf("[정렬삽입]case 3. 일반적인 경우\n");
return;
}
}
printf("[정렬삽입]case 4. 가장 큰 값을 삽입한 경우\n");
curNode->next = newNode;
newNode->prev = curNode;
}
void remove_value_node() {
int data;
printf("삭제할 값 입력 : ");
scanf("%d", &data);
if (!head) {
printf("노드 생성 전!\n");
return;
}
DNode* removeNode = head;
while (removeNode) {
if (removeNode->value == data) {
removeNode->prev->next = removeNode->next;
removeNode->next->prev = removeNode->prev;
free(removeNode);
return;
}
removeNode = removeNode->next;
}
printf("삭제할 데이터가 없습니다!\n");
return 0;
}
void insert_nth_node() {
DNode* newNode = create_node();
DNode* curNode = head;
int n, i;
if (!head) {
printf("리스트 생성 전!\n");
printf("case 1. head가 NULL\n");
return;
}
do {//n번째 범위 유효성 체크
printf("몇 번째 넣을까요? : ");
scanf("%d", &n);
} while (n > get_node_count() + 1 || n < 1);
if (n == 1) {
newNode->next = head;
head->prev = newNode;
head = newNode;
printf("case 2. 첫 번째 삽입(head값 변경)\n");
return;
}
if (n == get_node_count() + 1) {
rear->next = newNode;
newNode->prev = rear;
rear = newNode;
printf("case 3. 마지막 삽입\n");
return;
}
for (i = 1; i < n; i++)
curNode = curNode->next;
newNode->prev = curNode->prev;
newNode->next = curNode;
curNode->prev->next = newNode;
curNode->prev = newNode;
printf("case 4. 일반적인 경우\n");
return;
}
void reverse() {
DNode* curNode = head;
DNode* temp;
if (head == NULL || head->next == NULL) //노드가 없거나 한 개인 경우
return;
while (curNode != NULL) {
temp = curNode->prev;
curNode->prev = curNode->next;
curNode->next = temp;
if (curNode->prev == NULL) {
head = curNode; // 마지막 노드로 변경
printf("\n\n\t\t역순 연결됐습니다.\n");
return;
}
curNode = curNode->prev; // cur와 prev 스왑했으므로 다음 노드 접근은 prev
}
}
void print_nth_node() {
DNode* curNode = head;
int n, i;
if (!head) {
printf("리스트 생성 전!\n");
return;
}
do {
printf("몇 번째 노드 출력 ? ");
scanf("%d", &n);
} while (n < 1 || get_node_count() < n);
for (i = 1; i < n; i++) {
curNode = curNode->next;
}
printf("%d번째 노드 값 : %d\n", n, curNode->value);
return;
}
void print_rear_nth_node() {
int n, i;
rear = head;
if (!rear) {
printf("리스트 생성 전!\n");
return;
}
do {
printf("뒤에서 몇 번째 노드 출력 ? ");
scanf("%d", &n);
} while (n < 1 || get_node_count() < n);
while (rear->next)
rear = rear->next;
for (i = 1; i < n; i++) {
rear = rear->prev;
}
printf("%d번째 노드 값 : %d\n", n, rear->value);
return;
}
void memory_free() {
DNode* delNode = head;
if (head == NULL) {
printf("리스트 생성 전!\n");
return;
}
while (head != NULL) {
head = head->next;
printf("%d노드를 해제합니다.\n", (*delNode).value);
free(delNode);
delNode = head;
}
return;
}
int main() {
int choice;
while (1) {
system("cls");
printf("\n\n***이중 연결 리스트(doubly linked list) ***\n");
printf("1. 노드 맨 앞 삽입\n"); //
printf("2. 노드 맨 뒤 삽입\n"); //
printf("3. 정렬 삽입\n"); //
printf("4. k번째 삽입\n");
printf("5. 리스트 출력\n"); //
printf("6. 첫 번째 노드 삭제\n"); //
printf("7. 특정 값 노드 삭제\n");
printf("8. 역순 연결\n");
printf("9. 노드의 개수 구하기\n"); //
printf("10. k번째 노드 출력\n");
printf("11. 뒤에서 k번째 노드 출력\n");
printf("0. 프로그램 종료\n"); //
printf("\n\n메뉴 선택 : [ ]\b\b");
scanf("%d", &choice);
while (getchar() != '\n');
switch (choice) {
case 1:
insert_front_node();
break;
case 2:
insert_rear_node();
break;
case 3:
insert_sort_node();
break;
case 4:
insert_nth_node();
break;
case 5:
display();
break;
case 6:
remove_first_node();
break;
case 7:
remove_value_node();
break;
case 8:
reverse();
break;
case 9:
printf("\n\n\t\t생성된 노드의 개수 : %d개\n", get_node_count());
break;
case 10:
print_nth_node();
break;
case 11:
print_rear_nth_node();
break;
case 0:
memory_free();
exit(0); //프로그램 종료
}
printf("\n\n\t\t");
system("pause");
}
return 0;
}
뒤돌아보면 남는 것은 사진, 그리고 기록 뿐