[자료구조] 자료구조 개념, 종류 알아보기

자료구조 종류에 대해 전체적으로 알아보는 포스팅을 하려고 합니다.

 

 

[목차]

1. 배열
2. 연결 리스트
3. 스택
4. 큐
5. 해시 테이블
6. 트리
7. 그래프
8. 힙

---

자료구조란 데이터를 효율적으로 저장하고 관리하는 방법을 의미합니다.

흔히 말하는 배열이 자료구조입니다.

 

갑자기 자료구조를 공부하는 이유는 이직에 대한 생각도 있지만, 개발자라면 제대로 알아야한다는 생각이 들었습니다.

개발자는 공부해야할 것이 산더미지만 그중에서도 기본은 알고 있어야 하는 것이 몇 개 있는데 그게 자료구조라는 생각이 들었습니다.

 

그래더 자료구조를 간단하게 전체적으로 한 번 정리해보려고 합니다.

자료구조별로 상세한 정리도 할 예정인데 그것은 이후에 포스팅해보겠습니다.

 

1. 배열

 

배열(Array)은 동일한 데이터 타입 요소들이 연속된 메모리 공간에 저장되는 자료구조입니다.

예를들어 데이터가 String타입이면 String만 저장할 수 있습니다.

 

각 데이터 요소는 인덱스를 갖고 있어서 인덱스를 통해 빠르게 접근이 가능합니다.

 

다만, 연속된 메모리 공간에 데이터를 저장하기 때문에 중간에 데이터 삽입, 삭제시 데이터들을 이동시켜야 하기 때문에 비용이 많이 드는 자료구조입니다.

 

2. 연결 리스트

 

연결 리스트(Linked List)는 각 요소가 노드 형태인데 이 노드는 '데이터+다음 노드를 가리키는 포인터'로 구성됩니다. 배열과 달리 연속된 메모리 공간이 필요하진 않고 크기가 동적으로 변할 수 있습니다.

 

그렇기 때문에 연결리스트는 삽입과 삭제에 유리한 자료구조입니다. 삽입, 삭제시 데이터를 이동시키지 않고 포인터를 적절히 조절하여 데이터를 변경합니다.

 

3. 스택

 

스택(Stack)은 LIFO(Last In, First Out) 구조로, 마지막에 추가된 데이터가 가장 먼저 제거됩니다. 보통 재귀 알고리즘이나 함수 호출 관리에 사용됩니다.

 

자바 책을 보면 쓰레드 실행 구조를 스택 이미지로 설명하는 경우를 많이 봤는데요. 쓰레드는 호출 스택(Call Stack)을 사용하여 메서드 호출을 관리합니다. 메서드가 호출될 때마다 스택에 쌓이고 종료되면 삭제됩니다.

 

4. 큐

 

큐(Queue)는 FIFO(First In, First Out) 구조로, 먼저 들어간 데이터가 먼저 나옵니다. 

 

보통 버스 정류장이나 은행의 대기열로 예를 많이 듭니다. 프린터 작업 역시 큐 자료구조로 먼저 들어온 작업이 먼저 인쇄됩니다.

 

5. 해시 테이블

 

해시 테이블은 키를 해시 함수로 변환하여 그 값에 해당하는 위치에 데이터를 저장하는 구조입니다.

그리고 리소스를 많이 먹는다는 단점이 있으나 데이터의 검색, 삽입, 삭제가 빠릅니다.

 

근데 만약 똑같은 결과가 나오면 어떻게 될까요? 이때는 충돌이 일어나기 때문에 이를 방지하기 위한 방법이 있습니다.

하나는 체이닝으로 빈 버켓에 리스트형 자료구조를 넣어 버켓에 이미 값이 있다면 뒤로 이어가는 방법입니다.

또 하나는 선형탐사입니다. 만약 충돌이 발생하면 거기에 넣지 않고 다른 빈 자리에 넣습니다.

이때 버킷자리가 꽉찬다면 테이블리사이징으로 늘립니다. 

 

6. 트리

 

트리((Tree)는 계층 구조로 '노드'와 '간선'으로 이루어집니다.

루트 노드에서 시작해 자식 노드로 이어지고 이진 트리나 이진 탐색 트리가 대표적입니다.

 

파일 시스템에서 많이 사용하는 자료구조이고 8번에서 설명할 힙 자료구조도 트리가 기반입니다.

 

7. 그래프

 

그래프(Graph)는 노드와  노드간 연결로 구성된 자료구조입니다.

크게 방향 그래프, 무방향 그래프, 가중치 그래프 등이 존재합니다.

 

탐색 알고리즘으로 유명한 DFS, BFS에서 주로 사용되는 자료구조입니다.

 

8. 힙

힙(Heap)은 완전 이진 트리 기반의 자료구조로, 최대 힙은 부모 노드가 자식보다 크고, 최소 힙은 부모 노드가 자식보다 작습니다.

주로 우선순위 큐를 구현하는 데 사용되며, 삽입과 삭제는 O(log n)의 시간 복잡도를 가집니다.

예로는 작업 스케줄링, 다익스트라 알고리즘, 네트워크 패킷 처리 등이 있습니다.

---

자료구조의 종류와 개념, 특징에 대해 간단히 살펴봤습니다.

이제 하나씩 차근차근 디테일한 포스팅을 해볼 예정입니다.

 

감사합니다!