[C++로 배우는 알고리즘과 자료구조] Day 3: 연결 리스트 (단일, 이중, 원형)

연결 리스트 (Linked List)

연결 리스트는 노드들이 포인터로 연결된 선형 자료구조입니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다. 연결 리스트는 동적 메모리 할당을 사용하여 크기를 유연하게 조정할 수 있습니다.

연결 리스트의 종류:

1. 단일 연결 리스트 (Singly Linked List)
2. 이중 연결 리스트 (Doubly Linked List)
3. 원형 연결 리스트 (Circular Linked List)

단일 연결 리스트 (Singly Linked List)

단일 연결 리스트는 각 노드가 다음 노드를 가리키는 포인터를 가진 자료구조입니다.

단일 연결 리스트 구현

노드 구조체 정의

#include <iostream>

// 단일 연결 리스트의 노드 구조체
struct Node {
    int data; // 데이터
    Node* next; // 다음 노드를 가리키는 포인터

    Node(int value) : data(value), next(nullptr) {} // 노드 생성자
};

// 단일 연결 리스트 클래스
class SinglyLinkedList {
public:
    SinglyLinkedList() : head(nullptr) {} // 생성자
    ~SinglyLinkedList(); // 소멸자

    void insert(int value); // 값 삽입
    void display() const; // 리스트 출력

private:
    Node* head; // 리스트의 첫 번째 노드를 가리키는 포인터
};

// 소멸자 정의 (메모리 해제)
SinglyLinkedList::~SinglyLinkedList() {
    Node* current = head;
    while (current != nullptr) {
        Node* nextNode = current->next;
        delete current; // 현재 노드 메모리 해제
        current = nextNode;
    }
}

// 값 삽입 함수 정의
void SinglyLinkedList::insert(int value) {
    Node* newNode = new Node(value); // 새로운 노드 생성
    if (head == nullptr) {
        head = newNode; // 리스트가 비어있을 경우 첫 노드로 설정
    } else {
        Node* current = head;
        while (current->next != nullptr) {
            current = current->next; // 리스트의 마지막 노드까지 이동
        }
        current->next = newNode; // 마지막 노드의 다음 노드로 설정
    }
}

// 리스트 출력 함수 정의
void SinglyLinkedList::display() const {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;
}

int main() {
    SinglyLinkedList list;
    list.insert(10);
    list.insert(20);
    list.insert(30);

    list.display(); // 리스트 출력

    return 0;
}

 

이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트는 각 노드가 다음 노드와 이전 노드를 가리키는 포인터를 가진 자료구조입니다.

이중 연결 리스트 구현

노드 구조체 정의

#include <iostream>

// 이중 연결 리스트의 노드 구조체
struct DNode {
    int data; // 데이터
    DNode* next; // 다음 노드를 가리키는 포인터
    DNode* prev; // 이전 노드를 가리키는 포인터

    DNode(int value) : data(value), next(nullptr), prev(nullptr) {} // 노드 생성자
};

// 이중 연결 리스트 클래스
class DoublyLinkedList {
public:
    DoublyLinkedList() : head(nullptr) {} // 생성자
    ~DoublyLinkedList(); // 소멸자

    void insert(int value); // 값 삽입
    void display() const; // 리스트 출력

private:
    DNode* head; // 리스트의 첫 번째 노드를 가리키는 포인터
};

// 소멸자 정의 (메모리 해제)
DoublyLinkedList::~DoublyLinkedList() {
    DNode* current = head;
    while (current != nullptr) {
        DNode* nextNode = current->next;
        delete current; // 현재 노드 메모리 해제
        current = nextNode;
    }
}

// 값 삽입 함수 정의
void DoublyLinkedList::insert(int value) {
    DNode* newNode = new DNode(value); // 새로운 노드 생성
    if (head == nullptr) {
        head = newNode; // 리스트가 비어있을 경우 첫 노드로 설정
    } else {
        DNode* current = head;
        while (current->next != nullptr) {
            current = current->next; // 리스트의 마지막 노드까지 이동
        }
        current->next = newNode; // 마지막 노드의 다음 노드로 설정
        newNode->prev = current; // 새로운 노드의 이전 노드로 설정
    }
}

// 리스트 출력 함수 정의
void DoublyLinkedList::display() const {
    DNode* current = head;
    while (current != nullptr) {
        std::cout << current->data << " <-> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;
}

int main() {
    DoublyLinkedList list;
    list.insert(10);
    list.insert(20);
    list.insert(30);

    list.display(); // 리스트 출력

    return 0;
}

 

원형 연결 리스트 (Circular Linked List)

원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 포인터를 가진 자료구조입니다.

원형 연결 리스트 구현

노드 구조체 정의

#include <iostream>

// 원형 연결 리스트의 노드 구조체
struct CNode {
    int data; // 데이터
    CNode* next; // 다음 노드를 가리키는 포인터

    CNode(int value) : data(value), next(nullptr) {} // 노드 생성자
};

// 원형 연결 리스트 클래스
class CircularLinkedList {
public:
    CircularLinkedList() : tail(nullptr) {} // 생성자
    ~CircularLinkedList(); // 소멸자

    void insert(int value); // 값 삽입
    void display() const; // 리스트 출력

private:
    CNode* tail; // 리스트의 마지막 노드를 가리키는 포인터
};

// 소멸자 정의 (메모리 해제)
CircularLinkedList::~CircularLinkedList() {
    if (tail != nullptr) {
        CNode* current = tail->next;
        do {
            CNode* nextNode = current->next;
            delete current; // 현재 노드 메모리 해제
            current = nextNode;
        } while (current != tail->next);
        delete tail; // 마지막 노드 메모리 해제
    }
}

// 값 삽입 함수 정의
void CircularLinkedList::insert(int value) {
    CNode* newNode = new CNode(value); // 새로운 노드 생성
    if (tail == nullptr) {
        tail = newNode; // 리스트가 비어있을 경우 첫 노드로 설정
        tail->next = tail; // 원형 연결 리스트로 만듦
    } else {
        newNode->next = tail->next; // 새로운 노드의 다음 노드를 첫 노드로 설정
        tail->next = newNode; // 마지막 노드의 다음 노드로 설정
        tail = newNode; // 새로운 노드를 마지막 노드로 설정
    }
}

// 리스트 출력 함수 정의
void CircularLinkedList::display() const {
    if (tail != nullptr) {
        CNode* current = tail->next;
        do {
            std::cout << current->data << " -> ";
            current = current->next;
        } while (current != tail->next);
        std::cout << "(back to head)" << std::endl;
    }
}

int main() {
    CircularLinkedList list;
    list.insert(10);
    list.insert(20);
    list.insert(30);

    list.display(); // 리스트 출력

    return 0;
}

 

설명

1. 단일 연결 리스트 (Singly Linked List):
   • 각 노드는 다음 노드를 가리키는 포인터를 가집니다.
   • 마지막 노드의 다음 포인터는 nullptr을 가리킵니다.
2. 이중 연결 리스트 (Doubly Linked List):
   • 각 노드는 다음 노드와 이전 노드를 가리키는 포인터를 가집니다.
   • 양방향으로 순회가 가능합니다.
3. 원형 연결 리스트 (Circular Linked List):
   • 마지막 노드는 첫 번째 노드를 가리키는 포인터를 가집니다.
   • 리스트의 모든 노드가 원형으로 연결됩니다.

이제 연결 리스트의 기본 개념을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 4: 스택과 큐"에 대해 학습하겠습니다.