[자료구조] sorting the element of the doubly linked list (feat.for loop)

참고자료

https://www.javatpoint.com/program-to-sort-the-elements-of-the-doubly-linked-list

Program to Sort the Elements of the Doubly Linked List - javatpoint

Data structure를 공부하며 node를 swap하는 것에 익숙해진 상황이었다.

그래서인지 Doubly linked list의 원소들을 오름차순으로 sort하는 알고리즘을 짤 때도 data를 변경하는 방식이 아닌 node를 swap하는 방식으로 시도했다.

이것은 나의 실수이다. 코드가 훨씬 복잡해지기 때문이다.

 

Doubly Linked List

위와 같이 각 노드가 previous, next pointer로 연결된 Doulby linked list가 있다고 하면,

 

1. node를 swap하여 sort하게 되면

아래와 같이 각 node의 previous와 next pointer를 수정하고,  각 노드가 head 혹은 tail 인 경우 이를 수정해야 한다.

void sort(){
    struct node *current = head;
    struct node *cur_temp = NULL;
    int temp = 0;
    
    if(head==NULL){
        return;
    }
    
    while(current->next!=NULL){
        cur_temp=current->next;
        while(cur_temp!=NULL){
            if(current->data > cur_temp->data){
                current->next = cur_tmep->next;
                cur_tmep->next = current->next;
                cur_tmep->previous = current->previous;
                current->previous = cur_tmep->previous;
                //exception
                if(current==head){
                    head==cur_temp;
                }
                if(cur_temp==tail){
                    tail=current;
                }
            }
            cur_temp=cur_temp->next;
        }
        current=current->next;
    }
}