Data Structure 테스트 전략 완벽 가이드

자료구조 구현 시 필수적인 테스트 전략을 다룹니다. 단위 테스트부터 경계값 테스트, 성능 테스트까지 실전 예제로 배워보세요.

---

---

들어가며

이 글에서는 Data Structure 테스트 전략 완벽 가이드에 대해 상세히 알아보겠습니다. 총 10가지 주요 개념을 다루며, 각각의 개념에 대한 설명과 실제 코드 예제를 함께 제공합니다.

목차

1. Stack_기본_테스트
2. Queue_FIFO_검증
3. LinkedList_삽입_삭제_테스트
4. 경계값_테스트
5. 이진_탐색_트리_검증
6. Hash_Table_충돌_처리
7. 성능_테스트_시간복잡도
8. 메모리_누수_테스트
9. 동시성_안전성_테스트
10. 불변성_테스트

---

1. Stack 기본 테스트

개요

Stack 자료구조의 핵심 기능인 push, pop, peek을 테스트합니다. 각 메서드가 예상대로 동작하는지 검증합니다.

코드 예제

test('Stack push and pop', () => {
  const stack = new Stack();
  stack.push(1);
  stack.push(2);
  expect(stack.pop()).toBe(2);
  expect(stack.pop()).toBe(1);
  expect(stack.isEmpty()).toBe(true);
});

설명

push로 데이터를 추가하고 pop으로 제거할 때 LIFO(후입선출) 순서가 지켜지는지 확인합니다. 마지막으로 스택이 비었는지 검증합니다.

---

2. Queue FIFO 검증

개요

Queue의 FIFO(선입선출) 특성을 테스트합니다. enqueue와 dequeue의 순서가 올바른지 확인합니다.

코드 예제

test('Queue maintains FIFO order', () => {
  const queue = new Queue();
  queue.enqueue('first');
  queue.enqueue('second');
  expect(queue.dequeue()).toBe('first');
  expect(queue.peek()).toBe('second');
});

설명

먼저 들어간 데이터가 먼저 나오는지 테스트합니다. peek 메서드로 제거하지 않고 다음 값을 확인할 수 있습니다.

---

3. LinkedList 삽입 삭제 테스트

개요

LinkedList의 다양한 위치에서 노드 삽입과 삭제를 테스트합니다. 헤드, 중간, 테일 위치 모두 검증합니다.

코드 예제

test('LinkedList insert and remove', () => {
  const list = new LinkedList();
  list.append(1);
  list.append(3);
  list.insertAt(1, 2);
  expect(list.toArray()).toEqual([1, 2, 3]);
  list.removeAt(1);
  expect(list.toArray()).toEqual([1, 3]);
});

설명

특정 인덱스에 노드를 삽입하고 제거한 후 배열로 변환하여 순서를 검증합니다. toArray 헬퍼 메서드로 쉽게 확인합니다.

---

4. 경계값 테스트

개요

빈 자료구조나 최대 용량 등 극단적인 상황을 테스트합니다. 예외 처리가 올바른지 확인합니다.

코드 예제

test('Edge cases for empty stack', () => {
  const stack = new Stack();
  expect(() => stack.pop()).toThrow('Stack is empty');
  expect(stack.peek()).toBeNull();
  expect(stack.size()).toBe(0);
});

설명

빈 스택에서 pop 시도 시 에러가 발생하는지, peek는 null을 반환하는지 테스트합니다. 경계값 테스트는 버그 예방에 필수적입니다.

---

5. 이진 탐색 트리 검증

개요

BST의 삽입 후 순서가 올바르게 유지되는지 중위 순회로 검증합니다. 이진 탐색 속성을 확인합니다.

코드 예제

test('BST maintains order', () => {
  const bst = new BST();
  [5, 3, 7, 1, 9].forEach(v => bst.insert(v));
  const inorder = bst.inorderTraversal();
  expect(inorder).toEqual([1, 3, 5, 7, 9]);
});

설명

순서 없이 삽입한 값들이 중위 순회 시 정렬된 순서로 나오는지 확인합니다. BST의 핵심 속성을 검증하는 테스트입니다.

---

6. Hash Table 충돌 처리

개요

Hash Table의 해시 충돌 상황을 테스트합니다. 같은 해시값을 가진 키들이 올바르게 저장되는지 확인합니다.

코드 예제

test('HashTable handles collisions', () => {
  const hash = new HashTable(10);
  hash.set('key1', 'value1');
  hash.set('key2', 'value2');
  expect(hash.get('key1')).toBe('value1');
  expect(hash.get('key2')).toBe('value2');
});

설명

작은 크기의 해시 테이블에 여러 키를 저장하여 충돌 처리 로직을 검증합니다. 각 값이 정확히 조회되는지 확인합니다.

---

7. 성능 테스트 시간복잡도

개요

자료구조의 시간 복잡도를 실제로 측정합니다. 대량 데이터로 예상 성능이 나오는지 검증합니다.

코드 예제

test('Array search performance O(n)', () => {
  const arr = Array.from({length: 10000}, (_, i) => i);
  const start = performance.now();
  arr.includes(9999);
  const duration = performance.now() - start;
  expect(duration).toBeLessThan(10);
});

설명

배열 검색의 선형 시간 복잡도를 실제 측정으로 확인합니다. 성능 테스트는 알고리즘 효율성을 보장하는 데 중요합니다.

---

8. 메모리 누수 테스트

개요

순환 참조나 메모리 누수가 없는지 테스트합니다. 큰 데이터 처리 후 메모리가 해제되는지 확인합니다.

코드 예제

test('LinkedList clears memory', () => {
  const list = new LinkedList();
  for(let i = 0; i < 1000; i++) list.append(i);
  list.clear();
  expect(list.head).toBeNull();
  expect(list.size()).toBe(0);
});

설명

대량의 노드를 추가한 후 clear 메서드로 모두 제거합니다. head가 null이고 크기가 0인지 확인하여 메모리 정리를 검증합니다.

---

9. 동시성 안전성 테스트

개요

여러 작업이 동시에 실행될 때 자료구조의 일관성을 테스트합니다. 비동기 환경에서의 안정성을 확인합니다.

코드 예제

test('Queue is thread-safe', async () => {
  const queue = new Queue();
  await Promise.all([
    queue.enqueue(1), queue.enqueue(2)
  ]);
  expect(queue.size()).toBe(2);
});

설명

Promise.all로 동시에 여러 enqueue를 실행하여 데이터 손실이 없는지 확인합니다. 멀티스레드 환경에서 중요한 테스트입니다.

---

10. 불변성 테스트

개요

원본 데이터를 변경하지 않는 불변 자료구조를 테스트합니다. 복사본이 독립적으로 동작하는지 확인합니다.

코드 예제

test('Immutable list preserves original', () => {
  const list1 = ImmutableList.of([1, 2, 3]);
  const list2 = list1.push(4);
  expect(list1.toArray()).toEqual([1, 2, 3]);
  expect(list2.toArray()).toEqual([1, 2, 3, 4]);
});

설명

불변 리스트에 push 시 원본은 그대로 유지되고 새로운 리스트가 반환됩니다. 함수형 프로그래밍의 핵심 개념입니다.

---

마치며

이번 글에서는 Data Structure 테스트 전략 완벽 가이드에 대해 알아보았습니다. 총 10가지 개념을 다루었으며, 각각의 사용법과 예제를 살펴보았습니다.

관련 태그

#JavaScript #Testing #DataStructures #UnitTest #Jest