자료구조란?

자료구조 정리

• 1. 자료구조란 무엇인가?
• 2. 자료구조의 분류
• 3. 배열 (Array)
• 4. 연결 리스트 (Linked List)
• 5. 스택 (Stack)
• 6. 큐 (Queue)
• 7. 트리 (Tree)
• 8. 그래프 (Graph)
• 9. 해시 테이블 (Hash Table)

1. 자료구조란 무엇인가?

자료구조는 컴퓨터에서 데이터를 저장, 관리, 그리고 사용하는 구조를 의미합니다. 이를 통해 데이터의 접근과 수정이 보다 효율적으로 이루어질 수 있습니다. 예를 들어, 어떤 자료구조는 검색에 효율적이고, 다른 자료구조는 삽입과 삭제가 빠릅니다. 적절한 자료구조를 선택하면 프로그램의 성능이 크게 향상될 수 있습니다.

2. 자료구조의 분류

2.1 선형 자료구조

선형 자료구조는 데이터가 직선 형태로 연결된 구조입니다. 각 요소가 순차적으로 배치되어 있으며, 데이터들이 일직선 상에 있습니다.

예: 배열, 연결 리스트, 스택, 큐

2.2 비선형 자료구조

비선형 자료구조는 데이터가 계층적 또는 그물 형태로 연결된 구조입니다. 데이터들이 다양한 경로로 연결될 수 있습니다.

예: 트리, 그래프

3. 배열 (Array)

배열은 동일한 타입의 데이터를 순차적으로 저장하는 자료구조입니다. 고정된 크기의 메모리 블록에 연속적으로 저장되기 때문에 인덱스를 이용해 빠르게 접근할 수 있습니다.

+----+----+----+----+----+
| 90 | 85 | 78 | 92 | 88 |
+----+----+----+----+----+
 인덱스:  0    1    2    3    4
            

4. 연결 리스트 (Linked List)

연결 리스트는 노드라는 개체들이 포인터를 통해 연결된 형태로 이루어진 자료구조입니다. 배열과 달리 크기가 동적으로 변할 수 있어, 데이터의 삽입과 삭제가 용이합니다.

[A] -> [B] -> [C] -> [D] -> NULL
            

5. 스택 (Stack)

스택은 후입선출(LIFO; Last In First Out) 구조로, 가장 최근에 삽입된 데이터가 가장 먼저 제거됩니다. 주로 재귀 호출의 추적이나 데이터의 역순 처리에 사용됩니다.

| 40 | <- Top (가장 최근에 추가된 값)
| 30 |
| 20 |
| 10 |
            

6. 큐 (Queue)

큐는 선입선출(FIFO; First In First Out) 구조로, 먼저 들어온 데이터가 먼저 나갑니다. 대기열이나 자원 관리에 주로 사용됩니다.

[Front]  10  ->  20  ->  30  ->  40  [Rear]
            

7. 트리 (Tree)

트리는 계층 구조를 나타내는 자료구조로, 노드로 구성되며 부모-자식 관계를 가집니다. 이진 트리가 가장 일반적인 형태입니다.

       (A)
      /   \
    (B)   (C)
    / \     \
  (D) (E)  (F)
            

8. 그래프 (Graph)

그래프는 노드(정점)와 노드 간의 연결(간선)로 이루어진 자료구조입니다. 네트워크 구조나 복잡한 관계를 표현하는 데 적합합니다.

(A) -- (B)
 | \    |
(C) -- (D)
            

9. 해시 테이블 (Hash Table)

해시 테이블은 키-값 쌍으로 데이터를 저장하며, 해시 함수를 이용해 데이터를 빠르게 검색할 수 있는 자료구조입니다. 해시 테이블은 평균적으로 매우 빠른 검색, 삽입, 삭제 성능을 제공합니다.

예를 들어, 전화번호부를 해시 테이블로 구현할 수 있습니다. 이름을 키로, 전화번호를 값으로 저장합니다. 해시 함수는 각 키를 특정한 슬롯으로 매핑합니다.

충돌 해결 기법으로는 체이닝(Chaining)과 오픈 어드레싱(Open Addressing) 등이 있습니다. 체이닝은 각 슬롯에 연결 리스트를 사용하여 여러 데이터를 저장하는 방식이며, 오픈 어드레싱은 비어 있는 슬롯을 찾아 데이터를 저장하는 방식입니다.

+------------+
| 0 |  --> [Alice, 12345]
+------------+
| 1 |  --> [Bob, 67890]
+------------+
| 2 |  --> [Charlie, 54321]
+------------+