자료구조 Data Structure

1. Stack (callstack의 stack/ Last-In First-Out)

박스를 쌓아놓은듯한 구조

자료를 넣는다 = push

자료를 뺀다 = pop

 

Big O (얼마나효율성을 갖는지 따짐/어떤 작업을 하는데 얼마나걸리는지 )

Insertion : O(1) //항상 일정한 시간이 걸리면 1

Deletion : O(1) 

Search : O(n) //stack의 양(size)이 n이면 찾을 때 걸리는 시간(시간복잡도)은 O(n)

 

Real Life Use Cases

Undo/Redo Machanism 취소하기

Backwards/Forwards Mechanism of Browsers 뒤로/앞으로가기

Call Stack

 

2.Queue 

enqueue : 자료추가

dequeue : 자료빼기

stack과 비슷함.

줄 서있는걸 Queue라고 함.

 

Big O

insertion : O(1) //항상 일관된 시간이 걸림 (그래프로 그렸을 때)

deletion : O(1)

search : O(n) //queue에 담긴 자료의 갯수(n)

항상 O(1)이 좋은건 아님.

 

3.LinkedList

LinkedList is made of bunch of nodes(집합 중 하나) that point to the next one in the list

줄서지 않고 줄선 효과를 볼 수 있음.

 

Big O

Insertion: O(1)

Deletion: O(1)

Search: O(n)

 

어딘가에 추가하고 싶다면 찾고(search) 추가(insertion)

 

 

Liknked List vs Array List

.

주요사항

해당자료구조의 개념이해

탐색, 삽입, 제거 등의 연산에 대한 시간복잡도 이해

실제 적용될 수 있는 케이스 탐구