직접 구현할 때 STL을 안 쓰는 이유는?

교육·인터뷰·제약 환경에서는 직접 구현이 요구됩니다. 프로덕션에서는 검증된 STL·라이브러리가 기본입니다.

연결 리스트가 항상 벡터보다 나은가요?

아닙니다. 캐시 지역성이 떨어져 실제로는 벡터가 빠른 경우가 많습니다. 삽입 패턴을 보고 고르세요.

BST 직접 구현 시 흔한 실수는?

균형이 깨져 최악 O(n)이 되거나, 삭제 시 자식 연결을 놓치는 경우입니다. AVL·레드블랙 등 균형 트리를 별도로 학습하세요.

해시테이블에서 충돌 처리는?

체이닝과 개방 주소법이 대표적입니다. 메모리·캐시·삭제 정책에 따라 성능이 달라집니다.

C++ 자료구조 | '직접 구현하기' 연결리스트/트리/해시테이블

2026년 3월 12일 · 16분 읽기 · 수정 2026년 3월 12일 중급 튜토리얼

이 글의 핵심

template <typename T> class BST { private: struct Node { T data; Node left; Node right; Node(T val) : data(val),…

1. 연결 리스트 (Linked List)

template <typename T>
class LinkedList {
private:
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(val), next(nullptr) {}
    };
    
    Node* head;
    int size;
    
public:
    LinkedList() : head(nullptr), size(0) {}
    
    ~LinkedList() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
    
    void push_front(T value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
        size++;
    }
    
    void push_back(T value) {
        Node* newNode = new Node(value);
        
        if (!head) {
            head = newNode;
        } else {
            Node* curr = head;
            while (curr->next) {
                curr = curr->next;
            }
            curr->next = newNode;
        }
        size++;
    }
    
    bool remove(T value) {
        if (!head) return false;
        
        if (head->data == value) {
            Node* temp = head;
            head = head->next;
            delete temp;
            size--;
            return true;
        }
        
        Node* curr = head;
        while (curr->next && curr->next->data != value) {
            curr = curr->next;
        }
        
        if (curr->next) {
            Node* temp = curr->next;
            curr->next = curr->next->next;
            delete temp;
            size--;
            return true;
        }
        
        return false;
    }
    
    void print() {
        Node* curr = head;
        while (curr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "null" << endl;
    }
};

2. 이진 탐색 트리 (Binary Search Tree)

template <typename T>
class BST {
private:
    struct Node {
        T data;
        Node* left;
        Node* right;
        
        Node(T val) : data(val), left(nullptr), right(nullptr) {}
    };
    
    Node* root;
    
    Node* insertHelper(Node* node, T value) {
        if (!node) {
            return new Node(value);
        }
        
        if (value < node->data) {
            node->left = insertHelper(node->left, value);
        } else if (value > node->data) {
            node->right = insertHelper(node->right, value);
        }
        
        return node;
    }
    
    bool searchHelper(Node* node, T value) {
        if (!node) return false;
        if (node->data == value) return true;
        
        if (value < node->data) {
            return searchHelper(node->left, value);
        } else {
            return searchHelper(node->right, value);
        }
    }
    
    void inorderHelper(Node* node) {
        if (!node) return;
        
        inorderHelper(node->left);
        cout << node->data << " ";
        inorderHelper(node->right);
    }
    
    void destroyTree(Node* node) {
        if (!node) return;
        
        destroyTree(node->left);
        destroyTree(node->right);
        delete node;
    }
    
public:
    BST() : root(nullptr) {}
    
    ~BST() {
        destroyTree(root);
    }
    
    void insert(T value) {
        root = insertHelper(root, value);
    }
    
    bool search(T value) {
        return searchHelper(root, value);
    }
    
    void inorder() {
        inorderHelper(root);
        cout << endl;
    }
};

int main() {
    BST<int> tree;
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    
    tree.inorder();  // 20 30 40 50 70
    cout << tree.search(40) << endl;  // 1
}

3. 해시 테이블 (Hash Table)

template <typename K, typename V>
class HashTable {
private:
    struct Entry {
        K key;
        V value;
        bool occupied;
        
        Entry() : occupied(false) {}
    };
    
    vector<Entry> table;
    int capacity;
    int size;
    
    int hash(const K& key) {
        return std::hash<K>{}(key) % capacity;
    }
    
    int probe(int index, int i) {
        return (index + i) % capacity;  // 선형 탐사
    }
    
public:
    HashTable(int cap = 10) : capacity(cap), size(0) {
        table.resize(capacity);
    }
    
    void insert(const K& key, const V& value) {
        if (size >= capacity * 0.7) {
            rehash();
        }
        
        int index = hash(key);
        int i = 0;
        
        while (table[probe(index, i)].occupied) {
            if (table[probe(index, i)].key == key) {
                table[probe(index, i)].value = value;
                return;
            }
            i++;
        }
        
        int finalIndex = probe(index, i);
        table[finalIndex].key = key;
        table[finalIndex].value = value;
        table[finalIndex].occupied = true;
        size++;
    }
    
    bool get(const K& key, V& value) {
        int index = hash(key);
        int i = 0;
        
        while (table[probe(index, i)].occupied) {
            if (table[probe(index, i)].key == key) {
                value = table[probe(index, i)].value;
                return true;
            }
            i++;
            if (i >= capacity) break;
        }
        
        return false;
    }
    
    void rehash() {
        vector<Entry> oldTable = table;
        capacity *= 2;
        table.clear();
        table.resize(capacity);
        size = 0;
        
        for (const auto& entry : oldTable) {
            if (entry.occupied) {
                insert(entry.key, entry.value);
            }
        }
    }
    
    void print() {
        for (int i = 0; i < capacity; i++) {
            if (table[i].occupied) {
                cout << "[" << i << "] " << table[i].key 
                     << " -> " << table[i].value << endl;
            }
        }
    }
};

4. 스택 (Stack)

template <typename T>
class Stack {
private:
    vector<T> data;
    
public:
    void push(T value) {
        data.push_back(value);
    }
    
    void pop() {
        if (!empty()) {
            data.pop_back();
        }
    }
    
    T top() {
        return data.back();
    }
    
    bool empty() {
        return data.empty();
    }
    
    int size() {
        return data.size();
    }
};

5. 큐 (Queue)

template <typename T>
class Queue {
private:
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(val), next(nullptr) {}
    };
    
    Node* front;
    Node* rear;
    int size;
    
public:
    Queue() : front(nullptr), rear(nullptr), size(0) {}
    
    ~Queue() {
        while (front) {
            Node* temp = front;
            front = front->next;
            delete temp;
        }
    }
    
    void enqueue(T value) {
        Node* newNode = new Node(value);
        
        if (!rear) {
            front = rear = newNode;
        } else {
            rear->next = newNode;
            rear = newNode;
        }
        size++;
    }
    
    void dequeue() {
        if (!front) return;
        
        Node* temp = front;
        front = front->next;
        
        if (!front) {
            rear = nullptr;
        }
        
        delete temp;
        size--;
    }
    
    T getFront() {
        return front->data;
    }
    
    bool empty() {
        return front == nullptr;
    }
};

실전 예시

예시 1: LRU 캐시

class LRUCache {
private:
    struct Node {
        int key, value;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    
    int capacity;
    unordered_map<int, Node*> cache;
    Node* head;
    Node* tail;
    
    void addToFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    void moveToFront(Node* node) {
        removeNode(node);
        addToFront(node);
    }
    
public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        
        Node* node = cache[key];
        moveToFront(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            Node* node = cache[key];
            node->value = value;
            moveToFront(node);
        } else {
            if (cache.size() >= capacity) {
                Node* lru = tail->prev;
                removeNode(lru);
                cache.erase(lru->key);
                delete lru;
            }
            
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addToFront(newNode);
        }
    }
};

예시 2: 그래프 (인접 리스트)

class Graph {
private:
    int V;
    vector<vector<int>> adj;
    
public:
    Graph(int vertices) : V(vertices) {
        adj.resize(V);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);  // 무방향 그래프
    }
    
    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            cout << curr << " ";
            
            for (int neighbor : adj[curr]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }
    
    void DFS(int start) {
        vector<bool> visited(V, false);
        DFSHelper(start, visited);
        cout << endl;
    }
    
private:
    void DFSHelper(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";
        
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                DFSHelper(neighbor, visited);
            }
        }
    }
};

자주 발생하는 문제

문제 1: 메모리 누수

증상: 메모리 계속 증가

원인: 노드 삭제 안함

해결법: 소멸자에서 모든 노드 삭제

문제 2: 댕글링 포인터

증상: 크래시

원인: 삭제된 노드 접근

해결법: 삭제 후 포인터를 nullptr로 설정

문제 3: 무한 루프

증상: 프로그램이 멈춤

원인: 순환 참조 또는 잘못된 포인터 연결

해결법: 디버거로 포인터 체크

FAQ

Q1: STL을 써도 되는데 왜 직접 구현하나요?

면접 준비
내부 동작 이해
특수한 요구사항

Q2: 어떤 자료구조를 먼저 배워야 하나요?

A: 배열 → 연결리스트 → 스택/큐 → 트리 → 그래프

Q3: 시간복잡도는?

연결리스트: 삽입 O(1), 탐색 O(n)
BST: 평균 O(log n), 최악 O(n)
해시테이블: 평균 O(1), 최악 O(n)

Q4: 실무에서 직접 구현하나요?

A: 대부분 STL을 사용하지만, 특수한 경우 직접 구현합니다.

Q5: 자료구조 학습 리소스는?

“Introduction to Algorithms” (CLRS)
LeetCode, 백준 문제 풀이
visualgo.net (시각화)

Q6: 포인터가 어려워요!

A: 그림을 그려가며 이해하세요. 디버거로 포인터 값을 확인하는 것도 도움이 됩니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

실전 체크리스트

실무에서 이 개념을 적용할 때 확인해야 할 사항입니다.

코드 작성 전

이 기법이 현재 문제를 해결하는 최선의 방법인가?
팀원들이 이 코드를 이해하고 유지보수할 수 있는가?
성능 요구사항을 만족하는가?

코드 작성 중

컴파일러 경고를 모두 해결했는가?
엣지 케이스를 고려했는가?
에러 처리가 적절한가?

코드 리뷰 시

코드의 의도가 명확한가?
테스트 케이스가 충분한가?
문서화가 되어 있는가?

이 체크리스트를 활용하여 실수를 줄이고 코드 품질을 높이세요.

배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「C++ 자료구조 | ‘직접 구현하기’ 연결리스트/트리/해시테이블」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]

sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)

불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역	운영 관점 질문
관측성	요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성	입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성	재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능	캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포	롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량	피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「C++ 자료구조 | ‘직접 구현하기’ 연결리스트/트리/해시테이블」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.

handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상	가능 원인	조치
간헐적 실패	레이스, 타임아웃, 외부 의존성, DNS	최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하	N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스	프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가	캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납	상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패	환경 변수, 권한, 플랫폼 차이, lockfile	CI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치	프로필·시크릿·기본값, 리전	스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치	비멱등 재시도, 부분 쓰기, 캐시 무효화 누락	멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.

이 글에서 다루는 키워드 (관련 검색어)

C++, 자료구조, data-structure, 알고리즘, 구현 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

Keyboard Shortcuts