자료구조 정리

주요 자료구조 정리

컬렉션 프레임워크
List	Set	Map
ArrayList	HashSet	HashMap
LinkedList	TreeSet	HashTable
Vector		TreeMap

• List 인터페이스
  • 순서가 있는 데이터의 집합
  • 중복 허용
  • 주요 구현 클래스 - ArrayList, LinkedList
    • ArrayList
      • 동적 배열구조
      • 인덱스로 빠른 접근 가능
      • 삽입/삭제 시 요소 이동 필요
    • LinkedList
      • 이중 연결 리스트 구조
      • 삽입/삭제가 빠름
      • 순차 접근만 가능
    • Vector
      • 크기가 가변적인 배열구조
      • 동기화되어 있어 thread-safe함
        (thread-safe한 구현이 필요한경우에만 사용하는것을 권장 이외 경우엔 ArrayList 사용)
      • ArrayList와 유사하지만, Vector는 레거시 클래스로 간주
• Set 인터페이스
  • 순서 없는 데이터의 집합
  • 중복 불허
  • 주요 구현 클래스 - HashSet, TreeSet
    • HashSet
      • 해시 테이블로 구현
      • 삽입/검색/삭제 O(1) 시간복잡도
    • TreeSet
      • 이진 검색트리로 구현
      • 정렬된 상태 유지
• Map 인터페이스
  • 키 - 값 쌍으로 데이터 저장
  • 키 중복 불가, 값 중복 가능
  • 주요 구현 클래스 - HashMap, TreeMap
    • HashMap
      • 해시 테이블 사용
      • 키로 빠른 검색 가능
    • TreeMap
      • 키를 기준으로 정렬

기타 자료구조

• Stack
  • LIFO (Last In First Out) 구조 (반대쪽 이 막힌 빨대 //가장먼저 들어간것이 가장 늦게 나옴)
  • push(),pop() 연산 (push 집어 넣기 / pop 꺼내기)
• Queue
  • FIFO(First In First Out) 구조 (한방양으로만 흐르는 빨대 // 가장 먼저 들어간것이 가장 빠르게 나옴)
  • offer(),poll() 연산 (offer 집어 넣기 / poll 꺼내기)
• Deque
  • 양쪽에서 삽입/삭제 가능한 큐 (빨대이지만 양쪽으로 넣고 뺄 수 있는 구조 )
  • ArrayDeque로 구현가능

HashTable이란?

키 - 값 쌍의 데이터를 효율적으로 저장하고 검색하기 위한 자료구조로 다음과 같은 특징을 가진다

1. 해시 함수 사용 
   키를 해시 함수에 통과시켜 고유한 인덱스로 변환
2. 빠른 검색 및 삽입
   평균적으로 O(1) 시간 복잡도로 데이터에 접근가능
3. 키 - 값 저장
   각 데이터는 키와 값의 쌍으로 저장됨
4. 충돌 해결
   서로 다른 키가 같은 인덱스에 매핑될 때 발생하는 충돌을 해결하기 위한 메커니즘이 있음
5. 동적 크기 조정
   데이터 양에 따라 자동으로 크기를 조정할 수 있음

HashMap은 키- 값 쌍으로 저장 // HashSet은 값만 저장하며 중복을 허용하지 않는다