5.2 선형 자료 구조 (Linear Data Structures)

선형 자료 구조는 데이터가 순차적(Linear)으로 저장, 특정한 순서를 따르는 자료 구조

5.2.1 연결 리스트 (Linked List)

연결 리스트(Linked List)는 노드(Node)와 포인터(Pointer)로 이루어진 선형 자료 구조
배열과 달리 동적 크기 조절이 가능하지만, 임의 접근(랜덤 액세스)이 불가능하다는 단점

C++ STL에서 연결 리스트 지원 : list

list는 이중 연결 리스트 (Doubly Linked List)를 제공

연결 리스트의 시간 복잡도

연산	시간 복잡도
맨 앞/뒤 삽입 (push_front, push_back)	O(1)
맨 앞/뒤 삭제 (pop_front, pop_back)	O(1)
중간 삽입/삭제 (반복자 사용)	O(1)
탐색	O(N)

예제 list 

#include <iostream>
#include <list>

using namespace std;

int main() {
    list<int> linkedList;

    // 원소 추가
    linkedList.push_back(10);
    linkedList.push_back(20);
    linkedList.push_front(5); // 맨 앞 삽입

    // 출력
    cout << "연결 리스트 원소: ";
    for (int x : linkedList) {
        cout << x << " ";
    }
    cout << endl;

    // 중간 삽입 (반복자 사용)
    auto it = linkedList.begin();
    advance(it, 1); // 두 번째 위치로 이동
    linkedList.insert(it, 15);

    // 삭제 (반복자 사용)
    it = linkedList.begin();
    linkedList.erase(it); // 첫 번째 원소 삭제

    cout << "수정 후 연결 리스트: ";
    for (int x : linkedList) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

연결 리스트 원소: 5 10 20 
수정 후 연결 리스트: 10 15 20

• push_front(), push_back()을 이용해 리스트의 앞/뒤에 삽입이 가능
• 반복자(iterator)를 이용해 중간 삽입 및 삭제를 수행

---

5.2.2 배열 (Array)

배열(Array)은 고정 크기의 선형 자료 구조
STL에서 배열을 다룰 때 보통 C++ 기본 배열 (int arr[10]) 또는 STL의 array를 사용

배열의 시간 복잡도

연산	시간 복잡도
임의 접근	O(1)
탐색	O(N)
삽입	O(N) (중간 삽입 시 이동 필요)
삭제	O(N)

예제 array

 

#include <iostream>
#include <array>

using namespace std;

int main() {
    array<int, 5> arr = {1, 2, 3, 4, 5};

    // 원소 접근 (O(1))
    cout << "배열 원소: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;

    // 크기 및 첫 번째 원소 접근
    cout << "배열 크기: " << arr.size() << endl;
    cout << "첫 번째 원소: " << arr.front() << endl;

    return 0;
}

배열 원소: 1 2 3 4 5
배열 크기: 5
첫 번째 원소: 1

• std::array는 std::vector보다 빠르며 고정된 크기의 배열을 제공

---

5.2.3 벡터 (Vector)

벡터(Vector)는 동적 크기 조절이 가능한 동적 배열
배열과 비슷하지만, 크기를 초과하면 자동으로 크기가 증가

C++ STL에서 벡터 지원: vector

벡터의 시간 복잡도

연산	시간 복잡도
임의 접근	O(1)
탐색	O(N)
끝 삽입 (push_back())	O(1) (평균)
중간 삽입 (insert())	O(N)
삭제 (erase())	O(N)

예제 vector

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3};

    // 원소 추가
    vec.push_back(4); // 끝에 추가
    vec.push_back(5);

    // 중간 삽입
    vec.insert(vec.begin() + 1, 10); // 두 번째 위치에 10 삽입

    // 원소 삭제
    vec.erase(vec.begin() + 2); // 세 번째 원소 삭제

    cout << "벡터 원소: ";
    for (int x : vec) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

벡터 원소: 1 10 3 4 5

• 벡터는 동적 크기 조절이 가능하지만, 중간 삽입 및 삭제 시 속도가 느려질 수 있다.

---

5.2.4 스택 (Stack)

스택(Stack)은 후입선출 (LIFO, Last In First Out) 구조를 따르는 자료 구조
C++ STL에서 std::stack을 사용하면 쉽게 구현

스택의 시간 복잡도

연산	시간 복잡도
삽입 (push())	O(1)
삭제 (pop())	O(1)
조회 (top())	O(1)

예제 stack

 

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;

    s.push(10);
    s.push(20);
    s.push(30);

    cout << "스택의 최상단 원소: " << s.top() << endl;

    s.pop();
    cout << "pop() 후 최상단 원소: " << s.top() << endl;

    return 0;
}

스택의 최상단 원소: 30
pop() 후 최상단 원소: 20

• push(), pop(), top()은 모두 O(1)의 시간 복잡도를 가진다.

---

추가. 큐 (Queue)

큐(Queue)는 선입선출(FIFO, First In First Out) 방식의 자료 구조
C++ STL에서 std::queue를 사용하여 쉽게 구현

큐의 시간 복잡도

연산	시간 복잡도
삽입 (push())	O(1)
삭제 (pop())	O(1)
조회 (front(), back())	O(1)

예제 queue

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;

    q.push(10);
    q.push(20);
    q.push(30);

    cout << "큐의 첫 번째 원소: " << q.front() << endl;
    cout << "큐의 마지막 원소: " << q.back() << endl;

    q.pop();
    cout << "pop() 후 첫 번째 원소: " << q.front() << endl;

    return 0;
}

큐의 첫 번째 원소: 10
큐의 마지막 원소: 30
pop() 후 첫 번째 원소: 20

 

• push(), pop(), front() 연산은 모두 O(1)의 시간 복잡도

---

추가. 덱 (Deque, Double-ended Queue)

덱(Deque, Double-ended Queue)은 양방향에서 삽입/삭제가 가능한 큐
STL의 std::deque는 스택과 큐의 장점을 결합한 자료 구조

덱의 시간 복잡도

연산	시간 복잡도
앞/뒤 삽입 (push_front(), push_back())	O(1)
앞/뒤 삭제 (pop_front(), pop_back())	O(1)
조회 (front(), back())	O(1)
임의 접근 (operator[])	O(1)

예제 deque

 

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> dq;

    dq.push_back(10);
    dq.push_back(20);
    dq.push_front(5); // 앞쪽 삽입

    cout << "덱의 첫 번째 원소: " << dq.front() << endl;
    cout << "덱의 마지막 원소: " << dq.back() << endl;

    dq.pop_front();
    cout << "pop_front() 후 첫 번째 원소: " << dq.front() << endl;

    return 0;
}

덱의 첫 번째 원소: 5
덱의 마지막 원소: 20
pop_front() 후 첫 번째 원소: 10

• std::deque는 양쪽 끝에서 O(1) 시간으로 삽입/삭제 가능하다는 점에서 std::vector보다 유리

---

추가. 원형 큐 (Circular Queue)

원형 큐는 고정된 크기에서 순환 구조를 가지는 큐
STL에서는 std::queue나 std::deque를 이용하여 구현

원형 큐의 시간 복잡도

연산	시간 복잡도
삽입 (enqueue())	O(1)
삭제 (dequeue())	O(1)
조회 (front(), back())	O(1)

예제 원형 큐 구현

#include <iostream>

using namespace std;

class CircularQueue {
private:
    int *arr;
    int front, rear, size, capacity;

public:
    CircularQueue(int cap) {
        capacity = cap;
        arr = new int[capacity];
        front = rear = -1;
        size = 0;
    }

    ~CircularQueue() { delete[] arr; }

    bool isFull() { return size == capacity; }
    bool isEmpty() { return size == 0; }

    void enqueue(int value) {
        if (isFull()) {
            cout << "큐가 가득 찼습니다.\n";
            return;
        }
        rear = (rear + 1) % capacity;
        arr[rear] = value;
        if (front == -1) front = 0;
        size++;
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "큐가 비어 있습니다.\n";
            return;
        }
        front = (front + 1) % capacity;
        size--;
    }

    int getFront() {
        if (isEmpty()) return -1;
        return arr[front];
    }
};

int main() {
    CircularQueue cq(3);
    cq.enqueue(1);
    cq.enqueue(2);
    cq.enqueue(3);
    cq.dequeue();
    cout << "현재 front 원소: " << cq.getFront() << endl;
    return 0;
}

현재 front 원소: 2

• 배열을 활용해 원형 큐를 구현
• 큐가 가득 차면 맨 처음 위치로 돌아가는 특성