# 자료구조

- 자료구조란 데이터를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다.
- 가장 간단한 자료구조로는 배열이 있으며, 배열은 데이터를 순차적으로 저장하는 구조이다.
- 자료를 저장하는 방식에 따라 선형 구조와 비선형 구조로 나뉜다.
- 선형 자료구조는 순차적으로 데이터를 저장하는 구조이며, 비선형 자료구조는 트리나 그래프와 같이 계층적인 구조를 가진다.
- 선형 자료구조 : 데이터를 순차적으로 저장하는 자료구조
- 데이터들은 선(line)처럼 일렬로 늘어선 형태를 가진다.
- 하나의 데이터 뒤에 다음 데이터가 존재한다.
- 데이터들간의 앞뒤 관계가 1:1 관계를 가진다.
- 리스트, 스택, 큐 등이 선형 자료구조에 속한다
- 비선형 자료구조 : 데이터를 순차적으로 저장하지 않는 자료구조
- 데이터들은 계층적인 구조를 가진다.
- 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있다.
- 데이터들간의 앞뒤 관계가 1:N, N:N 관계를 가진다.
- 트리, 그래프 등이 비선형 자료구조에 속한다.

## 리스트(List)

- 자료구조 중 하나로, 순서가 있는 요소들의 모임
- 리스트의 특징
- 순서: 리스트의 요소들은 순서를 가지고 있어, 인덱스를 사용하여 접근할 수 있다.
- 가변성: 리스트의 크기는 동적으로 변경할 수 있으며, 요소를 추가하거나 삭제할 수 있다.
- 중복 허용: 리스트는 중복된 요소를 포함할 수 있다.

### 배열 리스트 (Array List)


- 내부 구조: **동적 배열** 을 사용하여 요소를 저장한다.
- 조회 속도: 인덱스를 사용하여 요소에 빠르게 접근할 수 있다.
- 추가/삭제 속도: 배열의 중간에 요소를 추가하거나 삭제하는 경우, 요소를 이동시켜야 하기 때문에 속도가 상대적으로 느리다.
- 메모리 사용량: LinkedList에 비해 메모리 사용량이 적다.
- 활용 시나리오: 조회가 빈번하고 추가/삭제가 상대적으로 적은 경우에 적합하다.

### Array List의 요소 추가 시



1. 메모리에 새로운 배열을 할당한다.
2. 기존 배열의 요소를 새로운 배열로 복사한다.
3. 새로운 요소를 추가한다.
4. 새로운 배열을 기존 배열로 설정한다.
5. 기존 배열을 메모리에서 해제한다.

---

### 연결 리스트 (Linked List)


- 내부 구조: **이중 연결 리스트를 사용**하여 요소를 저장한다.
- 조회 속도: 인덱스를 사용하여 요소에 접근할 때, 처음이나 끝에서 순차적으로 탐색해야 하므로 속도가 상대적으로 느리다.
- 추가/삭제 속도: 중간에 요소를 추가하거나 삭제하는 경우, 이웃하는 노드만 연결을 변경하면 되기 때문에 속도가 빠르다. (단, 인덱스를 찾는 과정에서의 탐색 시간은 제외)
- 메모리 사용량: 각 노드가 이전 및 다음 노드의 참조를 유지하므로 메모리 사용량이 상대적으로 높다.
- 활용 시나리오: 추가/삭제가 빈번하고 조회가 상대적으로 적은 경우에 적합하다.

### Linked List의 요소 삽입 시


1. 새로운 노드를 생성한다.
2. 마지막 노드의 다음 노드를 새로운 노드로 설정한다.

## 스택(Stack)


- LIFO(Last In, First Out) 원칙을 따르는 자료구조이다.
- 가장 최근에 삽입된 요소가 가장 먼저 제거된다.
- 함수 호출, 실행 콘택스트 관리등에 사용된다.
- 예시: 웹 브라우저의 뒤로 가기 기능

---

## 큐(Queue)


- FIFO(First In, First Out) 원칙을 따르는 자료구조이다.
- 가장 먼저 삽입된 요소가 가장 먼저 제거된다.
- 너비 우선 탐색(BFS), CPU 스케줄링, 캐시 구현 등에 활용된다.
- 작업이 순차적으로 처리되어야 하는 상황에 적합하다.
- 예시 : 은행의 대기열

### 데크 (Deque, Deouble-Ended Queue)


- 양쪽 끝에서 요소의 삽입과 삭제가 가능한 자료구조이다.
- 스택과 큐의 기능을 모두 포함하고 있다.
- 양방향 연결 리스트로 구현할 수 있다.

## 셋(Set)

- 중복을 허용하지 않는 자료구조
- 집합의 개념을 기반으로 하며, 모든 요소는 유일하다
- 데이터의 삽입, 삭제, 탐색이 빠르다

### 트리 셋 (Tree Set)

- 이진 검색 트리를 사용하여 셋(Set) 을 구현한 자료구조
- 이진 검색 트리를 사용하므로 정렬된 순서대로 저장한다.

### 해시 셋 (Hash Set)

- 헤시테이블을 사용하여 셋(Set) 을 구현한 자료구조
- 헤시테이블을 사용하므로 순서를 유지하지 않는다
- 일반적으로 트리셋보다 빠른 검색 성능을 제공한다

## 맵(Map)

- Key(키)랑 Value(값)으로 나눠서 데이터 관리하는 자료구조
- 값에 대한 중복은 허용하나, 키에 대한 중복은 허용하지 않는다
- 순서가 보장되지 않는다
- 데이터의 삽입, 삭제, 탐색이 빠르다
- 트리 맵 (Tree Map) : Tree Set을 사용하여 Key를 관리하는 Map
- 해시 맵 (Hash Map) : Hash Set을 사용하여 Key를 관리하는 Map

## 그래프 (Graph)


- 노드(node)와 간선(edge)으로 이루어진 자료구조이다.
- 노드는 그래프에서 위치를 나타내며, 간선은 노드들을 연결한다.
- 간선은 방향이 있을 수도 있고 없을 수도 있다. 방향성이 없는 그래프를 무향 그래프(undirected graph), 방향성이 있는 그래프를 유향 그래프(directed graph)라고 한다.
- 그래프는 실제로 다양한 상황에서 연결관계를 표현하고 분석하기 위한 자료구조이다.

## 트리 (Tree)


- 계층적인 구조를 가지며, 하나의 루트(root) 노드에서 시작하여 여러 개의 자식(child) 노드를 가질 수 있다.
- 각 노드는 하나의 부모(parent) 노드와 여러 개의 자식(child) 노드를 가질 수 있다.
- 트리는 실제로 계층적인 구조를 가진 데이터를 저장하고 탐색하기 위한 자료구조이다.

## 트리의 용어정리


- 노드의 차수 : 한노드가 가진 서브트리의 수
- 리프노드(단말,터미널) : 차수가 0인 노드
- 자식 노드 : 노드에 연결된 서브트리의 루트노드들
- 부모 노드 : 노드에 연결된 한단계 상위 레벨 노드
- 형제 노드 : 부모가 같은 노드
- 트리의 차수 : 트리노드들의 차수중 최대 차수
- 노드의 레벨 : 노드가 속한 트리의 깊이
- 트리의 높이 : 트리의 최대 레벨

## 이진 트리(Binary Tree)


- 자식노드가 최대 두 개인 노드들로 구성된 트리
- 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 부른다
- 순회방법에 따라 전위순회, 중위순회, 후위순회라고 부른다
- 전위 순회(Pre-order Traversal)
- 
- 중위 순회(In-order Traversal):
- 
- 특징: 이진 탐색트리에서 정렬된 순서로 노드를 방문한다.
- 후위 순회(Post-order Traversal):
- 

### 이진 트리의 종류


- 포화 이진 트리(Full binary tree)
- 모든 레벨에서 노드들이 모두 채워진 트리
- 완전 이진 트리(Complete binary tree)
- 왼쪽부터 노드가 순서대로 채워진 이진트리
- 편향 트리(Skewed binary tree)
- 왼쪽 또는 오른쪽 서브트리만 가지는 트리
- 최악의 경우에는 모든 노드를 탐색해야 하므로 시간 복잡도는 O(n)이 된다

### 이진 탐색 트리(Binary Search Tree, BST)


- 이진 탐색과 트리구조를 결합한 자료구조
- 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다
- 특징
- 검색 속도가 빠르다. O(logn)
- 삽입 및 삭제 연산이 효율적이다. O(logn)
- 이진 탐색트리의 조건
- 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드로 이루어져 있다.
- 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드로 이루어져 있다.
- 중복된 노드가 없어야 한다.
- 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.

> 이진 탐색트리의 높이가 매우 높아지면(예: 한쪽으로 치우친 트리), 검색, 삽입, 삭제 연산의 성능이 저하되는데, 이 경우, 균형 잡힌 이진 탐색트리(AVL 트리, 레드-블랙 트리 등)를 사용하여 성능을 개선할 수 있다.

## 해시 (Hash)


- 해시: 데이터를 고유한 고정 길이의 값으로 변환하는 과정이다.
- 해시 함수: 임의의 길이의 데이터를 고정된 길이의 데이터로 출력하는 함수이다
- 예를 들면 어떤 숫자를 10으로 나누었을 때 그 나머지를 구하는 함수도 일종의 해시 함수이다
- 특징
- 어떤 입력 값에도 항상 고정된 길이의 해시값을 출력한다
- 동일한 입력에 대해 항상 동일한 해시 값을 생성한다
- 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다
- 출력된 결과 값을 토대로 입력값을 유추할 수 없다
- 해시 값에서 원본 데이터를 쉽게 찾아낼 수 없다
- 해시 함수는 빠르게 해시 값을 생성한다

## 해시 테이블


- 해시 테이블은 컴퓨터 과학에서 매우 효율적인 자료 구조 중 하나로, 키(key)와 값(value)의 쌍을 저장하고 검색하기 위해 사용된다
- 해시 테이블은 해시 함수를 사용하여 키를 해시 코드(hash code)로 변환한 후, 이 해시 코드를 배열의 인덱스로 사용하여 값을 저장하거나 검색한다
- 해시함수를 사용하므로 해시 테이블은 일반적으로 빠른 검색, 삽입 및 삭제 작업을 제공한다

### 해시 충돌


- 서로 다른 key값에 대해 동일한 해시 값이 도출하는 현상
- 해시 함수 자체의 문제보다는 해시 테이블 크기의 물리적 한계로 인한 경우가 많다
- input으로 들어올 수 있는 key값은 무한하지만 해시 함수로 도출된 해시 값을 저장할 물리적 공간은 유한하기 때문
- 일반적인 충돌 해결 방법은 체이닝(Chaining)과 오픈 어드레싱(Open addressing)이 있다.

### 체이닝 (Chaining)


- 각 인덱스에 연결 리스트를 사용하여 동일한 해시 코드를 가진 키와 값의 쌍을 저장한다. 충돌이 발생하면 해당 인덱스의 연결 리스트에 새로운 항목을 추가한다

### 오픈 어드레싱 (Open Addressing)


- 충돌이 발생하면 다른 위치를 찾아 새로운 항목을 저장하는 방법아다. 선형 탐사, 제곱 탐사, 이중 해싱 등 여러 가지 오픈 어드레싱 방법이 있다

# Java Collection Framework


> 자바 컬렉션 프레임워크에는 그래프(Graph)와 관련된 직접적인 클래스나 인터페이스가 없는 이유는 그래프가 다양한 구현 방법과 활용 방식을 가지고 있어 범용적인 클래스나 인터페이스로 정의하기 어렵기 때문이다.

## List

List<String> list = new ArrayList<>();
// List<String> list = new LinkedList<>();

list.add("apple");
list.add("banana");
list.add("cherry");

System.out.println(list.get(1));

## Stack

Stack<String> stack = new Stack<>();

stack.push("apple");
stack.push("banana");
stack.push("cherry");

System.out.println(stack.pop());
System.out.println(stack.pop());

## Queue

Queue<String> queue = new LinkedList<>();

queue.add("apple");
queue.add("banana");
queue.add("cherry");

System.out.println(queue.poll());
System.out.println(queue.poll());

## Set

Set<String> set = new HashSet<>();
// Set<String> set = new TreeSet<>();

set.add("apple");
set.add("banana");
set.add("cherry");
set.add("apple");

for (String item : set) {
    System.out.println(item);
}

## Map

Map<String, Integer> map = new HashMap<>();
// Map<String, Integer> map = new TreeMap<>();

map.put("apple", 3);
map.put("banana", 5);
map.put("cherry", 2);

System.out.println(map.get("banana"));