20. 자료구조 01/10 (1) - 패스트캠퍼스 백엔드 부트캠프 3기

1. ArrayList

• 배열의 추가 삭제
  • 순차적 추가와 삭제는 성능이 떨어지지않는다.
  • 이동은 비용이 높다.
• 추가
  • 배열생성(x2) -> 복사 -> 참조변경

2. LinkedList

• 추가
  • 이동 -> 생성 -> 연결

3. 스택과 큐

• 스택 : LIFO구조 마지막에 저장된 것을 제일 먼저 꺼내게 된다.
  • 주로 배열을 쓰고, LinkedList는 메모리를 절약할때 사용
• 큐 : FIFO구조 제일먼저 저장된 것을 제일 먼저 꺼내게 된다.

4. Deque : Stack과 Queue의 결합. 양끝에서 저장(offer)과 삭제(poll)가능

• 우선순위 큐(PriorityQueue) : 우선순위가 높은 것부터 꺼냄(null저장불가)
• 블락킹 큐(BlockingQueue) : 비어 있을 때 꺼내기와, 가득 차 있을 때 넣기를 지정된 시간동안 지연시킴 - 멀티쓰레드

5. Iterator

• 반복문의 조건식
• 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것

6. Arrays

• 배열을 다루기 편리한 메서드 제공
• binarySearch() : 정렬 -> 검색

7. 검색

• 순차 검색과 이진 검색 + 해싱(함수이용)

8. Comparator 와 Comparable

• 객체를 정렬하는데 필요한 메서드를 정의한 인터페이스(정렬기준을 제공)
• Comparable : 기본 정렬기준을 구현하는데 사용
• Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용
• compare : 뺄셈 보다 비교가 빠르다

9. HashSet과 TreeSet - 순서X, 중복X

• HashSet : 해싱
  
  • 객체를 저장하기전에 기존에 가은 객체가 있는지 확인한다.
  • equals()와 hashCode()가 오버라이딩 되어 있어야 함
• TreeSet : 범위 검색과 정렬에 유리한 컬렉션 클래스
  • 비교 기준 -> 저장
  • 트리 순회(전위, 중위, 후위) : 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.
    전위, 중위, 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.
  • 레벨 순회 : 큐를 이용

10. HashMap과 TreeMap - 순서X, 중복(키O, 값X)

• 해싱(hasing) : 범위 검색이 안됨(대용량 검색 빠름)
• 해시함수로 해시테이블(2차원)에 데이터를 저장, 검색
• 해시테이블은 배열과 링크드 리스트가 조합된 형태