자료구조 목록 (+java에서의 사용)

자료구조에는 크게 선형자료구조와 비선형 자료구조가 있으며 아래는 기본적으로 사용하는 자료구조들의 간략한 설명이다.

각 자료구조의 자세한 설명은 해당 블로그 다른글에 서술 되어있다. 

 

💫기본적인 자료구조 모음

1. 배열(Array)

• 설명: 동일한 타입의 요소들이 연속된 메모리 공간에 저장된 자료구조입니다.
• 특징: 인덱스를 통해 빠르게 접근 가능, 크기가 고정되어 있음.
• 사용 예: 정수 배열, 문자 배열 등.

2. 연결 리스트(Linked List)

• 설명: 각 요소가 노드로 구성되고, 각 노드는 데이터와 다음 노드에 대한 포인터를 가집니다.
• 특징: 동적 크기, 요소 삽입/삭제가 용이함, 임의 접근이 비효율적.
• 사용 예: 리스트, 큐, 스택 구현.

3. 스택(Stack)

• 설명: 후입선출(LIFO, Last In First Out) 원칙을 따르는 자료구조입니다.
• 특징: 요소 추가/삭제가 O(1) 시간복잡도를 가짐, 주로 재귀적인 문제 해결에 사용됨.
• 사용 예: 함수 호출 스택, 후위 표기법 계산기.

4. 큐(Queue)

• 설명: 선입선출(FIFO, First In First Out) 원칙을 따르는 자료구조입니다.
• 특징: 요소 추가/삭제가 O(1) 시간복잡도를 가짐, 순차적인 작업 처리에 적합.
• 사용 예: 프린터 작업 대기열, 너비 우선 탐색(BFS).

5. 해시 테이블(Hash Table)

• 설명: 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용하여 키를 인덱스로 변환해 데이터를 저장합니다.
• 특징: 평균적으로 O(1) 시간복잡도로 빠른 검색, 삽입, 삭제가 가능.
• 사용 예: 데이터베이스 인덱스, 캐시 구현.

6. 트리(Tree)

• 설명: 계층적인 구조를 가지며, 노드가 부모-자식 관계를 가집니다.
• 특징: 다양한 트리 구조가 있으며, 빠른 검색, 삽입, 삭제가 가능.
• 사용 예: 파일 시스템, 이진 탐색 트리(BST).

6.1. 이진 트리(Binary Tree)

• 설명: 각 노드가 최대 두 개의 자식을 가질 수 있는 트리입니다.
• 특징: 균형을 맞추면 검색, 삽입, 삭제가 O(log n) 시간복잡도를 가짐.
• 사용 예: 이진 탐색 트리, 힙.

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

• 설명: 이진 트리의 일종으로, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 특성을 가집니다.
• 특징: 정렬된 데이터를 빠르게 검색, 삽입, 삭제 가능.
• 사용 예: 데이터베이스 검색, 범위 검색.

6.3. 힙(Heap)

• 설명: 완전 이진 트리로, 부모 노드가 자식 노드보다 크거나(최대 힙), 작아야(최소 힙) 합니다.
• 특징: 우선순위 큐 구현에 사용, 최댓값 또는 최솟값을 빠르게 찾을 수 있음.
• 사용 예: 우선순위 큐, 힙 정렬.

7. 그래프(Graph)

• 설명: 정점(노드)들과 이들을 연결하는 간선(엣지)으로 구성된 자료구조입니다.
• 특징: 방향 그래프, 무방향 그래프 등 다양한 형태가 있으며, 복잡한 관계를 나타낼 수 있음.
• 사용 예: 소셜 네트워크, 지도 경로 찾기.

8. 트라이(Trie)

• 설명: 문자열을 저장하고 빠르게 검색하기 위한 트리 기반 자료구조입니다.
• 특징: 키가 문자열인 데이터를 효율적으로 저장하고 검색할 수 있음.
• 사용 예: 자동 완성, 사전 구현.

💫이외의 많이 쓰는 자료구조 모음

1. 덱(Deque)

• 설명: 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐입니다.
• 특징: 이중 끝 큐로, 앞과 뒤에서 O(1) 시간복잡도로 삽입/삭제가 가능.
• 사용 예: 슬라이딩 윈도우 알고리즘, 회전하는 큐.

2. 우선순위 큐(Priority Queue)

• 설명: 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 큐입니다.
• 특징: 힙을 사용하여 구현하는 경우가 많으며, 삽입/삭제가 O(log n) 시간복잡도를 가짐.
• 사용 예: 작업 스케줄링, 다익스트라 알고리즘.

3. 집합(Set)

• 설명: 중복되지 않는 요소들의 컬렉션입니다.
• 특징: 보통 해시 테이블이나 이진 탐색 트리를 기반으로 구현되며, 요소 추가, 삭제, 검색이 평균적으로 O(1) 시간복잡도를 가짐.
• 사용 예: 집합 연산(합집합, 교집합 등), 고유값 저장.

4. 맵(Map) 또는 사전(Dictionary)

• 설명: 키-값 쌍을 저장하는 자료구조로, 각 키는 유일해야 합니다.
• 특징: 보통 해시 테이블이나 트리를 기반으로 구현되며, 키를 이용한 빠른 검색, 삽입, 삭제가 가능.
• 사용 예: 데이터베이스 인덱스, 캐시, 키-값 저장소.

5. 그래프(Graph)의 특수 형태

5.1. 방향성 비순환 그래프(DAG, Directed Acyclic Graph)

• 설명: 방향성이 있으며 순환이 없는 그래프입니다.
• 특징: 위상 정렬이 가능, 종속성 관리에 유용.
• 사용 예: 작업 스케줄링, 컴파일러 최적화.

5.2. 가중치 그래프(Weighted Graph)

• 설명: 각 간선이 가중치를 가지는 그래프입니다.
• 특징: 최단 경로 알고리즘에 사용.
• 사용 예: 다익스트라 알고리즘, 최소 신장 트리.

6. B-트리 및 변형

6.1. B-트리(B-Tree)

• 설명: 데이터베이스와 파일 시스템에서 널리 사용되는 자가 균형 이진 탐색 트리의 일반화입니다.
• 특징: 노드 하나에 여러 키를 저장, 높이가 낮아 검색, 삽입, 삭제가 효율적.
• 사용 예: 데이터베이스 인덱스, 파일 시스템.

6.2. B+트리(B+ Tree)

• 설명: B-트리의 변형으로, 리프 노드가 링크드 리스트로 연결되어 있습니다.
• 특징: 범위 쿼리 수행에 효율적.
• 사용 예: 데이터베이스 인덱스.

7. 피보나치 힙(Fibonacci Heap)

• 설명: 복잡한 우선순위 큐 연산을 효율적으로 수행하는 힙입니다.
• 특징: 삽입과 키 감소가 매우 빠름, 다익스트라 알고리즘 등에서 사용.
• 사용 예: 그래프 알고리즘에서의 최단 경로 계산.

8. AVL 트리

• 설명: 자가 균형 이진 탐색 트리로, 각 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 최대 1입니다.
• 특징: 검색, 삽입, 삭제가 O(log n) 시간복잡도를 가짐.
• 사용 예: 정렬된 데이터를 저장하고 빠르게 검색해야 할 때.

9. 레드-블랙 트리(Red-Black Tree)

• 설명: 자가 균형 이진 탐색 트리로, 각 노드가 빨강 또는 검정으로 색칠됩니다.
• 특징: 검색, 삽입, 삭제가 O(log n) 시간복잡도를 가짐, 균형 유지.
• 사용 예: 맵과 세트의 내부 구현.

10. 세그먼트 트리(Segment Tree)

• 설명: 특정 범위의 쿼리와 업데이트를 효율적으로 처리하는 트리입니다.
• 특징: 구간 합, 최댓값, 최솟값 등의 쿼리를 O(log n) 시간복잡도로 처리.
• 사용 예: 범위 쿼리가 필요한 문제.

11. 펜윅 트리(Fenwick Tree)

• 설명: 이진 인덱스 트리로, 부분 합 쿼리와 업데이트를 효율적으로 수행.
• 특징: 구간 합 쿼리와 업데이트를 O(log n) 시간복잡도로 처리.
• 사용 예: 주식 거래 시스템, 구간 합 문제.

---

💫 Java에서의 자료구조 사용

자바에서는 Java Collections Framework를 통해 아래와 같이 다양한 자료구조를 제공한다.

1. 배열 (Array)

• 특징: 고정 크기, 인덱스를 통해 빠르게 접근 가능.
• 메서드:
  • int[] array = new int[10]; // 배열 선언 및 생성
  • array.length // 배열의 길이

2. List (ArrayList)

• 특징: 동적 배열, 크기 자동 조절. / 순서 있음, 중복된 요소 허용
• 메서드:
  • add(E e): 리스트의 끝에 요소를 추가
  • add(int index, E element): 지정된 위치에 요소를 삽입
  • get(int index): 지정된 위치에 있는 요소를 반환
  • remove(int index): 지정된 위치의 요소를 제거
  • set(int index, E element): 지정된 위치의 요소를 지정된 요소로 바꿈
  • contains(Object o): 리스트에 특정 요소가 포함되어 있는지 확인
  • indexOf(Object o): 리스트에서 특정 요소의 첫 번째 발생 위치를 반환
  • size(): 리스트의 요소 개수를 반환
  • clear(): 리스트의 모든 요소를 제거
  • subList(int fromIndex, int toIndex): 리스트의 특정 범위의 요소들로 새로운 리스트를 반환

3. LinkedList

• 특징: 양방향 연결 리스트, 요소 삽입/삭제가 용이.
• 메서드:
  • add(E e) // 요소 추가
  • addFirst(E e) // 첫 번째 위치에 요소 추가
  • addLast(E e) // 마지막 위치에 요소 추가
  • remove(int index) // 특정 인덱스의 요소 제거
  • removeFirst() // 첫 번째 요소 제거
  • removeLast() // 마지막 요소 제거
  • get(int index) // 특정 인덱스의 요소 반환
  • getFirst() // 첫 번째 요소 반환
  • getLast() // 마지막 요소 반환
  • size() // 리스트의 크기 반환
  • clear() // 모든 요소 제거
  • contains(Object o) // 특정 요소가 포함되어 있는지 확인

4. Stack

• 특징: 후입선출 (LIFO).
• 메서드:
  • push(E item) // 요소 추가
  • pop() // 맨 위의 요소 제거 및 반환
  • peek() // 맨 위의 요소 반환
  • isEmpty() // 스택이 비어 있는지 확인
  • search(Object o) // 특정 요소의 위치 반환

5. Queue (LinkedList를 사용하여 구현)

• 특징: 선입선출 (FIFO).
• 메서드:
  • add(E e) // 요소 추가 (예외 발생)
  • offer(E e) // 요소 추가 (성공 여부 반환)
  • remove() // 첫 번째 요소 제거 및 반환 (예외 발생)
  • poll() // 첫 번째 요소 제거 및 반환 (없으면 null 반환)
  • element() // 첫 번째 요소 반환 (예외 발생)
  • peek() // 첫 번째 요소 반환 (없으면 null 반환)
  • isEmpty() // 큐가 비어 있는지 확인
  • size() // 큐의 크기 반환

6. HashMap

• 특징: 키-값 쌍으로 저장, 해시 함수를 사용한 빠른 검색.
• 메서드:
  • put(K key, V value) // 키-값 쌍 추가
  • get(Object key) // 특정 키의 값 반환
  • remove(Object key) // 특정 키의 값 제거
  • containsKey(Object key) // 특정 키가 포함되어 있는지 확인
  • containsValue(Object value) // 특정 값이 포함되어 있는지 확인
  • size() // 맵의 크기 반환
  • clear() // 모든 요소 제거
  • keySet() // 모든 키 (Set)반환
  • values() // 모든 값 (Collection)반환
  • entrySet() // 모든 키-값 쌍 (Set)반환

 

7. TreeMap

• 특징: 키-값 쌍으로 저장, 키가 정렬된 상태로 저장.
• 메서드:
  • put(K key, V value) // 키-값 쌍 추가
  • get(Object key) // 특정 키의 값 반환
  • remove(Object key) // 특정 키의 값 제거
  • containsKey(Object key) // 특정 키가 포함되어 있는지 확인
  • containsValue(Object value) // 특정 값이 포함되어 있는지 확인
  • size() // 맵의 크기 반환
  • clear() // 모든 요소 제거
  • firstKey() // 첫 번째 키 반환
  • lastKey() // 마지막 키 반환
  • keySet() // 모든 키 반환
  • values() // 모든 값 반환
  • entrySet() // 모든 키-값 쌍 반환

8. HashSet

• 특징: 중복되지 않는 요소들의 집합, 해시 함수를 사용한 빠른 검색.
• 메서드:
  • add(E e) // 요소 추가
  • remove(Object o) // 특정 요소 제거
  • contains(Object o) // 특정 요소가 포함되어 있는지 확인
  • size() // 집합의 크기 반환
  • clear() // 모든 요소 제거
  • isEmpty() // 집합이 비어 있는지 확인

// Set -> 배열
Integer[] arr = set.toArray(new Integer[0]); // 0을 입력하면 arr의 크기를 자동으로 지정해준다

 

9. TreeSet

• 특징: 중복되지 않는 요소들의 집합, 정렬된 상태로 저장.
• 메서드:
  • add(E e) // 요소 추가
  • remove(Object o) // 특정 요소 제거
  • contains(Object o) // 특정 요소가 포함되어 있는지 확인
  • size() // 집합의 크기 반환
  • clear() // 모든 요소 제거
  • isEmpty() // 집합이 비어 있는지 확인
  • first() // 첫 번째 요소 반환
  • last() // 마지막 요소 반환
  • headSet(E toElement) // 특정 요소보다 작은 모든 요소 반환
  • tailSet(E fromElement) // 특정 요소보다 큰 모든 요소 반환