자료구조의 종류 #1

2024.06.15 - [CS/자료구조] - 자료구조란 무엇인가?

 

앞선 글에서 자료구조를 사용하는 이유에 대해서 살펴보았다.

그렇다면 CS에서 대표적으로 사용하고 있는 자료구조와 그 특징들을 살펴보자.

선형구조

1. 배열

고정된 크기의 연속된 메모리에 데이터를 저장하는 구조

장점

• index를 통해서 접근 하기 때문에 빠르게 접근 가능하다.

단점

• 메모리를 정적으로 쓰다보니 데이터를 삽입, 삭제가 비효율적이다.

시간 복잡도

• Access : O(1)
• Search : O(n)
• Insertion : O(n)
• Deletion : O(n)

2. 연결 리스트(Linked List)

각 노드에는 데이터와 다음을 가리키는 주소를 가지고 있는 자료구조

장점

• 메모리를 동적을 활용 할 수 있다.
• 데이터의 삽익 및 삭제가 효율적이다.

단점

• 배열에 비해 데이터의 접근 및 검색이 비효율적이다.

시간 복잡도

• Access : O(n)
• Search : O(n)
• Insertion : O(1)
• Deletion : O(1)

3. Stack

후입선출(Last In First Out)구조로 마지막에 삽입된 데이터가 먼저 삭제되는 자료구조

사용 예

• 브라우저 뒤로가기
• 함수 호출
• 실행 취소

4. Queue

선입선출(First In First Out) 처음 삽입된 데이터가 먼저 삭제되는 자료구조

사용 예

• 작업 대기열
• BFS 너비우선탐색