[c++] 연결 리스트(Linked List) 데이터 구조

08 Dec 2023

연결 리스트는 데이터를 순서대로 저장하는 데이터 구조로, 각 데이터 요소가 다음 요소를 가리키는 포인터를 갖고 있다. 이러한 구조는 각 요소가 물리적으로 연속적으로 저장되지 않아도 되기 때문에 데이터 삽입과 삭제가 쉽고 효율적으로 처리될 수 있다.

연결 리스트의 장단점

연결 리스트의 가장 큰 장점은 삽입과 삭제가 빠르다는 것이다. 삽입, 삭제 시에는 단순히 포인터를 조정하는 것만으로 작업을 끝낼 수 있다. 반면에 연결 리스트의 단점은 특정 인덱스에 접근하는 데에는 선형적인 시간이 걸린다는 점이다.

연결 리스트의 구현

아래는 C++로 연결 리스트를 구현한 예시이다.

#include <iostream>

class Node {
public:
    int data;
    Node* next;
};

class LinkedList {
private:
    Node* head;
public:
    LinkedList() {
        head = nullptr;
    }

    void insert(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = head;
        head = newNode;
    }

    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
    }
};

int main() {
    LinkedList list;
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.display();
    return 0;
}

위 코드는 간단한 연결 리스트의 구현 예시이며, 이러한 방식으로 데이터를 삽입하고 표시할 수 있다.

연결 리스트는 다양한 응용 분야에서 유용하게 사용되며, 데이터 구조와 알고리즘을 공부하는 데에 중요한 개념 중 하나이다.

더 자세한 내용은 아래 레퍼런스를 참조하시기 바랍니다.

레퍼런스

GeeksforGeeks - Linked List