[Java] ArrayList vs LinkedList, HashSet vs TreeSet 비교

 

목차

 

 

컬렉션 프레임워크의 인터페이스를 이해했다면, 이제 실제 구현체들의 차이를 살펴볼 차례입니다.

같은 인터페이스를 구현하더라도 내부 구조와 성능 특성이 완전히 다르기 때문에 상황에 맞는 선택이 정말 중요하죠.

 

이번 글에서는 List의 대표 구현체인 ArrayList와 LinkedList, Set의 대표 구현체인 HashSet과 TreeSet의 특징과 성능을 예제 코드와 함께 비교해 보겠습니다.

---

📦 ArrayList vs LinkedList

ArrayList

ArrayList는 동적 배열(Dynamic Array) 구조로, 내부적으로 Object 배열을 사용해 요소를 저장합니다.

List<String> arrayList = new ArrayList<>();
arrayList.add("Apple");    // 인덱스 0
arrayList.add("Banana");   // 인덱스 1
arrayList.add("Cherry");   // 인덱스 2

// 인덱스로 빠른 접근
String fruit = arrayList.get(1);  // "Banana" - O(1)

 

ArrayList 내부 구조

[Apple] [Banana] [Cherry] [null] [null] [null] ...
   0        1        2       3      4      5

 

✅ ArrayList 특징

• 빠른 인덱스 접근 (O(1))
• 끝에 추가는 빠름 (O(1)), 중간 삽입/삭제는 느림 (O(n))
• 메모리 효율적 (배열 기반)

 

LinkedList

LinkedList는 이중 연결 리스트(Doubly Linked List) 구조로, 각 노드가 이전/다음 노드를 참조합니다.

List<String> linkedList = new LinkedList<>();
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.add("Cherry");

// 처음이나 끝에 추가하기 쉬움
linkedList.addFirst("Apricot");  // 맨 앞에 추가
linkedList.addLast("Date");      // 맨 뒤에 추가

 

LinkedList 내부 구조

[Apricot] ↔ [Apple] ↔ [Banana] ↔ [Cherry] ↔ [Date]

 

✅ LinkedList 특징

• 양 끝 삽입/삭제 빠름 (O(1))
• 중간 삽입/삭제 느림 (O(n))
• 인덱스 접근 느림 (O(n))
• 노드 포인터로 인한 메모리 오버헤드 발생

 

언제 사용할까?

🔸 ArrayList

• 인덱스 접근이 빈번할 때
• 데이터 추가/조회가 많고 중간 삽입/삭제가 적을 때
• 메모리 사용량을 최소화해야 할 때

🔸 LinkedList

• 양 끝 삽입/삭제가 잦을 때
• Queue, Stack 자료구조로 활용할 때
• 데이터 크기가 자주 변할 때

---

🔄 HashSet vs TreeSet

HashSet 

HashSet은 해시 테이블(Hash Table) 기반으로 요소를 저장합니다.

Set<String> hashSet = new HashSet<>();
hashSet.add("Banana");
hashSet.add("Apple");
hashSet.add("Cherry");

System.out.println(hashSet);  // 순서 보장 안됨 (해시값에 따라 결정)
// 출력 예: [Cherry, Apple, Banana]

 

✅ HashSet의 특징

• 순서 보장 안됨: 해시값에 따라 저장 위치 결정
• 빠른 성능: 평균 O(1) 시간복잡도
• null 허용: null 값을 하나 저장할 수 있음

 

TreeSet 

TreeSet은 Red-Black Tree(이진 검색 트리의 한 종류) 구조로 요소를 자동 정렬합니다.

Set<String> treeSet = new TreeSet<>();
treeSet.add("Banana");
treeSet.add("Apple");
treeSet.add("Cherry");

System.out.println(treeSet);  // 자동 정렬됨
// 출력: [Apple, Banana, Cherry]

 

✅ TreeSet의 특징

• 자동 정렬: 요소들이 자동으로 정렬된 상태 유지
• NavigableSet 구현: 범위 검색, 근접 값 찾기 등 가능
• null 불가: null 값을 저장할 수 없음

 

언제 사용할까?

🔸 HashSet

• 순서보다 빠른 검색이 중요할 때
• 중복 없는 데이터 관리

🔸 TreeSet

• 정렬이 필요할 때
• 범위 검색(부분집합) 기능이 필요할 때

---

⏱️ 성능과 시간복잡도

연산	ArrayList	LinkedList	HashSet	TreeSet
추가(끝)	O(1)	O(1)	O(1) 평균	O(log n)
삽입/삭제(중간)	O(n)	O(n)	O(1) 평균	O(log n)
검색(contains)	O(n)	O(n)	O(1) 평균	O(log n)
순회	O(n)	O(n)	O(n)	O(n)
정렬된 순회	O(n log n)	O(n log n)	O(n log n)	O(n)

 

💡 Tip

• 데이터 양이 많고 순서 유지가 필요하다면 ArrayList를 고려하세요.
• 삽입/삭제가 빈번하다면 LinkedList가 유리합니다.
• 중복 제거와 빠른 검색이 필요하면 HashSet이 적합합니다.
• 데이터 정렬이 필요하면 TreeSet이 좋습니다.

---

🙌 마무리

이번 글에서는 Java 컬렉션 프레임워크에서 자주 사용하는 ArrayList, LinkedList, HashSet, TreeSet의 구조와 성능 차이를 비교해 봤습니다.

 

컬렉션을 선택할 때는 데이터의 사용 패턴(조회, 삽입/삭제, 검색, 정렬 여부)을 고려해 적절한 구현체를 선택하는 것이 중요합니다.

대부분의 경우 ArrayList와 HashSet으로 시작해 보고, 특별한 요구사항이 있을 때 다른 구현체로 확장하는 것이 좋습니다.

 

 

다음 글에서는 Java의 Map 계열(HashMap, TreeMap, LinkedHashMap)의 비교와 사용법을 다뤄보겠습니다.

궁금한 점이나 더 알고 싶은 부분이 있으면 댓글로 남겨주세요 😊