인터페이스	구현체	순서 유지	중복 허용	기타 설명
Array	ArrayList	✅	✅
Array	LinkedList	✅	✅
-----------	-----------------	----------	---------------------	---------------------------------------------------
Map	HashMap	❌	Key: ❌ / Value: ✅
Map	LinkedHashMap	✅	Key: ❌ / Value: ✅
Map	TreeMap	❌	Key: ❌ / Value: ✅	입력 순서는 유지되지 않지만, Key 기준으로 정렬
-----------	-----------------	----------	---------------------	---------------------------------------------------
Set	HashSet	❌	❌
Set	LinkedHashSet	✅	❌
Set	TreeSet	❌	❌	입력 순서는 유지되지 않지만, 데이터 기준 정렬

📦 Array

• 연속된 메모리 공간에 순서대로 저장
  👍 가장 빠른 순회 가능(iterate)한 자료 구조
  👎 크기 변경 제약이 있는 경우가 많음

🛠 구현체

• C++ : std::vector
• Java
  • ArrayList : 단방향 포인터 구조로 조회가 빠름
  • LinkedList : 양방향 포인터 구조로 삽입/삭제가 빠름
• Python / JavaScript : 기본 list/array가 동적으로 확장 가능

⏱ 일반적인 시간 복잡도

작업	시간 복잡도
조회	O(1)
삽입/삭제	O(N)

💡 사용 예시

🏆 점수 저장 → 순위 정렬 후 바로 접근
🎬 영화관 좌석 배열 → 좌석 번호로 바로 찾기
📅 날짜별 매출 기록 → 순서대로 기록하고 확인

---

🗺️ Map

• Key-Value 쌍으로 데이터 저장
  👍 Key만 알면 빠른 검색 가능, 값 변경·삭제도 빠름
  👎 Key가 중복되면 덮어씌워져서 데이터 유실 위험

🛠 구현체

• Hash 기반
  • C++ : unordered_map
  • Java : HashMap (Key 순서 보장 ❌), LinkedHashMap (Key 순서 보장)
• Tree 기반
  • C++ : std::map
  • Java : TreeMap (입력한 Key 데이터의 크기가 비교 가능한 경우 오름차순으로 자동 정렬)

⏱ 일반적인 시간 복잡도

작업	시간 복잡도
Hash 기반 접근	O(1)
Tree 기반 접근	O(logN)

💡 사용 예시

🔎 사용자 ID로 개인정보 매핑 → 로그인 처리
🏷️ 상품 코드로 재고 조회 → 쇼핑몰 장바구니 기능

---

✅ Set

• 중복을 허용하지 않는 원소 집합
  👍 값이 있는지 검사 매우 빠름
  👎 데이터 순서가 없음

🛠 구현체

• C++ : unordered_map
• Java
  • HashSet : 입력 순서 보장 ❌
  • LinkedHashSet : 입력 순서를 보장
  • TreeSet : 입력한 데이터 크기가 비교 가능한 경우 오름차순으로 자동 정렬
• Python : set

⏱ 일반적인 시간 복잡도

작업	시간 복잡도
조회	O(1)
삽입/삭제	O(1)

✅ 사용 예시

🚫 블랙리스트 검사 → 차단 유저 조회
♻️ 이미 본 영화 중복 검사 → 중복 방지 추천 시스템

참고자료
[간단정리] List, Set, Map 특징 및 차이점(+ 구현체 )
출처: https://hahahoho5915.tistory.com/35 [넌 잘하고 있어:티스토리]