[C++] 자료구조 Linked List 원리와 사용방법

Photo by Markus Spiske on Unsplash

 

Linked list는 C++에서 포인터의 개념을 기반으로 구현되며, 이는 C 언어의 포인터를 통한 메모리 동적 할당을 바탕으로 합니다. Linked list는 배열과 달리 요소들이 메모리 상에서 연속적으로 위치하지 않고 각 요소가 다음 요소를 가리키는 포인터를 갖습니다.

아래는 C++에서 간단한 linked list를 동적으로 생성하는 예제 코드입니다.

#include <iostream>

// 각 노드를 나타내는 구조체
struct Node {
    int data;
    Node* next; // 다음 노드를 가리키는 포인터
};

int main() {
    // 첫 번째 노드 생성
    Node* head = new Node();
    head->data = 1;
    head->next = nullptr; // 초기에는 다음 노드가 없음

    // 두 번째 노드 생성
    Node* second = new Node();
    second->data = 2;
    second->next = nullptr;

    // 첫 번째 노드가 두 번째 노드를 가리키도록 설정
    head->next = second;

    // 세 번째 노드 생성
    Node* third = new Node();
    third->data = 3;
    third->next = nullptr;

    // 두 번째 노드가 세 번째 노드를 가리키도록 설정
    second->next = third;

    // 연결 리스트 순회하며 출력
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }

    // 메모리 해제
    current = head;
    while (current != nullptr) {
        Node* nextNode = current->next;
        delete current;
        current = nextNode;
    }

    return 0;
}

 

이 예제에서는 각 노드가 data와 next라는 두 개의 멤버를 가지는 구조체로 정의되었습니다. next는 다음 노드를 가리키는 포인터입니다. Linked list는 동적으로 크기를 조절할 수 있기 때문에, 노드를 동적으로 할당하고 메모리를 해제하는 과정이 중요합니다.

위의 코드는 간단한 예제일 뿐이며, 실제 프로덕션 코드에서는 예외 처리 및 기타 안전성 관련 고려 사항이 추가되어야 합니다. Linked list의 장점 중 하나는 중간에 요소를 효율적으로 추가하거나 삭제할 수 있는 능력이며, 이는 데이터의 동적인 조작에 유용합니다.

 

추가로 C++에서 linked list(연결 리스트)는 std::list와 같은 STL 컨테이너를 통해 사용할 수 있습니다. 또한, C++11부터는 std::forward_list도 추가되었는데, 이는 단일 연결 리스트를 나타냅니다. Linked list는 동적으로 크기가 조절되는 데이터 구조로, 삽입 및 삭제가 효율적입니다.

 

std::list 사용법

#include <iostream>
#include <list>

int main() {
    // 리스트 생성
    std::list<int> myList;

    // 원소 추가
    myList.push_back(1);
    myList.push_back(2);
    myList.push_front(0); // 맨 앞에 원소 추가

    // 원소 순회
    for (int num : myList) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    // 특정 위치에 원소 삽입
    auto it = std::find(myList.begin(), myList.end(), 2);
    if (it != myList.end()) {
        myList.insert(it, 3);
    }

    // 특정 원소 삭제
    myList.remove(1);

    // 리스트 크기 출력
    std::cout << "Size: " << myList.size() << "\n";

    return 0;
}

 

std::forward_list 사용법 : 

#include <iostream>
#include <forward_list>

int main() {
    // 단일 연결 리스트 생성
    std::forward_list<int> myForwardList;

    // 원소 추가
    myForwardList.push_front(1);
    myForwardList.push_front(2);
    myForwardList.push_front(3);

    // 원소 순회
    for (int num : myForwardList) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    // 특정 위치에 원소 삽입 (단일 연결 리스트에서는 insert() 사용 불가)

    // 특정 원소 삭제
    myForwardList.remove(2);

    // 리스트 크기 출력 (단일 연결 리스트에서는 size() 사용 불가)

    return 0;
}

 

linked list 특징 및 주의사항

 

 

1. 메모리 동적 할당: 연결 리스트는 동적으로 메모리를 할당하므로, 크기를 동적으로 조절할 수 있습니다.
2. 포인터로 연결: 각 노드는 다음 노드를 가리키는 포인터를 가지고 있어, 요소의 삽입 및 삭제가 효율적입니다.
3. 검색 속도: 일반적으로 특정 위치의 요소를 찾는 데는 배열보다 느립니다. 순차적으로 검색해야 하기 때문입니다.
4. 랜덤 액세스 제한: 인덱스를 사용하여 특정 위치의 요소에 바로 액세스할 수 없습니다. 반드시 처음부터 순차적으로 탐색해야 합니다.
5. std::list와 std::forward_list의 차이:
   • std::list: 이중 연결 리스트로, 양방향으로 탐색이 가능합니다.
   • std::forward_list: 단일 연결 리스트로, 다음 노드만을 가리키기 때문에 양방향 탐색이 불가능합니다.

연결 리스트는 특히 삽입 및 삭제가 빈번한 상황에서 유용하며, 특정 순서를 유지해야 하는 경우에도 활용됩니다.