반응형
자료 구조의 분류
자료 구조는 크게 선형 구조와 비선형 구조로 나눌 수 있습니다.
- 선형 구조(Linear Structure): 데이터가 일렬로 나열되는 구조입니다.
- 배열(Array)
- 스택(Stack)
- 큐(Queue)
- 데크(Deque)
- 선형 리스트(Linear List): 순차 리스트와 연결 리스트로 구분
- 비선형 구조(Non-Linear Structure): 데이터가 계층적 또는 연결된 형태로 나열됩니다.
- 트리(Tree)
- 그래프(Graph)
배열 (Array)
배열은 정적인 자료 구조로 메모리 내에서 연속된 공간을 차지하며 반복적인 데이터 처리에 적합한 구조입니다.
- 장점: 같은 데이터형을 가진 데이터를 한 이름으로 관리해 코드의 가독성과 처리 효율성을 높입니다.
- 단점: 메모리가 연속적으로 할당되어야 하므로 메모리 낭비 가능성이 있으며, 데이터 추가가 어렵습니다.
스택 (Stack)
스택은 한쪽 끝에서만 데이터의 삽입과 삭제가 이루어지는 자료 구조로, 후입선출(Last In First Out, LIFO) 방식을 따릅니다.
- 예시: 함수 호출 구조, 되돌리기 기능
- 특징: 마지막에 삽입된 데이터가 가장 먼저 삭제됩니다.
큐 (Queue)
큐는 한쪽 끝에서 삽입하고 다른 한쪽 끝에서 삭제하는 자료 구조로, 선입선출(First In First Out, FIFO) 방식을 따릅니다.
- 예시: 운영체제의 작업 스케줄링
- 특징: 데이터는 들어온 순서대로 처리됩니다. 삽입과 삭제를 나타내기 위해 두 개의 포인터(Front와 Rear)가 사용됩니다.
데크 (Deque)
데크(Deque)는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조입니다. 스택과 큐의 기능을 모두 포함하고 있어 유연한 데이터 처리에 유용합니다.
선형 리스트 (Linear List)
선형 리스트는 배열처럼 연속된 저장 공간을 사용하는 **연속 리스트(Contiguous List)**와, 포인터를 사용해 노드를 연결하는 **연결 리스트(Linked List)**로 구분됩니다.
- 연속 리스트: 메모리 공간이 연속적이어서 접근이 빠르지만, 데이터의 삽입/삭제 시 효율성이 떨어질 수 있습니다.
- 연결 리스트: 노드 간 포인터로 연결되어 삽입/삭제가 용이하나, 연속적이지 않으므로 접근 속도가 다소 느리고 추가 메모리가 필요합니다.
트리 (Tree)
트리는 노드(Node)와 가지(Branch)로 구성된 계층적 자료 구조로, 사이클이 없는 그래프의 한 형태입니다.
- 근 노드(Root Node): 트리의 최상위 노드
- 단말 노드(Terminal Node): 자식 노드가 없는 노드로, **차수(Degree)**가 0입니다.
- 자식/부모 노드: 특정 노드와 연결된 상하 관계에 있는 노드들
- 형제 노드(Sibling Node): 동일한 부모를 가진 노드들
- 트리의 차수: 노드들의 차수 중 가장 큰 값
트리는 주로 파일 시스템, 데이터베이스 인덱싱 등 계층적 구조가 필요한 상황에서 유용하게 사용됩니다.
그래프 (Graph)
그래프는 **정점(Vertex)**과 **간선(Edge)**으로 구성된 자료 구조로, 정점 간의 연결 관계를 나타냅니다.
- 방향 그래프: 정점 간 간선에 방향이 존재하며, 특정 방향으로만 이동 가능합니다.
- 최대 간선 수: n개의 정점에서 최대 간선 수는 n(n-1)입니다.
- 무방향 그래프: 정점 간 간선에 방향이 없어 양방향 이동이 가능합니다.
- 최대 간선 수: n개의 정점에서 최대 간선 수는 n(n-1)/2입니다.
그래프는 네트워크, 소셜 미디어 등 다양한 분야에서 활용됩니다.
반응형
