[ Algorithm ] 기초 자료구조와 시간복잡도

기초 자료구조 종류

• 배열
• 스택
• 큐
• 연결 리스트
• 해시 테이블, 해시 맵

배열

배열의 시간복잡도

• 검색: O(N)
• 삽입: O(N)
• 삭제: O(N)

스택

스택 시간복잡도

• 검색: O(N)
• 삽입: O(1)
• 삭제: O(1)

큐

큐 시간복잡도

• 검색: O(N)
• 삽입: O(1)
• 삭제: O(1)

연결 리스트

연결 리스트 시간 복잡도

• 검색: O(N)
• 삽입: O(1)
• 삭제: O(1)

해시 테이블

해시 테이블 시간 복잡도

평균

• 검색: O(1)
• 삽입: O(1)
• 삭제: O(1)

최악

• 검색: O(N)
• 삽입: O(N)
• 삭제: O(N)

해시 맵

• 키(key) - 값(value) 쌍을 저장하는 자료구조

• 저장 및 검색

  • 해시 테이블을 이용하여 키를 저장
  • 값은 그 키와 같은 위치에 저장
  • 검색도 키를 이용해서 저장된 위치를 찾는 게 전부

• 키는 위치 검색용

• 그 외엔 해시 테이블과 다른 게 없음