[c++] 배열과 포인터를 사용한 이중 연결 리스트 구현

14 Dec 2023

배열과 포인터를 사용하여 이중 연결 리스트를 구현할 수 있습니다. 이중 연결 리스트는 각 노드가 다음 노드뿐만 아니라 이전 노드를 가리키는 특징을 갖고 있어 효과적으로 데이터를 삽입, 삭제할 수 있습니다.

필요한 자료 구조

이중 연결 리스트를 구현하기 위해 노드 구조체를 정의하고, 배열과 포인터를 활용하여 리스트를 관리합니다.

#include <iostream>
using namespace std;

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

Node nodeList[100]; // 최대 100개의 노드를 담을 배열

Node* head = nullptr; // 리스트의 시작을 가리키는 포인터
Node* tail = nullptr; // 리스트의 끝을 가리키는 포인터

int nodeCount = 0; // 리스트에 존재하는 노드의 개수

위 코드에서 Node 구조체는 데이터를 저장하기 위한 data 변수와 이전 노드와 다음 노드를 가리키는 포인터를 포함하고 있습니다. 또한, 최대 100개의 노드를 담을 수 있는 배열과 리스트의 시작과 끝을 가리키는 포인터, 그리고 리스트에 존재하는 노드의 개수를 관리하는 변수도 정의되어 있습니다.

노드의 삽입

void insertNode(int newData, Node* prevNode) {
    nodeCount++;
    nodeList[nodeCount].data = newData;

    if (prevNode == nullptr) {
        nodeList[nodeCount].prev = nullptr;
        nodeList[nodeCount].next = nullptr;
        head = &nodeList[nodeCount];
        tail = &nodeList[nodeCount];
    } else {
        Node* nextNode = prevNode->next;
        nodeList[nodeCount].prev = prevNode;
        nodeList[nodeCount].next = nextNode;

        if (nextNode != nullptr) {
            nextNode->prev = &nodeList[nodeCount];
        } else {
            tail = &nodeList[nodeCount];
        }

        prevNode->next = &nodeList[nodeCount];
    }
}

위 코드는 주어진 prevNode 다음에 새로운 노드를 삽입하는 함수입니다. 새로운 노드를 배열에 추가한 후, prevNode와 nextNode의 포인터를 조정하여 새로운 노드를 연결합니다.

노드의 삭제

void deleteNode(Node* delNode) {
    if (delNode == nullptr) return;

    nodeCount--;

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

    if (delNode->next != nullptr) {
        delNode->next->prev = delNode->prev;
    } else {
        tail = delNode->prev;
    }
}

위 코드는 주어진 delNode를 리스트에서 삭제하는 함수입니다. delNode의 이전 노드와 다음 노드의 포인터를 조정하여 노드를 리스트에서 제거합니다.

결론

배열과 포인터를 사용하여 이중 연결 리스트를 구현하는 방법을 간단하게 살펴보았습니다. 배열을 사용함으로써 노드의 삽입 및 삭제 시 메모리를 동적으로 할당하거나 해제할 필요가 없어 빠른 속도로 데이터를 처리할 수 있습니다. 하지만 여러 가지 제약이 있을 수 있으므로 실제 프로젝트에서는 상황에 맞는 자료 구조를 선택하는 것이 중요합니다.

참고 문헌:

https://www.geeksforgeeks.org/doubly-linked-list/

이상으로 배열과 포인터를 사용한 이중 연결 리스트의 구현에 대해 알아보았습니다.