자료구조(Data Structure)란?
자료구조(Data Structure)는 대량의 데이터를 효율적으로 관리하고 사용할 수 있도록 데이터 특성에 따라 구분된 데이터 구조이다.
자료구조는 특정 상황에 맞게 메모리를 효율적으로 사용하면서 데이터를 빠르고 안정적으로 처리하도록 만들어져 있다. 그렇기 때문에 상황별로 빠르고 안정적이거나, 느리고 불안정적일 수 있다. 우리는 다양한 자료구조를 알고 상황에 맞는 자료구조를 선택할 수 있어야 한다.
자료구조는 크게 선형(Linear) 구조와 비선형(NonLinear) 구조로 나뉜다.
선형(Linear) 구조
선형 구조는 자료를 구성하는 데이터들을 순차적으로 나열한 구조로, 자료들 간의 앞/뒤 관계가 1:1 관계이다.
선형구조에는 배열, 연결리스트, 스택, 큐, 덱이 있다.
1. 배열(Array)
배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다.
- 배열을 구성하는 각각의 값을 요소(element), 배열에서의 위치를 가리키는 숫자를 인덱스(index)라고 한다.
- 배열은 동일한 타입의 데이터를 저장한다. 만약 배열이 String 타입인 경우, int, double 등 다른 타입의 요소는 저장할 수 없다.
- 메모리에 데이터가 순차적으로 저장되기 때문에 각 데이터에 순서가 존재하며, indexing과 slicing이 가능하다.
- indexing : index를 사용해서 특정 요소를 읽는 것
- slicing : 배열에서 필요한 부분만 뽑아 사용하는 것
2. 연결리스트(Linked List)
연결리스트는 데이터와 포인터로 구성된 노드 간의 연결을 통해 리스트를 구현한 자료구조이다.
- 배열과 달리 연속적인 메모리 공간에 저장되어 있지 않기 때문에 노드 간의 연결이 필요하다.
- 연결리스트에서 Head는 리스트의 처음을 의미하고, 마지막 노드는 Null을 가리켜 리스트의 끝을 나타낸다.
- 연결리스트의 노드는 데이터와 다음 노드를 가리키는 Next 포인터로 구성되어 있다. 이 Next 포인터로 노드 간 연결된다.
- 연결리스트의 크기는 가변적이다.
- 연결리스트에 데이터를 삽입/삭제할 때 데이터 이동이 필요없어서 삽입/삭제가 쉽다.
- 데이터에 랜덤 액세스가 불가능해서 첫 번째 노드부터 순차적으로 접근해야 한다.
연결리스트 자료구조에는 대표적으로 단일 연결 리스트(Single Linked List)와 이중 연결리스트(Doubly Linked List), 원형 연결리스트(Circular Linked List)가 존재한다.
단일 연결리스트는 위에서 설명한 기본적인 연결리스트의 형태이다.
단일 연결리스트는 Next로 다음 노드로 이동할 수 있지만, 이전 노드로 이동은 불가능하다.
이러한 점을 해결하기 위해 이중 연결리스트는 노드가 단방향이 아닌, 양방향으로 연결할 수 있도록 이전 노드를 가리키는 Prev가 추가된다.
원형 연결리스트는 마지막 노드가 첫 번째 노드를 가리키는 형태이다. 단일 연결리스트와 달리, 마지막 노드가 Null이 아닌 첫 번째 노드의 주소를 가리킨다. 그렇기 때문에 리스트 마지막에 노드를 추가하는 것이 단일 연결리스트보다 용이하다.
3. 스택(Stack)
스택은 한 쪽 끝에서만 데이터를 넣고 뺄 수 있는 후입선출(Last-In-First-Out) 형태의 자료구조이다.
- 스택은 push, pop 등 간단한 원칙에 따라 동작하기 때문에 비교적 구현이 쉽다.
- 스택은 정해진 크기의 메모리를 사용하기 때문에 메모리 관리가 용이하다.
- 스택은 크기가 제한(정적)되어 있어서 크기를 초과할 경우 오버플로우(Overflow)가 발생한다.
- 스택 원칙으로 인해 중간 데이터에 접근하기 위해서는 맨 위의 데이터들을 순차적으로 제거해야 한다.
4. 큐(Queue)
큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(First-In-First-Out) 형태의 자료구조이다.
- 큐의 끝(Rear)에 요소를 추가하는 것을 enqueue, 큐의 맨 앞(Front)에서 요소를 제거하는 것을 dequeue 라고 한다.
- 꽉 찬 큐에 요소를 추가하려고 하면 오버플로우(Overflow), 빈 큐에 요소를 제거하려고 하면 언더플로우(Underflow)가 발생한다.
큐 자료구조에는 선형 큐(Linear Queue)와 원형 큐(Circular Queue)가 존재한다.
선형 큐는 기본적인 큐의 형태로, 배열과 연결리스트를 통해 구현할 수 있다.
선형 큐는 요소를 제거하면 맨 앞 데이터가 빠져나가고, 요소를 추가하면 끝에 요소가 생성된다. 여기서 주의할 점은 빠져나간 데이터 자리가 채워지지 않는다는 것이다. 따라서, 선형 큐에서 요소를 제거하면 비어있는 공간이 있음에도 공간이 꽉 차있다고 판단된다.
원형 큐는 1차원 배열 형태로 큐를 원형으로 구성하여 배열의 시작과 끝을 연결한다.
전체적인 개념은 선형 큐와 동일하지만, 원형으로 구성되어 있기 때문에 선형 큐와 달리 요소를 제거하면 다음 요소를 옮기지 않아도 연결이 되어 공간 낭비를 방지할 수 있다.
5. 덱(Deque, Double-Ended Queue)
덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다.
- 덱은 스택과 큐를 혼합한 자료구조이다.
- 덱은 스택이나 큐보다 입/출력이 자유롭다.
비선형(NonLinear) 구조
비선형 구조는 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 구조로, 자료들 간의 앞/뒤 관계가 1:N 혹은 N:M이다.
비선형 자료구조에는 그래프, 트리가 있다.
1. 그래프(Graph)
그래프는 노드(Node)와 간선(Edge)로 이루어진 자료구조이다.
- 그래프에서 각 요소를 노드(Node), 노드 간의 연결선을 간선(Edge)라고 한다.
- 노드는 정점(Vertex)로 표현되기도 한다.
- 그래프 간선에는 가중치(Weight)를 설정할 수 있다. 주로 거리, 비용, 우선 순위 등을 나타낼 때 사용한다.
- 그래프에서 한 노드에서 시작해서 간선을 따라가다가 자기 자신으로 돌아오는 것을 사이클(Cycle)이라고 하는데, 사이클이 없는 그래프를 비순환 그래프, 사이클이 있는 그래프를 순환 그래프라고 부른다.
- 그래프에서 한 노드에 인접한 간선의 수를 차수(Degree)라고 한다.
2. 트리(Tree)
트리는 계층적 구조를 가진 자료구조이다.
- 트리는 한 개의 루트(Root) 노드에서 시작하고, 각 노드는 자식(Child) 노드를 가질 수 있다.
- 자식이 없는 노드를 리프(Leaf) 노드라고 하며, 노드와 자손들로 구성된 트리를 서브(Sub) 트리라고 한다.
- 트리는 계층적 구조이기 때문에 사이클(Cycle)이 존재하지 않는다.
- 불균형한 형태의 트리는 탐색 성능이 저하된다.
출처
긴 글 읽어주셔서 감사합니다 🍀
잘못 작성된 내용은 피드백 주시면 반영하겠습니다 😎
'자료구조' 카테고리의 다른 글
| [자료구조] 배열(Array)이란? (0) | 2024.04.14 |
|---|
