[자료구조] 개념 정리

자료구조

- 데이터를 효율적으로 저장하고 처리하기 위한 방법론

- 데이터를 어떻게 저장하고, 어떻게 접근할지에 대한 규칙을 정의.

- 자주 사용되는 자료구조 형식 : 배열, 연결 리스트, 스택, 큐, 덱, 힙, 해시테이블, 트리, 그래프, 트라이

 

1.배열 (Array)

- 같은 타입의 데이터를 연속적을 저장하는 자료구조

 

특징:

• 고정 크기: 한 번 크기가 결정되면 변경할 수 없습니다.
• 인덱스를 사용하여 빠르게 접근할 수 있습니다.

시간 복잡도:

• 인덱스를 통한 접근: O(1)
• 삽입/삭제: O(n) (특히 배열의 중간에 삽입/삭제할 경우)

2. 연결 리스트 (Linked List)

- 각 요소가 데이터와 다음 요소에 대한 참조(링크)를 가지고 있는 자료구조

종류:

• 단일 연결 리스트(Singly Linked List): 각 노드가 다음 노드를 가리킵니다.
• 이중 연결 리스트(Doubly Linked List): 각 노드가 이전 노드와 다음 노드를 모두 가리킵니다.

특징:

• 동적 크기 조정이 가능하여 메모리를 효율적으로 사용할 수 있습니다.
• 요소 간의 접근 속도가 배열보다 느립니다.

시간 복잡도:

• 삽입/삭제: O(1) (노드를 알고 있는 경우)
• 접근: O(n) (중간 노드를 찾는 데 시간이 걸림)

사용 사례

데이터를 연속적으로 빠르게 삽입 및 제거가 필요한 경우 (사진 앨범, 음악 플레이어 등)

3. 스택 (Stack)

- 후입선출 (LIFO, Last In First Out)구조로, 가장 마지막에  들어온 데이터가 가장 먼저 나옴

 

특징:

• 푸시(Push): 데이터를 스택에 추가
• 팝(Pop): 데이터를 스택에서 제거
• 피크(Peek): 스택의 가장 위에 있는 데이터를 확인

시간 복잡도:

• 푸시/팝/피크: O(1)

사용 사례

웹 브라우저의 뒤로 가기 기능, 함수의 호출 스택 등에 사용됨

4. 큐 (Queue)

- 선입선출 (FIFO, First In First Out)구조로, 가장 먼저 들어온 데이터가 가장 먼저 나옴

 

특징:

• 인큐(Enqueue): 데이터를 큐에 추가
• 디큐(Dequeue): 데이터를 큐에서 제거
• 프론트(Front): 큐의 가장 앞에 있는 데이터를 확인

시간 복잡도:

• 인큐/디큐/프론트: O(1)

 

사용 사례

프린트 작업 대기열, 프로세스 스케줄링 등에 사용됨

5. 덱 (Deque)

- 양쪽 끝에서 삽입과 삭제가 가능한 큐

 

특징:

• 양쪽 끝에서 모두 데이터를 삽입하고 삭제할 수 있습니다.

시간 복잡도:

• 양쪽 끝에서 삽입/삭제: O(1)

사용 사례

슬라이딩 윈도우 문제

6. 힙 (Heap)

- 완전 이진 트리 형태로, 부모 노드가 자식노드보다 크거나 작은 성질을 가진 자료구조

종류:

• 최대 힙(Max Heap): 부모 노드가 자식 노드보다 크거나 같은 성질을 가짐.
• 최소 힙(Min Heap): 부모 노드가 자식 노드보다 작거나 같은 성질을 가짐.

특징:

• 힙은 우선순위 큐(priority queue) 구현에 사용됩니다.

시간 복잡도:

• 삽입/삭제: O(log n)
• 힙 정렬: O(n log n)

사용 사례

힙은 최대값 및 최소값을 빠르게 찾아낼 수 있고 배열을 효율적으로 정렬하고자 하는 경우 유용하다.

7. 해시 테이블 (Hash Table)

- 데이터를 해시 함수를 통해 키 (Key)와 값 (Value) 형태로 저장하는 자료구조

 

특징:

• 키를 해시 함수로 변환하여 빠르게 접근할 수 있습니다.
• 충돌 처리 방법으로 체이닝(Chaining) 또는 개방 주소법(Open Addressing)을 사용합니다.

시간 복잡도:

• 삽입/삭제/검색: 평균적으로 O(1) (충돌이 발생하지 않는 경우)

사용 사례

해시 테이블은 주로 빠른 데이터 검색, 삽입, 삭제가 필요할 때 사용된다.

예를 들어, 사용자 이름으로 사용자 정보를 검색하거나, 데이터가 이미 존재하는지 빠르게 확인할 필요가 있을 때 유용하다.

8. 트리 (Tree)

- 계층적 구조를 가지며, 각 노드가 데이터와 자식 노드를 가지는 자료구조

 

종류:

• 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식 노드를 가짐.
• 이진 탐색 트리(Binary Search Tree, BST): 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 성질을 가짐.
• 균형 이진 트리(AVL, Red-Black Tree 등): 트리의 균형을 맞춰 성능을 최적화한 이진 탐색 트리.

시간 복잡도:

• 검색/삽입/삭제: 평균 O(log n), 최악 O(n) (불균형 트리일 경우)

사용 사례

Binary Trees(이진트리), Binary Search Tree(이진 검색 트리), Heap(힙)

9. 그래프 (Graph)

- 노드(정점)와 간선(엣지)으로 구성된 자료구조, 노드들 간의 관계를 나타냄

 

종류:

• 방향 그래프(Directed Graph): 간선이 방향을 가짐.
• 무방향 그래프(Undirected Graph): 간선에 방향이 없음.
• 가중 그래프(Weighted Graph): 간선에 가중치가 부여됨.

시간 복잡도:

• 인접 행렬(Adjacency Matrix): O(1) (간선 확인)
• 인접 리스트(Adjacency List): O(n) (간선 확인)

사용 사례

최소거리 측정, 다익스트라 등

10. 트라이

- 문자열을 저장하는 특수한 트리, 문자열의 공통 접두사를 공유하는 방식으로 데이터를 저장

 

특징:

• 문자열 검색에 매우 효율적이며, 자동 완성 시스템에 많이 사용됩니다

시간 복잡도:

• 삽입/검색: O(m), m은 문자열의 길이

사용 사례

문자열 비교

 

참고자료 :

https://developer-haru.tistory.com/70

[Data Structure] 기본적인 자료구조 8가지 정리

 

 

https://bnzn2426.tistory.com/115

자료 구조(Data Structure) 개념 및 종류 정리

https://blog.naver.com/sooftware/221516440423

c언어로 구현하는 덱(Deque) [자료구조]