[CS] 자료 구조 (Data Structure)

* 정의

데이터를 효율적으로 저장, 관리, 처리 하기 위한 조직화된 방법을 의미

* 종류

1. 선형 자료구조 (Linear Data Structure)

데이터가 일렬로 나열된 구조로, 하나의 요소가 그 앞뒤 요소와 직접적인 관계를 가짐, 각 데이터 요소가 선형적인 순서를 가지는 구조

(1) 배열(Array)

동일한 데이터 타입의 요소들이 연속된 메모리 공간에 저장된 자료구조. 배열의 크기가 고정되어있으며, 각 요소는 인덱스를 통해 접근할 수 있다.

장점

• 빠른 접근 : 인덱스를 통해 임의의 요소에 O(1) 시간 복잡도로 접근할 수 있다.
• 간단한 구현 : 배열을 구조가 단순하고 기본적인 자료구조로, 사용이 쉽다.
• 캐시 지역성 (Cache Locality) : 메모리 상에서 연속된 공간에 저장되므로 캐시 효율성이 높다.

단점

• 고정된 크기 : 배열은 선언할 때 크기가 고정되므로, 크기를 미리 알기 어렵거나 유동적인 경우에 비효율적
• 삽입과 삭제를 비효율성 : 배열의 중간에 삽입하거나 삭제할 때, 해당 위치 이후의 요소들을 모두 이동해야 하므로 O(n) 의 시간이 소요된다.
• 메모리 낭비 : 필요한 크기를 정확히 예측하지 못하면 공간이 낭비될 수 있다.

(2) ArrayList

동적 배열을 구현한 자바의 표준 클래스중 하나로, 배열과 유사하지만 크기가 동적으로 조정되는 특징을 가지지고 있다. 크기를 미리 정의할 필요가 없고, 필요에 따라 크기가 자동을 조정된다.

장점

• 동적 크기 조정 : 배열은 고정 크기지만, ArrayList 는 요소가 추가됨에 따라 자동으로 크기가 늘어 나고 크기를 미리 정의할 필요가 없어 메모리 사용이 더 효율적이다.
• 빠른 임의 접근 : 인덱스를 이용한 요소 접근이 가능하며, 시간 복잡도는 O(1) 이다. 즉, 배열과 마찬가지로 요소에 빠르게 접근할 수 있다.
• 내장된 메서드 제공 : add(), remove(),contains() 등 다양한 메서드를 제공하여 데이터 추가, 삭제, 검색을 쉽게 수행할 수 있다.
• 다양한 유틸리티 : 크기, 조정, 복사, 정렬 등 유용한 메서드가 많이 내장되어 있어 개발 생산성이 높다.
• 유연성 : 객체를 저장할 수 있는 제너릭 클래스로, 다양한 데이터 타입을 저장할 수 있다.

단점

• 느린 중간 삽입 및 삭제 : 중간에 요소를 삽입하거나 삭제할 때는 해당 위치 이후의 모든 요소를 이동시켜야 하기 때문에 최악의 경우 O(n)의 시간이 소요된다. 특히 배열의 앞쪽이나 중간에서 삽입/삭제르 많이
• 메모리 낭비
• 비동기 안전성 부족
• 비교적 느린 탐색

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

각 데이터 요소(노드)가 포인터를 통해 다음 노드를 가리키는 방식으로 연결된 자료구조이다. 노드들은 반드시 연속된 메모리 위치에 있을 필요가 없으며, 필요할 때마다 동적으로 메모리를 할당 받는다.

장점

• 동적 크기 조정 : 배열과 달리 크기가 고정되지 않으며, 필요할 때마다 동적으로 노드를 추가하거나 제거할 수 있다.
• 삽입과 삭제의 효율성 : 특정 위치에서의 삽입과 삭제가 O(1) 시간 복잡도로 가능(단, 해당 위치를 찾는 과정은 O(n)) 하므로, 중간 삽입 및 삭제에 유리하다

단점

• 느린 접근 속도 : 임의의 위치에 접근하려면 순차적으로 노드를 탐색해야 하므로 O(n)의 시간이 걸린다.
• 추가적인 메모리 사용 : 각 노드가 데이터뿐만 아니라 다음 노드를 가리키는 포인터를 저장해야 하므로, 배열보다 메모리 사용량이 많다.
• 캐시 비효율성 : 노드들이 연속된 메모리 공간에 저장되지 않으므로, 캐시 효율이 떨어진다.

(4) 스택(Stack)

후입선출(LIFO, Last In First Out) 방식의 자료구조로, 마지막에 삽입된 데이터가 먼저 삭제 된다. 주로 재귀적인 문제 나 역순 처리, 실행 기록 저장 에 사용 된다.

장점

• 간단한 구현 : 데이터 삽입과 삭제가 한쪽 끝에만 일어나므로 구현이 간단하다.
• 빠른 작업 처리 : 삽입과 삭제가 O(1) 시간 복잡도로 이루어지기 때문에 매우 효율적이다.
• 재귀 문제 해결 : 재귀적인 함수 호출을 관리하거나 역순 처리가 필요한 작업에 적합하다.

단점

• 제한적인 접근 : 마지막으로 삽입된 요소만 접근할 수 있으므로, 임의의 요소에 접근할 수 없다.
• 메모리 오버플로우 위험 : 재귀 함수 호출이 너무 많아지면 스택 오버플로우(Stack Overflow) 가 발생할 수 있다.

(5) 큐(Queue)

: 선입선출(FIFO, First In First Out) 방식의 주료 구조로, 먼저 삽입된 데이터가 먼저 삭제 된다. 주로 대기열 처리나 너비 우선 탐색 등에 사용된다.

장점

• 빠른 작업 처리 : 큐의 삽입(Enqueue)과 삭제(Dequeue)는 각각 O(1) 시간 복잡도로 효율적이다.
• 대기열 처리에 적합 : 선입선출 구조이므로, 먼저 들어온 데이터부터 처리해야 하는 상황 ( 예: 프린터 대기열, 프로세스 스케줄링) 에 적합

단점

• 제한적인 접근 : 스택과 마찬가지로, 임의의 요소에 접근할 수 없으며, 고정 크기 큐의 경우 메모리 낭비가 발생할 수 있다.
• 메모리 관리 문제 : 큐가 꽉 차면 데이터의 삽입이 불가능할 수 있으며, 고정 크기 큐의 경우 메모리 낭비가 발생할 수 있다.

메서드

• add(E e) : 큐의 끝에 요소를 추가. 성공하면 true, 큐의 용량이 제한되어 있고 용량이 가득찬 경우 예외(IllegalStateException)
• offer(E e) : 큐의 끝에 요소를 추가. 용량이 제한되어 있는 경우도 예외없이 false를 반환
• remove() : 큐의 첫 번째 요소를 제거하고 반환. 큐가 비어 있으면 예외(NoSuchElementException)
• poll() : 큐의 첫 번째 요소를 제거하고 반환. 큐가 비어있으면 null 반환
• element() : 큐의 첫 번째 요소를 반환. 큐가 비어 있으면 예외(NoSuchElementException)
• peek() : 큐의 첫 번째 요소를 반환. 큐가 비어 있으면 null 반환

(6) 덱 (Deque, Double-Ended Queue)

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조. 큐와 달리 양쪽에서 데이터를 처리할 수 있는 유연성을 제공

장점

• 양방향 처리 가능 : 양쪽 끝에서 삽입과 삭제가 모두 가능하여, 상황에 따라 데이터를 앞뒤로 처리 할 수 있다.
• 빠른 삽입/삭제 : 큐처럼 양쪽 끝에서의 삽입과 삭제가 O(1) 시간 복잡도로 효율적이다.

단점

• 제한적인 접근 : 중간 요소에 접근할 수 없으며, 양 끝에만 데이터를 삽입하고 삭제할 수 있다.
• 메모리 낭비 가능성 : 덱의 고정 크기를 미리 설정할 경우 필요 이상의 메모리를 낭비할 수 있다.

(7) 원형 큐 (Circular Queue)

고정된 크기의 큐에서 처음과 끝이 연결된 구조로, 배열처럼 선형적인 큐의 단점을 보완한 자료구조. 끝에 도달하면 다시 처음으로 돌아간다.

장점

• 효율적인 공간 활용 : 끝에 도달하면 다시 처음으로 돌아가기 때문에 메모리 공간을 효율적으로 사용할 수 있다.
• 빠른 삽입/삭제 : 큐의 삽입과 삭제가 O(1) 시간 복잡도로 이루어진다.

단점

• 고정된 크기 :크기가 고정되어 있어, 크기를 초과하는 데이터를 처리할 수 없을 때 문제가 될 수 있다.
• 복잡한 구현 : 일반적인 큐보다 구현이 조금 더 복잡할 수 있다.

2. 비선형 구조

데이터들이 계층적이거나 복잡한 방식으로 연결되어 있으며, 일반적으로 트리와 그래프의 형태를 띈다. 각 데이터가 하나 이상의 다른 데이터와 연결될 수 있어, 데이터를 더 복잡하게 표현하고 처리할 수 있다.

(1) 트리(Tree)

계층적인 구조를 가지며, 루트 노드에서 시작해 자식 노드들로 연결되는 비선현 자료구조. 트리의 각 노드는 부모와 자식의 관계를 가질 수 있으며, 이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree), AVL 트리, 힙(Heap) 등이 포함된다.

-> 이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리.
-> 이진 탐색 트리(Binary Search Tree, BST) : 왼쪽 서브트리의 모든 노드가 루트보다 작고, 오른쪽 서브트리의 모든 루트보다 큰 이진 트리
-> 힙(Heap) : 이진 트리 기반의 트리 구조로, 최대값 또는 최소값을 빠르게 찾기 위해 사용. (최대 힙, 최소 힙)
-> AVL 트리 : 자동으로 균형을 맞추는 이진 탐색

장점

• 빠른 검색, 삽입, 삭제 : 이진 탐색 트리의 경우 평균적으로 O(log n)의 시간 복잡도를 가지고 있다.
• 계층적 데이터 표현 : 계측적 데이터 구조( 예 : 파일시스템, 조직도 ) 를 표현하기에 적합

단점

• 불균형 문제 : 이진 탐색 트리는 트리의 높이가 커질수록 비효율적일 수 있다. 최악의 경우 O(n) 시간이 걸린다. (이를 해결하기 위해 AVL 트리나 레드-블랙 트리 등 균형 잡힌 트리를 사용)
• 복잡한 구현 : 균현 잡힌 트리( ex) AVL 트리 ) 는 삽입, 삭제 시 트리의 균형을 유지하기 위한 추가 연산이 필요해 구현이 복잡하다.

(2) 그래프(Graph)

노드(정점)와 노드 사이의 간선(엣지)으로 구성된 비선형 자료구조. 그래프는 방향성이 있을 수도 있고 없을 수도 있다. 주로 네트워크 연결이나 관계를 표현할 때 사용

-> 무방향 그래프(Undirected Graph) : 간선이 양방향으로 연결된 그래프. 두 노드 간의 관계가 쌍방향일 때 사용
-> 방향 그래프(Directed Graph) : 간선이 한 방향으로만 연결된 그래프. 간선이 방향성을 가지며, 일방적인 관계를 표현할 때 사용
-> 가중 그래프(Weighted Graph) : 간선마다 가중치(비용 또는 거리)를 부여한 그래프
-> 비가중 그래프(UnWeighted Graph) : 간선에 가중치가 없는 그래프

장점

• 유연한 데이터 표현 : 그래프는 네트워크, 소셜 미디어 연결, 도로망 등 복잡한 관계를 표현하는 데 적합
• 강력한 탐색 알고리즘 : 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 과 같은 알고리즘을 사용해 경로 탐색, 최단 경로 문제 등을 해결할 수 있다.
• 다양한 문제 해결 : 최단 경로 문제(다익스트라 알고리즘), 최소 신장 트리(크루스칼, 프림 알고리즘) 등 다양한 알고리즘을 적용

단점

• 메모리 사용량 : 그래프는 노드와 간선 모두를 저장해야 하므로, 큰 네트워크나 복잡한 구조에서는 많은 메모리가 필요
• 복잡한 구현 : 그래프를 표현하고 탐색하는 알고리즘이 비교적 복잡하다. 특히 가중 그래프나 방향 그래프는 추가적인 처리 로직이 필요
• 연산 비용 : 그래프의 크기가 커질수록 탐색 및 최적화에 필요한 시간이 급격히 증가 할 수 있다.

(3) 트리 vs 그래프 비교

특성	트리(Tree)	그래프(Graph)
노드 연결	계층적 구조 (부모-자식 관계)	복잡한 관계 표현 가능 (노드 간 다중 연결)
루트 노드	루트 노드가 반드시 존재	루트 노드가 존재하지 않음
사이클	사이클이 발생하지 않음 (비순환 구조)	사이클이 발생할 수 있음
경로	루트에서 자식으로 내려가는 단일 경로 존재	노드 간 여러 경로가 존재할 수 있음
알고리즘	트리 순회 (전위, 중위, 후위)	그래프 탐색 (BFS, DFS), 최단 경로 등 다양한 알고리즘