배열
시간 복잡도 : 검색(탐색) O(n), 삽입 O(n), 삭제 O(n)
맨 앞 또는 맨 뒤에 값을 삽입하는 경우 시간 복잡도가 O(1) 이 될 수 있으나
복잡도는 항상 최악의 상황을 기준으로 한다 그러므로 중간에 삽입, 삭제 할 경우
앞 뒤의 숫자들이 밀리거나 당겨질 수 있기 때문에 O(n) 으로 정한다
스택
시간 복잡도 : 검색 O(n), 삽입 O(1), 삭제 O(1)
LIFO Last-In, Last-Out
스택의 입출력이 발생하는 부분 스택 상단 top, 바닥 부분 bottom
top 의 위치를 기준으로 삭제 삽입이 이뤄지므로 시간 복잡도가 O(1) 이다
검색은 bottom - top 까지의 모든 값을 꺼내어 확인하고 다시 넣어주는 방식으로
접근해야되므로 시간 복잡도는 O(n) 이다
큐
시간 복잡도 : 검색 O(n), 삽입 O(1), 삭제 O(1)
FIFO First-In, First-Out
삭제할 때 front, 삽입할 때 back(rear) 위치로 관리
시간 복잡도는 스택과 동일하다
연결리스트
시간 복잡도 : 검색 O(n), 삽입 O(1), 삭제 O(1)
head 노드를 시작점으로 검색하여 특정 노드 또는 마지막 노드에 삽입, 삭제할 수 있다
해시테이블
시간 복잡도
평균 : 검색 O(n), 삽입 O(1), 삭제 O(1)
최악 : 검색 O(n), 삽입 O(n), 삭제 O(n)
비정형 데이터를 해시함수를 통해 32비트 정수를 리턴받아 나머지(%)계산으로 테이블 위치를 정한다
나머지 값이 같은 다른 데이터가 들어가야할 때 LinkedList 를 사용하여 삽입, 삭제할 수 있다
이 때 계속해서 한 곳에 데이터가 삽입, 삭제 되는 경우가 있으므로 시간 복잡도는 위와 같다
해시맵
키(key)-값(value) 쌍을 저장하는 구조
해시테이블을 이용하여 키를 저장, 값과 키는 같은 위치에 저장, 키를 이용해 저장된 위치를 검색
이 외에 구조는 해시 테이블과 동일하다
시간복잡도 정리표
.jpeg)
