Architecture/Data Structure
Collection
is..cy
2025. 2. 14. 19:56
Collection
- 객체 지향 프로그래밍에서 여러 개의 요소를 하나의 집합으로 묶어 다룰 수 있도록 하는 데이터 구조
- 여러 개의 데이터 항목을 저장하고, 이를 효율적으로 관리하는 기능을 제공하는 인터페이스 또는 클래스를 의미
- Java에서 컬렉션 프레임워크의 최상위 인터페이스로, 데이터의 그룹을 다루는 다양한 자료구조에 대한 공통적인 규약을 제공
- Collection Interface : 리스트, 셋, 큐 등 여러 컬렉션 클래스를 위한 기본 인터페이스로 사용
- java.util 패키지에 속함
- Iterable: 컬렉션을 순차적으로 반복(iterate) 할 수 있게 해주는 인터페이스
- TreeSet
- 내부적으로 이진 탐색 트리를 사용하여 요소들을 자동으로 정렬합니다.
- 중복된 값을 허용하지 않으며, 빠른 검색 및 정렬 기능을 제공합니다. 그러나 삽입 및 삭제는 상대적으로 느릴 수 있습니다.
- LinkedList
- 이중 연결 리스트로 구현되어 있어, 양 끝에서 삽입과 삭제가 매우 빠릅니다.
- 그러나 인덱스 기반 접근은 비효율적이며, 중간에서 삽입/삭제가 자주 일어나면 성능이 저하될 수 있습니다.
- ArrayList
- 내부적으로 동적 배열을 사용하여 요소를 저장합니다.
- 인덱스를 사용한 접근이 매우 빠르지만, 배열 크기가 초과할 경우 배열 크기 재조정(리사이징) 시 비용이 발생합니다.
- 중간에서의 삽입 및 삭제는 느리며, 메모리 사용이 상대적으로 효율적입니다.
TreeSet | LinkedList | ArrayList | |
인터페이스 구현 | Set (중복 허용하지 않음) | List, Deque | List |
내부 구현 | 이진 탐색 트리 (Red-Black Tree) | 이중 연결 리스트 (Doubly Linked List) | 동적 배열 |
순서 보장 | 정렬된 순서 (오름차순) | 삽입 순서 유지 | 삽입 순서 유지 |
중복 허용 여부 | 허용하지 않음 | 허용 | 허용 |
검색 시간 복잡도 | O(log n) | O(n) | O(1) (인덱스로 접근) |
삽입/삭제 시간 복잡도 | O(log n) | O(1) (리스트 양 끝에서) | O(n) (중간 삽입/삭제시) |
메모리 사용 | 상대적으로 더 많이 사용 | 각 노드에 링크 정보 추가 | 배열 크기 증가 시 추가 메모리 사용 |
장점 | 정렬된 요소, 검색 성능 좋음 | 삽입/삭제가 빠르며 양쪽 끝에서 빠름 | 빠른 인덱스 접근, 메모리 효율성 |
단점 | 검색이 빠르지만 삽입/삭제가 느림 | 인덱스 접근이 느림, 메모리 사용이 많음 | 중간 삽입/삭제 성능이 좋지 않음 |
- Stack
- LIFO(Last In, First Out) 구조로, 가장 최근에 삽입된 데이터가 먼저 제거
- 데이터를 삽입하는 작업은 push(), 제거하는 작업은 pop()으로 처리
- ex. 함수 호출 시 재귀 함수 호출, 웹 브라우저의 뒤로 가기 버튼의 히스토리 등.
- Queue
- FIFO(First In, First Out) 구조로, 가장 먼저 삽입된 데이터가 먼저 제거
- 데이터를 삽입하는 작업은 enqueue(), 제거하는 작업은 dequeue()로 처리
- ex. 프린터에서 문서가 처리되는 순서, 프로세스 스케줄링에서 대기열 처리 등.
구조 | LIFO (Last In, First Out) | FIFO (First In, First Out) |
주요 연산 | push() (데이터 삽입) / pop() (데이터 제거) | enqueue() (데이터 삽입) / dequeue() (데이터 제거) |
데이터 접근 순서 | 맨 위의 데이터를 먼저 처리 | 맨 앞의 데이터를 먼저 처리 |
사용 예시 | 함수 호출 스택, 후위 표기법 계산, 웹 브라우저 히스토리 등 | 프린터 큐, 프로세스 스케줄링, 데이터 스트림 처리 등 |
삽입/삭제 시간 복잡도 | O(1) | O(1) |
기타 연산 | peek() (맨 위 데이터 확인) | front() (맨 앞 데이터 확인) |
메모리 사용 | 상수 크기 (하나의 끝에서만 처리) | 양쪽 끝을 모두 처리 (양방향) |