[DataStructure] 자료구조의 종류

저기요 여기 배열 안에 사람 있어요

자료구조는 왜 필요할까?

자료구조는 데이터를 효율적으로 저장하고 관리하기 위해 사용되는 구조
각 자료구조는 특정한 상황에서 데이터를 다루는 데 최적화되어 있다.

1. 기본 자료구조

• 배열 (Array): 동일한 타입의 요소를 연속된 메모리 공간에 저장하는 자료구조로 고정된 크기를 가지며, 인덱스를 통해 빠르게 접근할 수 있다.
  보통 특정 요소를 빠르게 읽어야 할 때 사용한다.

• 연결 리스트 (Linked List): 요소들이 노드 형태로 존재하며, 각 노드는 다음 노드를 가리키는 포인터를 포함한다. 크기가 가변적이며, 삽입과 삭제가 배열보다 효율적이고 배열과 달리 크기가 가변적이라 메모리 낭비가 적다.

  	- 단일 연결 리스트: 각 노드가 다음 노드를 가리킴
  	- 이중 연결 리스트: 각 노드가 이전 및 다음 노드를 가리킴
  	- 원형 연결 리스트: 마지막 노드가 처음 노드를 가리킴

2. 선형 자료구조

• 스택 (Stack): LIFO (Last In, First Out) 원칙을 따르는 자료구조
  요소의 삽입과 삭제는 스택의 한쪽 끝에서만 일어난다.
  대표적인 연산으로는 push, pop 등이 있다.

• 큐 (Queue): FIFO (First In, First Out) 원칙을 따르는 자료구조
  요소가 한쪽 끝에서 삽입되고 반대쪽 끝에서 제거된다.
  변형된 큐로는 원형 큐, 우선순위 큐 등이 있다.
  *tmi: 리그오브레전드에서 사용하는 단어인 큐도 이와 같은 원리

• 덱 (Deque): 양쪽 끝에서 삽입과 삭제가 가능한 자료구조
  스택과 큐의 기능을 모두 수행할 수 있다.

3. 비선형 자료구조

• 트리 (Tree): 계층 구조를 표현하는 자료구조로, 부모-자식 관계를 가진다.

  	- 이진 트리 (Binary Tree): 각 노드가 최대 두 개의 자식을 가진다.
  	- 이진 탐색 트리 (BST): 이진 트리의 일종으로, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다  
  	- AVL 트리: 자체 균형 이진 탐색 트리로, 삽입과 삭제 시 균형을 유지한다. 
      - 힙 (Heap): 이진 트리 기반의 자료구조로, 최대값 또는 최소값을 빠르게 찾을 수 있다. 최대 힙(max heap)과 최소 힙(min heap)으로 구분된다.

• 그래프 (Graph): 정점과 간선의 집합으로, 정점들이 간선으로 연결되어 있는 구조입니다.

  	- 무방향 그래프: 간선이 양방향
  	- 유방향 그래프: 간선이 특정 방향으로만 연결됨
  	- 가중치 그래프: 간선에 가중치가 부여된 그래프

4. 집합 및 사전 자료구조

• 집합 (Set): 중복되지 않는 요소의 집합. 주로 해시 테이블이나 이진 탐색 트리를 사용해 구현된다.

• 맵/딕셔너리 (Map/Dictionary): 키-값 쌍을 저장하는 자료구조로, 키를 통해 값을 효율적으로 검색할 수 있습니다. 코틀린이나 자바의 HashMap, 파이썬의 dict 등이 이에 해당합니다.

5. 고급 자료구조

• 트라이 (Trie): 문자열 검색을 빠르게 수행하기 위한 트리 형태의 자료구조.

• 세그먼트 트리 (Segment Tree): 배열의 특정 구간의 합이나 최댓값을 효율적으로 계산할 수 있는 트리

• B-트리 (B-Tree): 자식 노드의 수가 2개 이상일 수 있는 트리로, 데이터베이스나 파일 시스템에서 사용된다.

• 레드-블랙 트리 (Red-Black Tree): 이진 탐색 트리의 일종으로, 균형을 유지하며 삽입과 삭제 연산의 시간복잡도를 𝑂(log⁡𝑛)으로 보장한다.

6. 기타 자료구조

• 해시 테이블 (Hash Table): 해시 함수를 사용해 데이터를 키-값 쌍으로 저장하며, 빠른 검색과 삽입을 제공한다.
  (위에서 본 자바와 코틀린에서 사용하는 HashMap도 Map 인터페이스를 해시 테이블을 사용하여 구현되어 있다.)

• 비트맵 (Bitmap): 비트 배열을 사용해 데이터를 효율적으로 저장하며, 주로 집합이나 블룸 필터 구현에 사용한다.