[C언어]구조체로 이중연결리스트 정렬 구현

구조체를 사용한 이중연결리스트 정렬 구현

데이터 push와 pop이 용이하다는 장점이 있어서 Dummy Node를 포함한 이중 연결리스트를 생성했다.

1. 구조체 선언

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
}Node;


typedef struct List {
    int count;
    Node* head;
    Node* tail;
    bool sorted;
}List;

구현에 목적을 두기 위해 정수형 데이터 한 개만 포함하는 노드를 선언했고,
더미노드를 사용하기 위해 리스트 구조체는 head, tail을 포함해서 선언했다.
리스트의 크기를 저장하는 count변수도 포함했다. 탐색할 때 정렬이 되어있는지
확인하기 위해 stdbool 라이브러리를 추가하고 리스트 구조체에 sorted를
추가했다.

2. 노드, 리스트 초기화 함수

List* initList(int data) {
    List* new_list = (List*)malloc(sizeof(List));

    //new_list의 head와 tail에 dummy node 생성
    new_list->head = createNewNode(0);
    new_list->tail = createNewNode(0);

    //head와 tail포인터 연결
    new_list->head->next = new_list->tail;
    new_list->tail->prev = new_list->head;

    //크기가 0이고 정렬되지 않은 상태
    new_list->count = 0;
    new_list->sorted = false;

    return new_list;
}


Node* createNewNode(int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));

    //shem 구조체에 데이터 저장, 포인터 초기화
    new_node->data = data;
    new_node->next = new_node->prev = NULL;

    return new_node;
}

리스트 구조체에 더미 노드를 생성하고 head와 tail 노드의 포인터가
서로를 가리키게 연결해줬다. 이 경우 push나 pop을 할 때 새로운 노드를
직관적으로 다루기가 쉬워진다.

3. push 함수

void pushToTail(List* list, int data) {
    Node* now_node = createNewNode(data);

    now_node->next = list->tail;
    now_node->prev = list->tail->prev;

    list->tail->prev->next = now_node;
    list->tail->prev = now_node;

    //크기가 1 증가하고 정렬되지 않은 상태
    list->count++;
    list->sorted = false;
}


void pushToHead(List* list, int data) {
    Node* now_node = createNewNode(data);

    now_node->prev = list->head;
    now_node->next = list->head->next;

    list->head->next->prev = now_node;
    list->head->next = now_node;

    //크기가 1 증가하고 정렬되지 않은 상태
    list->count++;
    list->sorted = false;
}

push함수는 비교적 간단하게 만들 수 있다.
리스트 구조체의 head와 tail부분에 모두 push할 수 있도록 함수를
두 종류를 만들었고, 리스트의 포인터를 파라미터로 정해서 반환값이
없도록 만들었다.

4. pop 함수

int popFromTail(List* list){
    if (isNull(list) == true){
        puts("List Empty!");
        return -1;
    }

    Node* pop_node = list->tail->prev;
    int data = pop_node->data;

    //노드 연결 해제, 노드 제거
    pop_node->prev->next = list->tail;
    list->tail->prev = pop_node->prev;
    free(pop_node);

    list->count--;
    return data;
}


int popFromHead(List* list){
        if (isNull(list) == true){
        puts("List Empty!");
        return -1;
    }

    Node* pop_node = list->head->next;
    int data = pop_node->data;

    //노드 연결 해제, 노드 제거
    pop_node->next->prev = list->head;
    list->head->next = pop_node->next;
    free(pop_node);

    list->count--;
    return data;
}

5. timSort 함수

#. print 함수

void printList(List* list) {
    //List의 haed에서 시작
    Node* now_node = list->head;

    //head와 tail 노드 제외하고 print
    do {
        now_node = now_node->next;
        printf("%d ", now_node->data);
    } while (now_node->next->next); 
}

print할 때 head와 tail 노드는 buffer node이므로 제외하고 프린트했다.

source code