[자료구조] Swapping nodes in a singly linked list without swapping data- review

https://www.javatpoint.com/program-to-swap-nodes-in-a-singly-linked-list-without-swapping-data

Program To Swap Nodes In A Singly Linked List Without Swapping Data - javatpoint

singly linked list에서 node의 데이터값을 바꾸지 않고 두 node를 swap하는 알고리즘입니다.

 

본 알고리즘 코드를 리뷰하기 전에 혼자 코드를 짜봤습니다.

2개의 node 포인터(temp_1,temp_2)를 선언하여 바꾸고자 하는 데이터값이 있는 노드를 point하고

또 다른 2개의 node 포인터(prev_1,prev_2)를 선언하여 위의 node의 이전 node를 point하게 하고

(이전의 node란 singly linked list에서 해당 노드를 next로 point하고 있는 node를 의미합니다.)

각 node 포인트를 바꿀 때 필요한 sub pointer(temp)를 하나 더 선언하는 것으로,

총 5개의 node 포인터를 이용하는 측면은 원문의 코드와 같았습니다.

 

위와 같은 개념으로 알고리즘을 짜고 세부코드를 짜면서 오류가 생겼고 원문 코드를 보고 이를 수정하면서 저의 부족함을 많이 느꼈습니다.

 

선언한 struct는 다음과 같습니다.

struct node{

        int data;

        struct node* next

}

    struct node *temp_1 = head;
    struct node *temp_2 = head;
    struct node *prev_1 = NULL;
    struct node *prev_2 = NULL;
    struct node *temp = NULL;

 

첫번째,

 

node포인터를 선언하고 인수로 받은 데이터값을 가지고 있는 node와 그 이전의 node를 포인트하는 과정을 저는 아래와 같이 코딩했습니다.

 

temp_1가 linked list의 head를 point하는 상황에서, 위의 첫번째 if문에서 temp_1의 데이터와 찾고자하는 데이터 n1의 일치성을 따져보고 prev_1를 temp_1로,  temp_1는 temp_1->next로 point를 변경해준 다음.

while 문으로 들어가서 temp_1가 가르키는 노드의 데이터 값이 n1와 일치하거나 NULL이 아닌 동안 계속 loop를 돌렸습니다.

 

원문을 보니 아래와 같이 while문으로 한 번에 위의 과정을 수행했습니다.

두개의 포인터가 나란히 따라가는 상황에서 훨씬 간결하게 코딩할 수 있음을 깨달았습니다.

저의 별볼일없는 코딩능력에 또 한 번 감탄하였고 앞으로 계속 겸손하자는 마인드로 기록에 남깁니다.

 

두 번째,

 

두개의 node를 swap할 때 노드가 head일 경우 head pointer도 바꿔줘야하는 상황이었습니다.

제가 처음 짠 코드는 아래와 같습니다.

temp_1와 temp_2가 각각 head인지 따지고 둘 중 하나가 head이면 head를 그 반대인 다른 노드에 point하게끔 하려고 했습니다.

그 이후 두 노드를 swap하기 위해 각 노드 앞뒤로 연결되어 있는 point들을 수정하는 과정에서

prev_1->next=temp_2->next

를 통해 prev_1->next에 접근하는 코드를 짰는데 여기서 문제점이 발견됐습니다.

 

temp_1가 head가 아닌 경우에는 prev_1가 특정 node를 point하고 있어 prev_1->next에 접근하는 것이 가능하지만,

temp_1가 head인 경우에는 prev_1의 point 값이 NULL이기 때문에 접근할 때 segment error가 발생했습니다.

 

원문에서는 아래와 같이 코드를 짰습니다.

 

temp_1가 head인지를 직접적으로 따지는 것이 아니라

prev_1의 값이 NULL이면 head가 temp_1를 point하고 있는 것이니,

if(prev_1!=NULL) 즉 temp_1가 head가 아니면 prev_1도 특정 node를 point하고 있으니 prev_1->next 값에 접근하여 point를 수정해주는 방식으로 진행했습니다.

 

저의 문제점을 정확하게 심플한 방법으로 해결한 코드였습니다.

 

오늘의 배운점

1.

2.

 

추후 수정하여 업로드할것임.