자료구조

자료구조
메모리를 어떻게 구조를 만들어서 사용할 것인가?
메모리 안 데이터들을 효율적으로 다루기 위해 만들어진
데이터 참조방식

---

Stack
Last In First Out (LIFO)
제일 마지막에 들어온 데이터가 제일 먼저 나간다
ex) ctrl + z , 햄버거 놀이

스택 구현 함수
1차원 배열 : Push, Pop
리스트

---

Queue
First In First Out (FIFO)
제일 처음 들어온 데이터가 제일 빨리 나간다.
ex) 줄 선 순서대로 처리, 프린터 출력 처리

정적인 어레이
장점 : 구현이 쉽다
단점 : 고정된 Queue 크기

동적인 어레이
장점: 자유로운 Queue 크기
단점 : 구현이 어렵다

대표 함수
Enqueue : Queue에 값을 집어 넣는다
Dequeue : Queue에서 값을 뺀다.
Size : Queue 크기를 확인
Enpty : Queue가 비었는지 확인  

---

List
어레이 사이즈 미리 지정하는 정적 어레이와 달리
데이터가 들어올 때마다 동적으로 메모리 할당하는 자료구조

Singly Linked List
노드안에 링크 1개, 단방향 진행

Doubly Linked List
노드안에 링크 2개, 양방향 진행

Circular Linked List
마지막 노드가 첫번째 노드롤 가르켜 원 모양 회전

링크 하나 => 4바이트 소모

탐색, 정렬 자주 한다 => 배열

추가,삭제가 많다 => 연결 리스트

메모리 사이즈를 모를때
어레이 < 리스트

데이터 하나당 소모되는 메모리양
어레이 > 리스트

중간 값 추가, 삭제
어레이 < 리스트

 

https://medium.com/@lyhlg0201/immersive-sprint-js-linkedlist-4edcb5928a9e

---

Hash Table
함수를 사용하여 키 값을 데이터 공간 주소로 변환 후
해당 주소에 데이터를 넣는 자료 구조

중복된 주소값에 대한 처리 ?
Linked List
연결 리스트로 연결
단점 : 연결리스트가 길어질수록 성능 낮아짐

Linear probing
충돌 발생 => 다음방이 빈방 => 데이터 삽입
빈공간이 없다 => 맨 처음으로 가서 검사
주변에 데이터 공간이 비어있지 않으면 
모든 공간 탐색 해야 함

---

Tree
하나의 뿌리에서 뻗어나가는 모양
자식의 자식 형태
ex) 회사 조직도, DOM트리구조

Root Node : 가장 상위 노드
Leaf Node : 자식 노드X, 가장 하단 노드
차수 : 노드에 연결된 서브 트리의 개수
Binary Tree (이진트리) : 한 트리내의 차수가 2개 이하
Level : 루트 노드부터 해당 노드 경로 찾는데 방문한 총 노드 수

Linear Search tree 선형 탐색
처음부터 모든 값 비교 후 찾는다
ex) 메뉴판에서 메뉴찾기
장점 : 구현 쉽다, 정렬이 안되어도 됨
단점 : 시간이 오래걸림


Binary Search Tree 이진 탐색
반씩 범위를 나누어 가면서 분할정복 하여 탐색
장점 : 속도가 빠르다
단점 : 자료구조 안 값들이 정렬되어 있어야함

왼쪽 자식 노드 : 부모보다 작은 값이여야 함
오른쪽 자식 노드 : 부모보다 큰 값이여야 함

 

---

- 참고자료
https://im-developer.tistory.com/121?category=828401
https://www.youtube.com/watch?v=S49nm3SYZmY