# 자료구조 지식 - 1

<cs스터디_1주차, 자료구조>

1. 배열
byte단위로 메모리에 연속적 저장 선형 자료구조
boolean도 byte단위로 저장
크기 고정 o , 크기 변경 x
데이터 변경 o, 데이터 삽입 삭제 x => 메모리 낭비 없음

i번째 데이터에 접근 -> o(1), 메모리의 주소를 알 수 있으므로
x가 있는지 탐색 -> o(n), 순차적으로 다 돌아야 함



2. dinamic array(list, arraylist, vector)
메모리 상에서 데이터가 연속적으로 연결, 선형 자료구조
물리적으로 불변이지만, 논리적 가변되도록 코드상 구현
크기가 동적으로 변경 가능, 배열 기반
여유공간이 없으면, 사이즈를 2배(or 1.5배) 늘림 -> 언어마다 다르고 구현마다도 다름, c++는 2배, 자바는 1.5배
내부적으로 늘리는 로직(리사이징)상 메모리 낭비

i번째 데이터에 접근 -> o(1)
x가 있는지 탐색 -> o(n)
리스트 끝에 데이터 삽입 삭제 -> o(1)
리스트 끝이 아닌 곳의 데이터 삽입 삭제 -> o(n) //list.remove()같은거


- 리사이징
ex. init size=4, size 50%씩 증가
리사이징이 발생할때마다 "새로운 메모리 영역을 할당"하고, 데이터 "복사"



3. linked list
메모리 상에서는 데이터가 "불연속적"으로 저장, 논리적으로는 연속성 구현한 선형 자료 구조
값과 다음 값의 위치(메모리 주소)를 노드라는 이름의 쌍으로 저장
가변적인 메모리, 다음 노드의 주소값 저장 공간만큼의 메모리 추가 요소

i번째 데이터에 접근 -> o(n), 하나하나 타고 가야함
x가 있는지 탐색 -> o(n)
데이터의 삽입 삭제는 어느 위치에서나  -> o(1) but, 해당 노드에 접근하는 시간 제외한 것,
해당 노드에 접근하는 시간은 o(n)이므로 결국 o(n)이 될 수 있음

double linked list
중간의 데이터 찾는게 가장 오래 걸림 -> o(n)
로직 : 사이즈/2를 해서 내가 찾는 값이 그거보다 큰지 작은지 확인 후, 크면 뒤에서부터 찾기(작으면 앞에서부터 찾기)



4. queue
데이터가 연속적으로 저장되어 있는 선형 자료 구조
FIFO(선입선출)
Enqueue, Dequeue

i번째 데이터에 접근 -> o(n)
맨 앞 데이터 접근, 삭제 -> o(1)
맨 뒤 데이터 추가 -> o(1)
x가 있는지 탐색 -> o(n)



5. deque
한 방향으로만 데이터를 넣거나 꺼내는게 아니라 양쪽 끝에서 데이터를 추가하거나 꺼낼 수 있는 자료구조

i번째 데이터에 접근 -> o(n)
맨 앞/뒤 데이터 접근, 추가,삭제 -> o(1)
x가 있는지 탐색 -> o(n)




6. stack
데이터가 연속적(논리적)으로 연결되어 있는 선형 자료구조
LIFO(후입선출)
push, pop

스택 메모리를 초과하면 stack overflow error발생
비어있는 stack에서 pop하면 empty stack error발생
대표적으로 프로세스 메모리 영역에 사용, stack 영역이라고 부름(함수의 복귀 주소, 지역변수 저장등에 사용)

i번째 데이터에 접근 -> o(n)
맨 위/밑 데이터 접근, 삭제 -> o(1)
x가 있는지 탐색 -> o(n)