자료구조를 처음 배울 때는 그냥 외우기만 했다. “배열, 리스트, 스택, 큐…” 하지만 실제 개발을 하다 보니 언제 어떤 걸 써야 할지 모르겠더라.
오늘은 실무에서 정말 많이 쓰이는 자료구조들과 활용법을 정리해보겠다.
배열은 가장 기본이지만 가장 강력한 자료구조다. 잘못 쓰면 성능이 엄청 떨어진다.
// 나쁜 예시
public int[] processData(int[] input) {
    int[] result = new int[input.length];
    
    for (int i = 0; i < input.length; i++) {
        result[i] = input[i] * 2 + 10;
    }
    
    return result;
}
// 좋은 예시
public List<Integer> processDataOptimized(List<Integer> input) {
    List<Integer> result = new ArrayList<>();
    
    for (Integer value : input) {
        result.add(value * 2 + 10);
    }
    
    return result;
}
상품 목록 관리 시스템에서 배열을 활용한 예시다.
// 상품 검색 결과를 효율적으로 관리
public class ProductManager {
    private Product[] products;
    private int size;
    
    // 효율적인 검색을 위한 정렬된 배열 유지
    public void addProduct(Product product) {
        if (size >= products.length) {
            resize();
        }
        
        // 삽입 정렬로 정렬 상태 유지
        int insertIndex = findInsertPosition(product);
        shiftElements(insertIndex);
        products[insertIndex] = product;
        size++;
    }
    
    // 이진 탐색으로 빠른 검색
    public Product findProduct(String productId) {
        int left = 0, right = size - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int comparison = products[mid].getId().compareTo(productId);
            
            if (comparison == 0) {
                return products[mid];
            } else if (comparison < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return null;
    }
}
배열을 선택한 이유:
배열의 한계:
ArrayList vs LinkedList, 언제 뭘 써야 할까? 처음에는 ArrayList만 썼는데, 규모가 커지면서 LinkedList의 필요성을 느꼈다.
// 1. ArrayList - 조회가 많은 경우
public class UserRepository {
    private List<User> users = new ArrayList<>();
    
    // 자주 호출되는 메서드
    public User findUserById(int id) {
        // ArrayList는 인덱스 접근이 O(1)
        if (id >= 0 && id < users.size()) {
            return users.get(id);
        }
        return null;
    }
    
    // 사용자 목록 조회 (자주 호출됨)
    public List<User> getAllUsers() {
        return new ArrayList<>(users); // 방어적 복사
    }
}
// 2. LinkedList - 삽입/삭제가 많은 경우
public class MessageQueue {
    private LinkedList<Message> messages = new LinkedList<>();
    
    // 메시지 추가 (많이 발생)
    public void addMessage(Message message) {
        messages.addLast(message); // O(1)
    }
    
    // 메시지 처리 (많이 발생)
    public Message getNextMessage() {
        return messages.pollFirst(); // O(1)
    }
    
    // 큐 크기 제한
    public void addMessageWithLimit(Message message, int maxSize) {
        messages.addLast(message);
        
        while (messages.size() > maxSize) {
            messages.removeFirst(); // 오래된 메시지 제거
        }
    }
}
ArrayList 사용하는 경우:
LinkedList 사용하는 경우:
// 10만 개 데이터로 테스트한 결과
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// 중간 삽입 테스트
long start = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    arrayList.add(arrayList.size() / 2, i); // ArrayList: ~2초
}
long arrayTime = System.nanoTime() - start;
start = System.nanoTime();
for (int i = 0; i < 100000; i++) {
    linkedList.add(linkedList.size() / 2, i); // LinkedList: ~0.1초
}
long linkedTime = System.nanoTime() - start;
System.out.println("ArrayList 중간삽입: " + arrayTime / 1_000_000 + "ms");
System.out.println("LinkedList 중간삽입: " + linkedTime / 1_000_000 + "ms");
결과: LinkedList가 약 20배 빠름!
스택은 LIFO(Last In, First Out) 구조로, 가장 최근에 들어온 데이터가 가장 먼저 나간다. 웹 애플리케이션의 네비게이션 히스토리, 함수 호출, 괄호 매칭 등에 활용된다.
class NavigationManager {
    constructor() {
        this.history = [];
        this.currentIndex = -1;
    }
    
    // 페이지 이동
    navigateTo(url) {
        // 현재 위치 이후의 히스토리 제거
        this.history = this.history.slice(0, this.currentIndex + 1);
        
        // 새 페이지 추가
        this.history.push(url);
        this.currentIndex++;
        
        this.loadPage(url);
    }
    
    // 뒤로가기
    goBack() {
        if (this.currentIndex > 0) {
            this.currentIndex--;
            const url = this.history[this.currentIndex];
            this.loadPage(url);
            return true;
        }
        return false;
    }
    
    // 앞으로가기
    goForward() {
        if (this.currentIndex < this.history.length - 1) {
            this.currentIndex++;
            const url = this.history[this.currentIndex];
            this.loadPage(url);
            return true;
        }
        return false;
    }
    
    loadPage(url) {
        // 실제 페이지 로딩 로직
        console.log(`Loading: ${url}`);
    }
}
// 사용 예시
const nav = new NavigationManager();
nav.navigateTo('/home');
nav.navigateTo('/products');
nav.navigateTo('/cart');
nav.goBack(); // '/products'로 이동
nav.goBack(); // '/home'으로 이동
nav.goForward(); // '/products'로 이동
코드 리뷰 도구에서 괄호 매칭을 검사하는 기능을 구현할 때도 스택을 사용했다.
public class BracketValidator {
    private static final Map<Character, Character> BRACKET_PAIRS = Map.of(
        '(', ')',
        '[', ']',
        '{', '}'
    );
    
    public boolean isValid(String code) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : code.toCharArray()) {
            if (isOpenBracket(c)) {
                stack.push(c);
            } else if (isCloseBracket(c)) {
                if (stack.isEmpty() || !isMatchingPair(stack.pop(), c)) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
    
    private boolean isOpenBracket(char c) {
        return BRACKET_PAIRS.containsKey(c);
    }
    
    private boolean isCloseBracket(char c) {
        return BRACKET_PAIRS.containsValue(c);
    }
    
    private boolean isMatchingPair(char open, char close) {
        return BRACKET_PAIRS.get(open) == close;
    }
}
// 사용 예시
BracketValidator validator = new BracketValidator();
System.out.println(validator.isValid("(a + b) * [c - d]")); // true
System.out.println(validator.isValid("(a + b) * [c - d")); // false
System.out.println(validator.isValid("((a + b) * [c - d])")); // true
언제 스택을 사용해야 할까?
스택 구현 시 주의사항:
큐는 FIFO(First In, First Out) 구조로, 먼저 들어온 데이터가 먼저 나간다. 대기열, 작업 스케줄링, BFS 알고리즘 등에 활용된다.
이메일 발송 시스템을 구현할 때 큐를 사용했다. 수만 명에게 이메일을 보내야 하는데, 한 번에 보내면 서버가 터진다.
@Service
public class EmailQueueService {
    private final Queue<EmailTask> emailQueue = new ConcurrentLinkedQueue<>();
    private final ExecutorService executorService = Executors.newFixedThreadPool(5);
    private volatile boolean isProcessing = false;
    
    // 이메일 발송 요청
    public void sendEmail(String to, String subject, String content) {
        EmailTask task = new EmailTask(to, subject, content);
        emailQueue.offer(task);
        
        // 큐가 비어있었다면 처리 시작
        if (!isProcessing) {
            startProcessing();
        }
    }
    
    // 대량 이메일 발송
    public void sendBulkEmails(List<EmailTask> tasks) {
        emailQueue.addAll(tasks);
        
        if (!isProcessing) {
            startProcessing();
        }
    }
    
    private void startProcessing() {
        isProcessing = true;
        
        executorService.submit(() -> {
            while (!emailQueue.isEmpty()) {
                EmailTask task = emailQueue.poll();
                if (task != null) {
                    try {
                        sendEmailTask(task);
                        Thread.sleep(100); // API 제한 고려
                    } catch (Exception e) {
                        // 실패한 작업을 다시 큐에 추가
                        emailQueue.offer(task);
                        log.error("이메일 발송 실패: {}", e.getMessage());
                    }
                }
            }
            isProcessing = false;
        });
    }
    
    private void sendEmailTask(EmailTask task) {
        // 실제 이메일 발송 로직
        System.out.println("Sending email to: " + task.getTo());
    }
}
게임에서 플레이어가 목표 지점까지 가는 최단 경로를 찾는 알고리즘이다.
public class PathFinder {
    private static final int[][] DIRECTIONS = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1} // 상하좌우
    };
    
    public List<Point> findShortestPath(int[][] map, Point start, Point end) {
        int rows = map.length;
        int cols = map[0].length;
        
        // 방문 여부와 부모 노드 추적
        boolean[][] visited = new boolean[rows][cols];
        Point[][] parent = new Point[rows][cols];
        
        Queue<Point> queue = new LinkedList<>();
        queue.offer(start);
        visited[start.x][start.y] = true;
        
        while (!queue.isEmpty()) {
            Point current = queue.poll();
            
            // 목표 지점에 도달
            if (current.equals(end)) {
                return reconstructPath(parent, start, end);
            }
            
            // 4방향 탐색
            for (int[] direction : DIRECTIONS) {
                int newX = current.x + direction[0];
                int newY = current.y + direction[1];
                
                // 유효한 좌표이고, 벽이 아니며, 방문하지 않은 경우
                if (isValid(newX, newY, rows, cols) && 
                    map[newX][newY] != 1 && 
                    !visited[newX][newY]) {
                    
                    Point next = new Point(newX, newY);
                    queue.offer(next);
                    visited[newX][newY] = true;
                    parent[newX][newY] = current;
                }
            }
        }
        
        return null; // 경로를 찾을 수 없음
    }
    
    private List<Point> reconstructPath(Point[][] parent, Point start, Point end) {
        List<Point> path = new ArrayList<>();
        Point current = end;
        
        while (current != null) {
            path.add(current);
            current = parent[current.x][current.y];
        }
        
        Collections.reverse(path);
        return path;
    }
    
    private boolean isValid(int x, int y, int rows, int cols) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}
// 사용 예시
int[][] map = {
    {0, 0, 1, 0, 0},
    {0, 0, 0, 0, 1},
    {1, 1, 0, 1, 0},
    {0, 0, 0, 0, 0}
};
PathFinder finder = new PathFinder();
Point start = new Point(0, 0);
Point end = new Point(3, 4);
List<Point> path = finder.findShortestPath(map, start, end);
if (path != null) {
    System.out.println("최단 경로: " + path);
} else {
    System.out.println("경로를 찾을 수 없습니다.");
}
큐의 종류와 특징:
큐 사용 시 주의사항:
해시맵은 키-값 쌍을 저장하는 자료구조로, 평균 O(1) 시간에 검색, 삽입, 삭제가 가능하다. 캐싱, 인덱싱, 빈도 계산 등에 활용된다.
자주 조회되는 데이터를 캐싱하는 시스템을 구현했다.
@Component
public class CacheManager {
    private final Map<String, CacheEntry> cache = new ConcurrentHashMap<>();
    private final int maxSize;
    private final long expirationTime;
    
    public CacheManager(int maxSize, long expirationTime) {
        this.maxSize = maxSize;
        this.expirationTime = expirationTime;
    }
    
    // 캐시에서 데이터 조회
    public <T> T get(String key, Class<T> type) {
        CacheEntry entry = cache.get(key);
        
        if (entry == null) {
            return null;
        }
        
        // 만료 시간 체크
        if (System.currentTimeMillis() - entry.getTimestamp() > expirationTime) {
            cache.remove(key);
            return null;
        }
        
        return type.cast(entry.getData());
    }
    
    // 캐시에 데이터 저장
    public void put(String key, Object data) {
        // 캐시 크기 제한
        if (cache.size() >= maxSize && !cache.containsKey(key)) {
            evictOldestEntry();
        }
        
        cache.put(key, new CacheEntry(data, System.currentTimeMillis()));
    }
    
    // 가장 오래된 엔트리 제거
    private void evictOldestEntry() {
        String oldestKey = null;
        long oldestTime = Long.MAX_VALUE;
        
        for (Map.Entry<String, CacheEntry> entry : cache.entrySet()) {
            if (entry.getValue().getTimestamp() < oldestTime) {
                oldestTime = entry.getValue().getTimestamp();
                oldestKey = entry.getKey();
            }
        }
        
        if (oldestKey != null) {
            cache.remove(oldestKey);
        }
    }
    
    // 캐시 통계
    public CacheStats getStats() {
        return new CacheStats(cache.size(), maxSize, expirationTime);
    }
    
    private static class CacheEntry {
        private final Object data;
        private final long timestamp;
        
        public CacheEntry(Object data, long timestamp) {
            this.data = data;
            this.timestamp = timestamp;
        }
        
        public Object getData() { return data; }
        public long getTimestamp() { return timestamp; }
    }
}
// 사용 예시
@Service
public class UserService {
    @Autowired
    private UserRepository userRepository;
    
    @Autowired
    private CacheManager cacheManager;
    
    public User getUserById(Long id) {
        String cacheKey = "user:" + id;
        
        // 캐시에서 먼저 조회
        User cachedUser = cacheManager.get(cacheKey, User.class);
        if (cachedUser != null) {
            System.out.println("캐시에서 조회: " + id);
            return cachedUser;
        }
        
        // DB에서 조회
        User user = userRepository.findById(id);
        if (user != null) {
            // 캐시에 저장
            cacheManager.put(cacheKey, user);
            System.out.println("DB에서 조회 후 캐시 저장: " + id);
        }
        
        return user;
    }
}
로그 분석에서 사용자 행동 패턴을 분석할 때 해시맵을 활용했다.
public class UserBehaviorAnalyzer {
    
    // 사용자별 페이지 방문 횟수
    public Map<String, Integer> getPageVisitCounts(List<LogEntry> logs) {
        Map<String, Integer> visitCounts = new HashMap<>();
        
        for (LogEntry log : logs) {
            String page = log.getPage();
            visitCounts.put(page, visitCounts.getOrDefault(page, 0) + 1);
        }
        
        return visitCounts;
    }
    
    // 가장 많이 방문한 페이지 TOP 10
    public List<Map.Entry<String, Integer>> getTopVisitedPages(List<LogEntry> logs, int topN) {
        Map<String, Integer> visitCounts = getPageVisitCounts(logs);
        
        return visitCounts.entrySet().stream()
            .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
            .limit(topN)
            .collect(Collectors.toList());
    }
    
    // 사용자별 세션 분석
    public Map<String, List<String>> getUserSessions(List<LogEntry> logs) {
        Map<String, List<String>> userSessions = new HashMap<>();
        
        for (LogEntry log : logs) {
            String userId = log.getUserId();
            String page = log.getPage();
            
            userSessions.computeIfAbsent(userId, k -> new ArrayList<>()).add(page);
        }
        
        return userSessions;
    }
    
    // 페이지 간 전환 패턴 분석
    public Map<String, Map<String, Integer>> getPageTransitionPatterns(List<LogEntry> logs) {
        Map<String, Map<String, Integer>> transitions = new HashMap<>();
        
        // 사용자별로 세션 정렬
        Map<String, List<LogEntry>> userLogs = logs.stream()
            .collect(Collectors.groupingBy(LogEntry::getUserId));
        
        for (List<LogEntry> userSession : userLogs.values()) {
            // 시간순 정렬
            userSession.sort(Comparator.comparing(LogEntry::getTimestamp));
            
            // 연속된 페이지 간 전환 계산
            for (int i = 0; i < userSession.size() - 1; i++) {
                String fromPage = userSession.get(i).getPage();
                String toPage = userSession.get(i + 1).getPage();
                
                transitions.computeIfAbsent(fromPage, k -> new HashMap<>())
                    .put(toPage, transitions.get(fromPage).getOrDefault(toPage, 0) + 1);
            }
        }
        
        return transitions;
    }
}
해시맵의 내부 동작 원리:
성능 최적화 팁:
주의사항:
트리는 계층적 구조를 표현하는 자료구조로, 노드와 엣지로 구성된다. 조직도, 파일 시스템, 데이터베이스 인덱스 등에 활용된다.
회사 조직도를 관리하는 시스템을 구현했다.
public class OrganizationTree {
    private Node root;
    
    public static class Node {
        private Employee employee;
        private List<Node> children;
        private Node parent;
        
        public Node(Employee employee) {
            this.employee = employee;
            this.children = new ArrayList<>();
        }
        
        // 직속 부하 추가
        public void addChild(Node child) {
            child.parent = this;
            this.children.add(child);
        }
        
        // 모든 하위 직원 조회
        public List<Employee> getAllSubordinates() {
            List<Employee> subordinates = new ArrayList<>();
            
            for (Node child : children) {
                subordinates.add(child.employee);
                subordinates.addAll(child.getAllSubordinates());
            }
            
            return subordinates;
        }
        
        // 특정 직원 찾기
        public Node findEmployee(String employeeId) {
            if (this.employee.getId().equals(employeeId)) {
                return this;
            }
            
            for (Node child : children) {
                Node found = child.findEmployee(employeeId);
                if (found != null) {
                    return found;
                }
            }
            
            return null;
        }
        
        // 조직도 출력
        public void printTree(String prefix) {
            System.out.println(prefix + employee.getName() + " (" + employee.getPosition() + ")");
            
            for (int i = 0; i < children.size(); i++) {
                Node child = children.get(i);
                boolean isLast = (i == children.size() - 1);
                String childPrefix = prefix + (isLast ? "└── " : "├── ");
                child.printTree(childPrefix);
            }
        }
    }
    
    // 조직도 구축
    public void buildOrganization() {
        // CEO
        Employee ceo = new Employee("001", "김철수", "CEO");
        root = new Node(ceo);
        
        // 부사장들
        Employee vp1 = new Employee("002", "이영희", "CTO");
        Employee vp2 = new Employee("003", "박민수", "CFO");
        
        Node vp1Node = new Node(vp1);
        Node vp2Node = new Node(vp2);
        
        root.addChild(vp1Node);
        root.addChild(vp2Node);
        
        // 개발팀
        Employee devManager = new Employee("004", "최지영", "개발팀장");
        Node devManagerNode = new Node(devManager);
        vp1Node.addChild(devManagerNode);
        
        Employee dev1 = new Employee("005", "정수현", "시니어 개발자");
        Employee dev2 = new Employee("006", "강민호", "주니어 개발자");
        
        devManagerNode.addChild(new Node(dev1));
        devManagerNode.addChild(new Node(dev2));
        
        // 마케팅팀
        Employee marketingManager = new Employee("007", "윤서연", "마케팅팀장");
        Node marketingManagerNode = new Node(marketingManager);
        vp2Node.addChild(marketingManagerNode);
        
        Employee marketer = new Employee("008", "임도현", "마케터");
        marketingManagerNode.addChild(new Node(marketer));
    }
    
    // 특정 직원의 모든 부하 조회
    public List<Employee> getSubordinates(String employeeId) {
        Node node = root.findEmployee(employeeId);
        return node != null ? node.getAllSubordinates() : new ArrayList<>();
    }
    
    // 조직도 출력
    public void printOrganization() {
        root.printTree("");
    }
}
// 사용 예시
OrganizationTree orgTree = new OrganizationTree();
orgTree.buildOrganization();
// 조직도 출력
orgTree.printOrganization();
// 특정 직원의 부하들 조회
List<Employee> subordinates = orgTree.getSubordinates("004");
System.out.println("개발팀장의 부하들: " + subordinates);
트리의 종류:
트리 순회 방법:
트리 사용 시 주의사항:
| 자료구조 | 접근 | 검색 | 삽입 | 삭제 | 공간복잡도 | 
|---|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) | O(n) | 
| ArrayList | O(1) | O(n) | O(1)* | O(n) | O(n) | 
| LinkedList | O(n) | O(n) | O(1) | O(1) | O(n) | 
| 스택 | O(n) | O(n) | O(1) | O(1) | O(n) | 
| 큐 | O(n) | O(n) | O(1) | O(1) | O(n) | 
| HashMap | - | O(1) | O(1) | O(1) | O(n) | 
*ArrayList의 삽입은 평균적으로 O(1)이지만, 배열 확장 시 O(n)
1. 조회가 많은 경우
// 사용자 정보 조회 - HashMap 사용
Map<String, User> userCache = new HashMap<>();
public User getUser(String userId) {
    return userCache.get(userId); // O(1)
}
2. 순서가 중요한 경우
// 작업 순서 관리 - Queue 사용
Queue<Task> taskQueue = new LinkedList<>();
public void addTask(Task task) {
    taskQueue.offer(task); // O(1)
}
public Task getNextTask() {
    return taskQueue.poll(); // O(1)
}
3. 중간 삽입/삭제가 많은 경우
// 실시간 채팅 메시지 - LinkedList 사용
List<Message> messages = new LinkedList<>();
public void insertMessage(int index, Message message) {
    messages.add(index, message); // O(1)
}
public void removeMessage(int index) {
    messages.remove(index); // O(1)
}
4. 최근 데이터만 필요한 경우
// 최근 검색어 - Stack 사용
Stack<String> recentSearches = new Stack<>();
public void addSearch(String keyword) {
    recentSearches.push(keyword);
    
    // 최대 10개만 유지
    if (recentSearches.size() > 10) {
        recentSearches.remove(0);
    }
}
웹 애플리케이션 개발 시:
게임 개발 시:
데이터 분석 시:
자료구조는 언제, 왜 사용하는지 이해하는 게 중요하다. 처음에는 ArrayList만 썼는데, 규모가 커지면서 각 자료구조의 특성을 이해하게 됐다.
각 자료구조의 특징:
선택 기준:
자료구조는 개발자의 기본 소양이다. 더 효율적인 코드를 생각하며 작성해보자.