Data Structure

스택과 큐

연결 리스트와 해시 테이블

그래프, 트리, 이진 탐색 트리 — -모두 그래프의 형태를 가지는 자료구조

시간 복잡도 / 공간 복잡도

시간 복잡도 수치가 작을수록 효율적인 알고리즘

비트 0 or 1

비트 8개 = 1 바이트

자료구조 (data structure)

-데이터 타입 : 하나의 데이터를 어떻게 해석할지 정의한 것

-자료 구조: 여러 데이터들의 묶음을 어떻게 저장하고 사용할지 정의 한 것

배열도 자료 구조의 하나!

Stack이나 Tree 역시 자료 구조

Stack은 쌓여있는 접시 더미와 같이 작동. 새로운 접시가 쌓일 때도 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가져 가는 것과 같음. (LIFO : Last In. First Out)

method

• push(element) — 요소를 스택의 최상단에 추가
• pop() — 스택의 최상단에서 요소를 제거하고 반환
• size() — 스택의 현재 요소 개수를 반환

Queue는 놀이공원에서 서는 줄과 같이 작동. 사람들이 맨 끝에 줄을 서고, 맨 앞에서 놀이기구에 탑승하는 것과 같음.
There’s also a thing called priority queue.
An example could be something like holding a special pass ticket while we are waiting for a roller coaster at an amusement park.

(FIFO: First In, First Out)

method

• enqueue(element) — 요소를 큐의 뒤에 추가
• dequeue() — 요소를 큐의 앞에서 제거하고 반환
• size() — 큐의 현재 요소 개수를 반환

Linked list

연결 리스트는 그 크기가 동적인 자료구조로, 자료구조를 구성하는 요소(we call this Node), Node의 연결로 이루어진 자료 구조입니다. 연결 리스트의 어떠한 임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖습니다. 추가와 삭제에 대해 O(n) (선형 시간)의 복잡도를 갖는 배열과는 다르죠.

*선형 시간(Linear time)이란 입력의 길이 n에 대하여, 어떤 알고리즘의 실행시간이 선형(O(n))이 되는 것을 뜻함.

예를 들어 입력된 숫자열의 총합을 계산하는 순서는 숫자열의 길이에 비례하는 시간이 필요

다만 이 추가와 삭제 속도에 대한 대가로, 연결 리스트의 각 노드는 인덱스를 갖지 않음. 그래서 어떤 특정 데이터를 연결 리스트에서 검색하고자 할 경우, 처음부터 전체 연결 리스트를 훑어야 하며, 이는 O(n) (선형 시간)의 복잡도를 필요로 함
cons of using Linked List :
use more memory than arrays
nodes in a linked list must be read in order from the beginning

Hash Table

해시 테이블(해시 맵이라고도 불림)은 키, 값 쌍을 저장하고 있는 자료 구조. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 “해시 함수(Hash Function)”라는 함수를 통해 특정 숫자값의 인덱스로 변환.
*Hash Function does not have a saving ability.

가변 크기의 입력값에서 고정된 크기의 출력값을 생성해 내는 과정을 Hashing

해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지