1. 기초 데이터 타입 및 상태 코드 정의

연산의 성공, 실패, 메모리 할당 오류 등의 상태를 명확하게 처리하기 위해 열거형(enum)을 활용한 상태 코드를 정의합니다. 또한, 노드에 저장될 데이터의 타입을 별도로 지정하여 추후 확장성을 높입니다.

#ifndef COMMON_DEFS_H
#define COMMON_DEFS_H

#include <stdio.h>
#include <stdlib.h>

typedef enum {
    OP_SUCCESS = 0,
    OP_FAILURE = -1,
    MEM_ALLOC_ERR = -2
} OperationStatus;

typedef int DataType;

#endif

2. 양방향 연결 리스트 구조체 설계

양방향 연결 리스트는 이전 노드와 다음 노드를 모두 가리킬 수 있도록 포인터 두 개를 포함하는 노드 구조체가 필요합니다. 또한, 리스트 전체를 관리하기 위해 머리(Head)와 꼬리(Tail) 포인터, 그리고 현재 요소의 개수를 추적하는 구조체를 정의합니다.

typedef struct DoublyNode {
    DataType value;
    struct DoublyNode* prev;
    struct DoublyNode* next;
} DoublyNode;

typedef struct DoublyLinkedList {
    DoublyNode* head;
    DoublyNode* tail;
    int size;
} DoublyLinkedList;

3. 핵심 기능 구현

리스트의 초기화, 노드 삽입 및 삭제, 그리고 양방향 순회 기능을 구현합니다. 기존에 더미 노드를 사용하던 방식에서 벗어나, 실제 데이터 노드만을 연결하여 메모리 효율을 높이고 포인터 조작 로직을 명확하게 개선했습니다.

// 리스트 초기화
OperationStatus initDList(DoublyLinkedList** list) {
    *list = (DoublyLinkedList*)malloc(sizeof(DoublyLinkedList));
    if (*list == NULL) return MEM_ALLOC_ERR;
    
    (*list)->head = NULL;
    (*list)->tail = NULL;
    (*list)->size = 0;
    return OP_SUCCESS;
}

// 새 노드 생성
DoublyNode* createNode(DataType val) {
    DoublyNode* newNode = (DoublyNode*)malloc(sizeof(DoublyNode));
    if (newNode == NULL) return NULL;
    newNode->value = val;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 특정 인덱스에 노드 삽입 (0-based index)
OperationStatus insertDList(DoublyLinkedList* list, int index, DataType val) {
    if (index < 0 || index > list->size) return OP_FAILURE;
    
    DoublyNode* newNode = createNode(val);
    if (!newNode) return MEM_ALLOC_ERR;
    
    if (list->size == 0) {
        list->head = newNode;
        list->tail = newNode;
    } else if (index == 0) {
        newNode->next = list->head;
        list->head->prev = newNode;
        list->head = newNode;
    } else if (index == list->size) {
        newNode->prev = list->tail;
        list->tail->next = newNode;
        list->tail = newNode;
    } else {
        DoublyNode* current = list->head;
        for (int i = 0; i < index; i++) {
            current = current->next;
        }
        newNode->prev = current->prev;
        newNode->next = current;
        current->prev->next = newNode;
        current->prev = newNode;
    }
    list->size++;
    return OP_SUCCESS;
}

// 특정 인덱스의 노드 삭제
OperationStatus removeDList(DoublyLinkedList* list, int index, DataType* outVal) {
    if (index < 0 || index >= list->size || list->size == 0) return OP_FAILURE;
    
    DoublyNode* target = NULL;
    if (index == 0) {
        target = list->head;
        list->head = target->next;
        if (list->head) list->head->prev = NULL;
        else list->tail = NULL;
    } else if (index == list->size - 1) {
        target = list->tail;
        list->tail = target->prev;
        if (list->tail) list->tail->next = NULL;
        else list->head = NULL;
    } else {
        target = list->head;
        for (int i = 0; i < index; i++) {
            target = target->next;
        }
        target->prev->next = target->next;
        target->next->prev = target->prev;
    }
    
    *outVal = target->value;
    free(target);
    list->size--;
    return OP_SUCCESS;
}

// 정방향 순회 및 출력
void printForward(DoublyLinkedList* list) {
    DoublyNode* curr = list->head;
    printf("Head -> ");
    while (curr != NULL) {
        printf("[%d] -> ", curr->value);
        curr = curr->next;
    }
    printf("Null\n");
}

// 역방향 순회 및 출력
void printBackward(DoublyLinkedList* list) {
    DoublyNode* curr = list->tail;
    printf("Tail -> ");
    while (curr != NULL) {
        printf("[%d] -> ", curr->value);
        curr = curr->prev;
    }
    printf("Null\n");
}

4. 테스트 및 실행 결과

구현된 양방향 연결 리스트의 동작을 검증하기 위해 데이터를 삽입하고, 중간에 요소를 추가 및 삭제한 뒤 정방향과 역방향으로 순회하는 테스트 코드를 작성합니다.

int main() {
    DoublyLinkedList* myList;
    if (initDList(&myList) != OP_SUCCESS) {
        printf("메모리 할당 실패\n");
        return -1;
    }

    // 초기 데이터 삽입
    for (int i = 10; i <= 50; i += 10) {
        insertDList(myList, myList->size, i);
    }

    printf("초기 상태 정방향 순회:\n");
    printForward(myList);
    printf("초기 상태 역방향 순회:\n");
    printBackward(myList);

    // 중간 삽입 테스트
    insertDList(myList, 2, 99);
    printf("\n인덱스 2에 99 삽입 후 정방향 순회:\n");
    printForward(myList);

    // 삭제 테스트
    DataType removedVal;
    removeDList(myList, 4, &removedVal);
    printf("\n인덱스 4의 요소(%d) 삭제 후 역방향 순회:\n", removedVal);
    printBackward(myList);

    return 0;
}

위 코드를 컴파일하고 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.

초기 상태 정방향 순회:
Head -> [10] -> [20] -> [30] -> [40] -> [50] -> Null
초기 상태 역방향 순회:
Tail -> [50] -> [40] -> [30] -> [20] -> [10] -> Null

인덱스 2에 99 삽입 후 정방향 순회:
Head -> [10] -> [20] -> [99] -> [30] -> [40] -> [50] -> Null

인덱스 4의 요소(40) 삭제 후 역방향 순회:
Tail -> [50] -> [30] -> [99] -> [20] -> [10] -> Null