12304. 기초 Double Linked List 연습

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: SW Expert Academy)

노드를 정적 할당하여 Double-linked list를 구현하는 문제.
head 혹은 각 노드의 prev나 next가 nullptr 일 경우에 대한 처리가 은근히 신경써야했던 부분이었다.

#define MAX_NODE 10000

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

Node node[MAX_NODE];
int nodeCnt;
Node *head;

Node *getNode(int data)
{
    node[nodeCnt].data = data;
    node[nodeCnt].prev = nullptr;
    node[nodeCnt].next = nullptr;
    return &node[nodeCnt++];
}

void init()
{
    nodeCnt = 0;
    head = nullptr;
}

void addNode2Head(int data)
{
    Node *newNode = getNode(data);
    newNode->next = head;
    if (newNode->next != nullptr)
    {
        newNode->next->prev = newNode;
    }
    head = newNode;
}

void addNode2Tail(int data)
{
    if (head == nullptr)
    {
        addNode2Head(data);
        return;
    }
    Node *newNode = getNode(data);
    Node *tailNode = head;
    while (tailNode->next != nullptr)
    {
        tailNode = tailNode->next;
    }
    tailNode->next = newNode;
    newNode->prev = tailNode;
}

void addNode2Num(int data, int num)
{
    if (num == 1)
    {
        addNode2Head(data);
        return;
    }
    Node *newNode = getNode(data);
    Node *prevNode = head;
    for (int i = 2; i < num; i++)
    {
        prevNode = prevNode->next;
    }
    Node *nextNode = prevNode->next;
    newNode->next = nextNode;
    newNode->prev = prevNode;
    prevNode->next = newNode;
    if (nextNode != nullptr)
    {
        nextNode->prev = newNode;
    }
}

int findNode(int data)
{
    Node *currNode = head;
    int num = 1;
    while (currNode->data != data)
    {
        currNode = currNode->next;
        num++;
    }
    return num;
}

void removeNode(int data)
{
    Node *currNode = head;
    while (currNode != nullptr)
    {
        if (currNode->data == data)
        {

            if (currNode->prev != nullptr)
            {
                currNode->prev->next = currNode->next;
            }
            else
            {
                head = currNode->next;
            }
            if (currNode->next != nullptr)
            {
                currNode->next->prev = currNode->prev;
            }
            return;
        }
        currNode = currNode->next;
    }
}

int getList(int output[MAX_NODE])
{
    Node *currNode = head;
    int i = 0;
    while (currNode != nullptr)
    {
        output[i] = currNode->data;
        currNode = currNode->next;
        i++;
    }
    return i;
}

int getReversedList(int output[MAX_NODE])
{
    if (head == nullptr)
    {
        return 0;
    }
    Node *currNode = head;
    while (currNode->next != nullptr)
    {
        currNode = currNode->next;
    }
    int i = 0;
    while (currNode != nullptr) {
        output[i] = currNode->data;
        currNode = currNode->prev;
        i++;
    }
    return i;
}