[그림으로 쉽게 배우는 자료구조와 알고리즘] 배열 연결리스트 스택 큐 덱 해시테이블 셋

* 해당 포스팅은 그림으로 쉽게 배우는 자료구조와 알고리즘- by 감자 멘토님 강의를 수강후 작성하는 글 입니다.

KEYWORD

배열

• 설명(한줄로): 연속된 메모리 공간에 데이터를 저장하는 선형 자료구조.

• 시간복잡도:

  • 접근: O(1)

  • 삽입/삭제: O(n) (중간/앞에서), O(1) (끝에서)

  • 탐색: O(n) (정렬되지 않은 경우), O(log n) (정렬된 경우)

• 유리한 케이스: 인덱스를 통해 데이터를 빠르게 접근할 때, 데이터 크기가 고정되어 있고 삽입/삭제가 자주 일어나지 않는 경우.

연결리스트 (Linked List)

• 설명(한줄로): 각 노드가 데이터와 다음 노드를 가리키는 포인터로 연결된 선형 자료구조.

• 시간복잡도:

  • 접근: O(n)

  • 삽입/삭제: O(1) (노드를 알고 있을 때)

  • 탐색: O(n)

• 유리한 케이스: 크기가 동적이고, 삽입/삭제가 빈번하게 일어나는 경우. 특히, 중간에 데이터가 삽입되거나 삭제될 때.

스택 (Stack)

• 설명(한줄로): 후입선출(LIFO, Last In First Out) 방식으로 데이터를 처리하는 자료구조.

• 시간복잡도:

  • 접근: O(n)

  • 삽입/삭제: O(1) (top에서)

  • 탐색: O(n)

• 유리한 케이스: 함수 호출 스택, 되돌리기 기능 등 후입선출 방식이 필요한 경우.

큐 (Queue)

• 설명(한줄로): 선입선출(FIFO, First In First Out) 방식으로 데이터를 처리하는 자료구조.

• 시간복잡도:

  • 접근: O(n)

  • 삽입/삭제: O(1) (front와 rear에서)

  • 탐색: O(n)

• 유리한 케이스: 주문 처리 시스템, 프린터 대기열 등 선입선출 방식이 필요한 경우.

덱 (Deque, Double-Ended Queue)

• 설명(한줄로): 양쪽 끝에서 삽입과 삭제가 가능한 자료구조.

• 시간복잡도:

  • 접근: O(n)

  • 삽입/삭제: O(1) (양쪽 끝에서)

  • 탐색: O(n)

• 유리한 케이스: 양방향에서 삽입/삭제가 자주 일어나는 경우. 예를 들어, 양쪽에서 데이터를 넣고 빼야 하는 데크나 스케줄링 시스템.

해시테이블 (Hash Table)

• 설명(한줄로): 해시 함수를 이용해 키를 인덱스로 변환하여 데이터를 저장하는 자료구조.

• 시간복잡도:

  • 접근: O(1) (평균), O(n) (최악의 경우)

  • 삽입/삭제: O(1) (평균), O(n) (최악의 경우)

  • 탐색: O(1) (평균), O(n) (최악의 경우)

• 유리한 케이스: 키-값 쌍으로 데이터를 저장하고 빠르게 검색할 때. 특히, 데이터의 크기가 클 때 빠른 검색이 필요할 경우.

셋 (Set)

• 설명(한줄로): 중복되지 않는 고유한 값들을 저장하는 자료구조.

• 시간복잡도:

  • 접근: O(1) (해시셋인 경우)

  • 삽입/삭제: O(1) (평균), O(n) (최악의 경우)

  • 탐색: O(1) (평균), O(n) (최악의 경우)

• 유리한 케이스: 중복이 없는 고유한 데이터를 관리할 때, 또는 값이 존재하는지 빠르게 확인할 때.