![[자료구조] 연결리스트 역순 알고리즘](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FJpZGM%2FbtryFNgYmAm%2FZWVv9u5XxKQASBBTSou4yK%2Fimg.png)
노드의 구성은 data와 *next 변수로 구성되어 있다.
노드의 *next 주소 흐름은 100(head) -> 200 -> 300 -> 400 -> NULL이다.
이 흐름을 역순, 즉 반대로 400 -> 300 -> 200 -> 100 -> NULL으로 바꾸는 알고리즘을 생각하는 것이 과제이다.
반복문과 재귀함수를 이용해서 두가지 방법으로 알고리즘을 구현할 수 있었다.
1. 반복문을 이용한 알고리즘 : 앞 노드부터 흐름을 바꾸면서 뒤 노드로 진행한다.
2. 재귀함수를 이용한 알고리즘 : 노드의 끝까지 타고 들어가서 뒤 노드부터 흐름을 바꾸면서 앞 노드로 돌아온다.
1. 반복문을 이용한 연결리스트 역순 알고리즘
처음으로 생각하게 된 알고리즘은 앞 노드부터 한 칸씩 *next 포인터를 역순으로 설정해주는 알고리즘이다.
가장 먼저 신경쓴 것은 100주소에 있는 포인터 변수 next이다.
역순으로 바꾸게 되면 100이 마지막 노드가 될 것이기 때문에 다음 노드의 주소는 NULL이 되므로, 200에서 NULL로 설정되면서 시작되어야 한다.
q의 초깃값이 NULL이라고 했을 때, 이 값을 p.next에 넣어주면 되지만, 이 것을 먼저 수행하게 되면 200 주소의 노드로 접근하는 포인터가 끊기게 된다.
그래서 q의 주소를 잠시 r에 저장시켜두고, p를 다음 노드로 전진시킬 것이다.
ex)
r=q;
p=p->next;
이때, 포인터 p의 값이 200이 된다면, 100 주소에 있는 포인터 next의 값을 바꿔줄 수 없다.
그래서 p가 전진하게 이전에 q로 100의 노드를 지정해두고 p가 다음 노드로 진행하여 200의 값을 얻을 수 있게 한다.
ex)
r=q;
q=p;
p=p->next;
r에 저장된 값은 100의 next에 넣어야 할 주소가 되고, 이 100은 q가 가르키고 있다. 이 상황에서 p는 다음 노드, 즉 200을 가르키고 있는 상황이 된다.
이제 q->next의 값에 200이 아닌 NULL로 흐름을 바꿔도 p는 이미 다음노드로 전진해 있기 때문에 흐름이 끊기지 않는다.
ex)
r=q;
q=p;
p=p->next;
q.next=r;
이 반복문을 계속 수행하고 p->next가 NULL이라면 반복문을 종료하면 모든 리스트의 흐름이 역순으로 바꿔져 있을 것이다. 아래 사진은 다음 과제를 예시로 들어서 반복문의 회차 별로 종료된 후 리스트의 상황을 정리한 사진이다.
리스트의 흐름이 역순으로 바뀐 것을 볼 수 있다. 알고리즘 흐름이 확실한지 확인하기 위해 코드로 구현해볼 것이다.
#include<stdio.h>
typedef struct node {
int data;
struct node* next;
} node;
int main() {
struct node node1;
struct node node2;
struct node node3;
struct node node4;
node1.data = 1;
node2.data = 2;
node3.data = 3;
node4.data = 4;
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = NULL;
node* p = &node1;
node* q = NULL;
node* r = NULL;
printf("node1 addr : %p | node1->data : %d | node1->next : %p\n",&node1 ,node1.data, node1.next);
printf("node2 addr : %p | node2->data : %d | node2->next : %p\n",&node2 ,node2.data, node2.next);
printf("node3 addr : %p | node3->data : %d | node3->next : %p\n",&node3 ,node3.data, node3.next);
printf("node4 addr : %p | node4->data : %d | node4->next : %p\n",&node4 ,node4.data, node4.next);
while (p != NULL) {
r = q;
q = p;
p = p->next;
q->next = r;
}
printf("\n\n");
printf("node1 addr : %p | node1->data : %d | node1->next : %p\n", &node1, node1.data, node1.next);
printf("node2 addr : %p | node2->data : %d | node2->next : %p\n", &node2, node2.data, node2.next);
printf("node3 addr : %p | node3->data : %d | node3->next : %p\n", &node3, node3.data, node3.next);
printf("node4 addr : %p | node4->data : %d | node4->next : %p\n", &node4, node4.data, node4.next);
}예제코드에서는 data를 각각 1, 2, 3, 4로 주고, 반복문이 수행하기 전 연결리스트의 흐름과, 수행한 후의 흐름을 출력했다.
실행 결과를 보면 각 노드의 next값의 주소와 각 노드의 addr의 값을 보면서 따라가게 되면 흐름이 역순으로 바뀐 것을 확인할 수 있다.
2. 재귀함수를 이용한 연결리스트 역순 알고리즘
두번째 알고리즘이다. recursion이라는 재귀함수를 선언하여 노드의 끝까지 들어가게 된 후, 뒤에서 부터 노드의 next 포인터를 바꾸면서 돌아온다.
recursion 안의 또 다른 재귀 recursion을 호출할 때는 현재 노드의 다음노드와 다음다음노드의 주소를 넘겨준다.
이 알고리즘에서 변수의 역할을 확인하면 p는 이전 노드의 주소를 기억할 것이고, q는 현재 노드 기준으로 다음 노드가 NULL 값인지 확인하고, 마지막 r은 첫 head 노드인지 확인하게 된다.
만약 p와 r이 같다면 head 노드였다는 것이 확인되므로 r->next 값에 NULL을 넣어주면 된다.
반복문을 사용한 것과 같은 예시로, 반복문 대신에 recursion 함수만 추가하여 코드를 실행시킬 것이다.
#include<stdio.h>
typedef struct node {
int data;
struct node* next;
} node;
void recursion(node* p, node* q, node* r) {
if (q->next == NULL) {
q->next = p;
return;
}
recursion(q, q->next, r);
q->next = p;
if (p == r)r->next = NULL;
return;
}
int main() {
struct node node1;
struct node node2;
struct node node3;
struct node node4;
node1.data = 1;
node2.data = 2;
node3.data = 3;
node4.data = 4;
node1.next = &node2;
node2.next = &node3;
node3.next = &node4;
node4.next = NULL;
node* p = &node1;
printf("node1 addr : %p | node1->data : %d | node1->next : %p\n",&node1 ,node1.data, node1.next);
printf("node2 addr : %p | node2->data : %d | node2->next : %p\n",&node2 ,node2.data, node2.next);
printf("node3 addr : %p | node3->data : %d | node3->next : %p\n",&node3 ,node3.data, node3.next);
printf("node4 addr : %p | node4->data : %d | node4->next : %p\n",&node4 ,node4.data, node4.next);
recursion(p, p->next, p);
printf("\n\n");
printf("node1 addr : %p | node1->data : %d | node1->next : %p\n", &node1, node1.data, node1.next);
printf("node2 addr : %p | node2->data : %d | node2->next : %p\n", &node2, node2.data, node2.next);
printf("node3 addr : %p | node3->data : %d | node3->next : %p\n", &node3, node3.data, node3.next);
printf("node4 addr : %p | node4->data : %d | node4->next : %p\n", &node4, node4.data, node4.next);
}
위 출력 4줄은 recursion 함수가 실행되기 전에 각 노드의 값들이며, 아래 출력 4줄은 recursion이 모두 수행된 후에 각 노드의 값들이다. 노드의 next주소와 addr주소를 확인하면 각 노드의 흐름들이 역순으로 바뀐 것을 확인할 수 있다.