[Java] Collection(컬렉션) : 자료구조 및 시간복잡도 관점으로 보기

[Java] Collection(컬렉션) : 자료구조 및 시간복잡도 관점으로 보기
/category/Backend/Java

2024. 3. 7. 07:00

Collection Framework(컬렉션 프레임워크)

자바에서는 데이터를 저장하고 관리할 수 있는 다양한 방법을 제공한다. 컬렉션 프레임워크는 자료를 구조화하여 데이터를 쉽게 사용할 수 있도록 도와준다.

계층 구조로 살펴보는 Collection의 종류

https://en.wikipedia.org/wiki/Java_collections_framework#/media/File:Java.util.Collection_hierarchy.svg

Collection : 대부분의 컬렉션 클래스의 상위 인터페이스. 컬렉션의 기본 동작을 정의한다.

Set : 중복된 요소를 허용하지 않는 컬렉션 인터페이스. 구현체로는 HashSet,, TreeSet 등

List : 순서가 있는 요소들의 컬렉션 인터페이스. 인덱스에 의해 접근이 가능하다. 구현체로는 ArrayList, LinkedList, Vector(Extend -> Stack) 등

Queue : FIFO를 따르는 컬렉션 인터페이스. 구현체로는 LinkedList, PriorityQueue 등

Deque : 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 큐의 확장된 인터페이스. 구현체로는 ArrayDeque 등

https://en.wikipedia.org/wiki/Java_collections_framework#/media/File:Java.util.Map_hierarchy.svg

Map: Key-Value 쌍의 컬렉션 인터페이스, Collection이 상위 인터페이스가 아님. 구현체로는 HashMap, TreeMap 등

List

순서가 있는 데이터의 집합을 나타내는 인터페이스이다. 중복된 요소를 허용하고 각 요소는 인덱스 번호를 통해 접근할 수 있다.

ArrayList

List<String> arrayList = new ArrayList<>();

// 요소 추가
arrayList.add("Apple");
arrayList.add("Banana");
arrayList.add("Orange");

// 요소 조회
System.out.println("ArrayList: " + arrayList);
// ArrayList: [Apple, Banana, Orange]


// 요소 삭제
arrayList.remove("Banana");
System.out.println("ArrayList: " + arrayList);
// ArrayList: [Apple, Orange]

크기를 동적으로 조정할 수 있는 배열 기반의 리스트, 요소들은 인덱스를 사용하여 접근하고 관리한다.

삽입 및 삭제
- 끝에 Element 추가 및 삭제 : 평균적으로 O(1), 단 배열의 크기가 부족하여 동적으로 확장 시 배열을 복사해야 하므로 최악의 경우 O(N)
- 중간에 Element 추가 및 삭제 : O(N)
탐색 : O(N)

LinkedList

List<String> linkedList = new LinkedList<>();

// 요소 추가
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Orange");

// 요소 조회
System.out.println("LinkedList: " + linkedList);
// LinkedList: [Apple, Banana, Orange]


// 요소 삭제
linkedList.remove("Banana");
System.out.println("LinkedList: " + linkedList);
// LinkedList: [Apple, Orange]

이중 연결 리스트(Doubly Linked List)를 기반으로 한 리스트. 요소들은 인덱스가 아닌 노드들 사이의 링크를 통해 관리된다.
- 이중 연결 리스트 : 단일 연결 리스트는 (데이터 저장 필드 + 다음 데이터 링크) 라면, 이중 연결 리스트는 (데이터 저장 필드 + 이전 데이터 링크 + 다음 데이터 링크)로 구성된다.
- ArrayList와 달리 인덱스 기반으로 직접 접근이 아닌, 요소들을 순회하면서 원하는 위치의 데이터에 접근하게 된다.
삽입 및 삭제 : O(1) (최악 : O(n))
탐색 : O(N).

List<String> linkedList = new LinkedList<>();

// 리스트의 시작에 요소 추가
linkedList.addFirst("Apple");
linkedList.addFirst("Banana");
linkedList.addFirst("Orange");

// 리스트의 시작에서 요소 삭제
linkedList.removeFirst();

// 리스트의 끝에 요소 추가
linkedList.addLast("Grapes");

// 리스트의 끝에서 요소 삭제
linkedList.removeLast();

System.out.println("LinkedList: " + linkedList);

다음 경우는 연결 리스트의 시작과 끝에 요소를 추가하고 삭제하는 경우이다. 따라서 인덱스의 위치를 찾지 않아도 되므로 시간 복잡도는 O(1)에 해당한다.

List<String> linkedList = new LinkedList<>();

// 리스트의 중간에 요소 추가
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Orange");
// 인덱스 1에 "Grapes" 추가
linkedList.add(1, "Grapes");

// 리스트의 중간에 있는 요소 삭제
linkedList.remove(2);

System.out.println("LinkedList: " + linkedList);

반면 연결 리스트의 중간에 요소를 추가하고 삭제하는 경우이다. 해당 경우에는 삽입할 위치를 찾아야 하므로, 시간 복잡도가 O(N)이 되게 된다.

ArrayList vs LinkedList

다음은 두 개의 리스트가 사용하기 유리한 경우이다.

ArrayList

접근 속도가 추가 및 삭제보다 중요하거나, 데이터에 대한 추가/삭제가 순서대로 이루어지는 경우 사용하는 것이 유리

검색 : 인덱스로 Element에 직접 접근 -> 검색 속도가 빠름

추가 및 삭제 : 순차적으로 추가/삭제의 경우에는 요소들의 재배치가 필요하지 않으므로 빠르지만, 중간에 추가/삭제하는 경우는 요소들의 재배치가 필요하므로 느리다.

메모리 효율성 : 요소를 추가할 때 메모리가 자동으로 배열이 확장 -> 잉여 배열 메모리가 생김

LinkedList

무작위, 혹은 리스트의 중간에서 데이터에 대한 잦은 추가 및 삭제가 이루어지는 경우 사용하는 것이 유리

검색 : 접근하려는 인덱스에 대해 순차적 탐색(정방향/역방향 링크 순회) 탐색을 진행하므로 ArrayList보다 느리다.

-> 데이터가 많을수록 접근이 느림. 단, 순서대로 요소를 검색해야 하는 경우에는 유리하다.

추가 및 삭제 : ArrayList와 달리 요소들의 재배치가 아니라 Link 포인터만을 변경해주면 되므로 더 빠르다.

메모리 효율성 : 각 Element에 대해, 연결 포인터에 대한 메모리 할당이 추가로 필요하다.

Set

순서가 없는 데이터의 집합을 나타내는 인터페이스

동시에 중복된 요소를 허용하지 않는다. 즉 새로운 요소를 추가할 때 이미 존재하는 요소와 같은지를 판별하여 추가하게 된다.

HashSet

Set<String> hashSet = new HashSet<>();

// 요소 추가
hashSet.add("Apple");
hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Orange");

//요소 삭제
hashSet.remove("Orange");

// 요소 조회
System.out.println("HashSet: " + hashSet);
// HashSet: [Apple, Banana]

해시 테이블(Hash Table) 기반의 Set
삽입, 삭제, 탐색 : 평균적으로 O(1)이지만, 최악의 경우 O(n)
- 해시 테이블의 Collision 발생 시, 최악의 경우 하나의 버킷에 모든 데이터가 들어가 있어서 해싱의 의미가 없어지는 경우에 해당한다.

TreeSet

Set<String> treeSet = new TreeSet<>();

// 요소 추가
treeSet.add("Apple");
treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Orange");

// 요소 삭제
treeSet.remove("Orange");

// 요소 조회
System.out.println("TreeSet: " + treeSet);
// TreeSet: [Apple, Banana]

이진 탐색 트리(Binary Search Tree) 기반의 Set
삽입, 삭제, 탐색 :O(log n) (최악 O(n))

Map

Key-value의 쌍으로 저장되는 형태의 인터페이스.

Key는 고유해야 하며, Key 에 대응하는 Value은 중복될 수 있다. 순서가 없는 자료구조이다.

HashMap

Map<String, Integer> hashMap = new HashMap<>();

// 요소 추가
hashMap.put("Apple", 10);
hashMap.put("Banana", 5);
hashMap.put("Orange", 8);
hashMap.remove("Orange");

// 요소 조회
System.out.println("HashMap: " + hashMap);
// HashMap: {Apple=10, Banana=5}

// 키를 사용하여 값에 접근
int val = hashMap.get("Apple");
System.out.println("Apple의 Value : " + val);
// Apple의 Value : 10

해시 테이블(Hash Table) 기반의 Map
삽입, 삭제, 탐색 : 평균적으로 O(1)이지만, 최악의 경우 O(n)
- 해시 테이블의 Collision 발생 시, 최악의 경우 하나의 버킷에 모든 데이터가 들어가 있어서 해싱의 의미가 없어지는 경우에 해당한다.

TreeMap

Map<String, Integer> treeMap = new TreeMap<>();

// 요소 추가
treeMap.put("Apple", 10);
treeMap.put("Banana", 5);
treeMap.put("Orange", 8);
treeMap.remove("Orange");

// 요소 조회
System.out.println("TreeMap: " + treeMap);
// HashMap: {Apple=10, Banana=5}

// 키를 사용하여 값에 접근
int val = treeMap.get("Apple");
System.out.println("Apple의 Value : " + val);
// Apple의 Value : 10

이진 탐색 트리(Binary Search Tree) 기반의 Map
삽입, 삭제, 탐색 :O(log n) (최악 O(n))

Hash vs Tree

HashSet/HashMap

데이터의 추가 및 조회 속도가 빠르다.

데이터의 저장 순서가 중요하지 않은 경우에 유용

원래 Hash Table은 중복값이 많을 수록 검색 성능이 저하되었다(최악의 경우 하나의 버킷에 모여서 그 안을 전부 탐색해야 함) -> Set과 Map은 중복된 값을 허용하지 않아 걱정을 덜어도 되긴 하지만 데이터가 비슷한 패턴을 가져 같은 버킷에 모일 수도 있긴 하다.

추가 및 조회 속도가 중요하고. 데이터의 저장 순서가 중요하지 않은 경우 유리

TreeSet/TreeMap

요소들이 정렬되어 있어 범위 기반 검색이나 정렬된 순서로 데이터에 접근하는 경우 유리하다.

데이터의 추가 및 삭제 속도는 HashSet/HashMap보다 느리다.

범위 기반 검색이나 정렬된 순서로 데이터에 접근하는 경우 유리

스택과 큐

스택(Stack)

Stack<String> stack = new Stack<>();

// Push
stack.push("Apple");
stack.push("Banana");
stack.push("Orange");

// Pop
while (!stack.isEmpty()) {
    System.out.println("Pop: " + stack.pop());
}

// Pop: Orange
// Pop: Banana
// Pop: Apple

스택(Stack)을 구현하는 컬렉션
- Stack은 후입선출(LIFO), 최근 추가 요소가 가장 먼저 조회 및 제거된다.
삽입, 삭제(조회) : O(1)
탐색 : O(n) -> Stack은 Pop으로 삭제와 동시에 조회를 주로 하므로 이 외에 직접 데이터를 찾는 경우를 말한다.

큐(Queue)

Queue<String> queue = new LinkedList<>();

// enqueue
queue.offer("Apple");
queue.offer("Banana");
queue.offer("Orange");

// dequeue
while (!queue.isEmpty()) {
    System.out.println("Dequeue: " + queue.poll());
}

// Dequeue: Apple
// Dequeue: Banana
// Dequeue: Orange

큐(Queue)를 구현하는 컬렉션
- Queue는 선입선출(FIFO), 가장 먼저 추가된 요소가 가장 먼저 조회 및 제거된다.
- Queue 인터페이스에 대한 구현체로는 LinkedList를 사용하였다.
삽입, 삭제(조회) : O(1)
탐색 : O(n) -> Queue은 Pop으로 삭제와 동시에 조회를 주로 하므로 이 외에 직접 데이터를 찾는 경우를 말한다.

우선순위 큐(Priority Queue)

PriorityQueue<String> priorityQueue = new PriorityQueue<>();

// enqueue
priorityQueue.offer("Orange");
priorityQueue.offer("Apple");
priorityQueue.offer("Banana");

// dequeue (우선 순위에 따라서, 정렬(compareTo) 순서를 따름)
while (!priorityQueue.isEmpty()) {
    System.out.println("Dequeue: " + priorityQueue.poll());
}

// Dequeue: Apple
// Dequeue: Banana
// Dequeue: Orange

우선순위 큐(Priority Queue)를 구현하는 컬렉션
- 요소들이 우선순위에 따라 정렬되어 저장되는 Queue. 높은 우선순위를 가진 요소가 낮은 우선순위를 가진 요소보다 먼저 처리
- Element들을 저장 시 Heap 자료구조를 사용하여 우선순위(Object의 compareTo에 따른다)에 따라 정렬하게 된다. 따라서 시간 복잡도가 힙에 따라서 결정된다.
삽입, 삭제(조회) : O(1) (Binary Heap 사용 시)

덱(Deque)

Deque<String> deque = new ArrayDeque<>();

// enqueue
deque.addFirst("Apple");
deque.addLast("Banana");
deque.addLast("Orange");

// dequeue
while (!deque.isEmpty()) {
    System.out.println("Dequeue: " + deque.removeFirst());
}

// Dequeue: Apple
// Dequeue: Banana
// Dequeue: Orange

덱(Deque)를 구현하는 컬렉션
- 양쪽 끝에서 삽입 및 삭제가 가능한 Queue로서, Double-Ended-Queue라고도 불린다.
- Deque 인터페이스에 대한 구현체로는 ArrayDeque를 사용하였다.
삽입, 삭제(조회) : O(1)

정리

자료 구조	컬렉션	탐색	삽입	삭제
스택(Stack)	Stack	O(N)	O(1)	O(1) (조회, Pop)
큐(Queue)	Queue	O(N)	O(1)	O(1) (조회, Dequeue)
덱(Deque)	Deque	O(N)	O(1)	O(1) (조회, Dequeue)
우선순위 큐(Priority Queue)	PriorityQueue	O(N)	O(log n)	O(log n) (조회, Dequeue)
기반 : 동적 배열(Dynamic Array)	ArrayList	O(N)	평균 : O(1) 최악 : O(N)	평균 : O(1) 최악 : O(N)
기반 : 연결 리스트(LinkedList)	LinkedList	O(N)	평균 : O(1) 최악 : O(N)	평균 : O(1) 최악 : O(N)
기반 : 해시 테이블(Hash Table)	HashSet, HashMap	평균 : O(1) 최악 : O(N)	평균 : O(1) 최악 : O(N)	평균 : O(1) 최악 : O(N)
기반 : 이진 탐색 트리(Binary Search Tree)	TreeSet, TreeMap	평균 : O(log n) 최악 : O(N)	평균 : O(log n) 최악 : O(N)	평균 : O(log n) 최악 : O(N)

자료구조

스택: 후입선출 구조의 데이터 저장소.
큐: 선입선출 구조의 데이터 저장소.
덱: 양쪽 끝에서 삽입과 삭제가 가능한 자료 구조.
우선순위 큐: 우선순위에 따라 요소를 저장하고 반환하는 자료 구조.
동적 배열: 크기가 자동으로 조절되는 배열.
연결 리스트: 노드들이 링크로 연결된 자료 구조.
해시 테이블: 키와 값의 쌍을 저장하고, 키를 통해 값에 빠르게 접근하는 자료 구조.
이진 탐색 트리: 각 노드가 최대 두 개의 자식을 갖는 이진 트리로서, 정렬된 데이터나 연속된 범위 데이터를 빠르게 탐색하는 자료 구조.

컬렉션 비교

List : 순서가 있는 데이터의 집합. 중복된 요소를 허용. 인덱스 번호를 통해 접근 가능

Map : 순서가 없는 Key-value의 쌍의 데이터 집합. 중복된 Key 허용 X.

Set : 순서가 없는 데이터의 집합. 중복된 Element 허용 X.

ArrayList : 접근 속도가 추가 및 삭제보다 중요하거나, 데이터에 대한 추가/삭제가 순서대로 이루어지는 경우 사용하는 것이 유리
LinkedList : 무작위, 혹은 리스트의 중간에서 데이터에 대한 잦은 추가 및 삭제가 이루어지는 경우 사용하는 것이 유리

Hash [Set/Map] : 추가 및 조회 속도가 중요하고. 데이터의 저장 순서가 중요하지 않은 경우 유리
Tree [Set/Map] : 범위 기반 검색이나 정렬된 순서로 데이터에 접근하는 경우 유리

<함께 보기>

https://sjh9708.tistory.com/200

[자료구조/JAVA] 스택과 큐(Stack, Queue)

스택(Stack) 한 쪽 끝에서만 Item을 삭제하거나 새로운 Item을 저장하는 자료구조이다. 후입선출(Last In First Out, LIFO)의 원리를 따른다. 즉, 가장 최근에 추가된 요소가 가장 먼저 제거되는 구조이다.

sjh9708.tistory.com

'Backend > Java' 카테고리의 다른 글

[Java] 표준 입력 : Scanner와 BufferedReader + PS(코딩 테스트) 입력 패턴 정리 (0)	2024.04.16
[Java] 정렬(Sorting) : Comparator과 Comparable (0)	2024.03.07
[Java] 문자열(String) : 메서드, 형변환 및 StringBuilder & StringBuffer (0)	2024.03.05
[Java] Stream API 사용하기 (1)	2024.02.25
[Java] 람다식(Lambda Expression)과 함수형 프로그래밍 (1)	2024.02.25

데굴데굴 개발자의 기록

CATEGORIES