자료구조(Data Structure)란

자료구조란?

 

일상생활에서 우리는 사물들을 정리하는 여러 가지 방법을 이용한다. 마트 계산대에서는 줄을 이루어서 기다리기도 하고, 지도에서는 도시들을 연결한느 도로가 표시되어 있다. 

사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 다양한 구조가 있다. 이것을 우리는 자료구조(data structure)이라고 한다. 

 

 

프로그램 = 자료구조 + 알고리즘

 

컴퓨터 프로그램은 뭐로 이루어져 있을까? 흔히 "프로그램 = 자료구조+알고리즘"이라고 한다. 

프로그램은 자료(data)를 처리하고, 이 자료들은 자료구조에 저장된다. 또, 알고리즘으로 주어진 문제를 처리하는 절차가 필요하다. 효율적인 자료구조가 성능이 좋은 알고리즘을 만들기 때문에 효율적이고 성능 좋은 프로그램을 만들기 위해서는 자료구조에 대해 이해하고 적절한 자료구조를 활용하는 것이 중요하다. 

 

---

자료구조의 종류

 

추상자료형 (ADT, Abstract Data Type)와 자료구조

 

우선 자료형(Data Type)은 말 그대로 데이터의 종류이다. 자료형은 int, char, float, double과 같은 기초 자료형과, 배열과 포인터를 뜻하는 파생 자료형, 구조체, 공용체, 열거형의 사용자 정의 자료형이 있다. 

추상 자료형(Abstract Data Type)은 자료구조를 설명하는 데이터의 타입을 말하며, 자료구조는 추상 데이터 타입을 실제로 구현한 결과이다. 

 

 

 

https://www.hanbit.co.kr/data/editor/20231027090450_wfludeql.png

 

 

자료구조는 크게 선형(Linear)와 비선형(Non-Linear)로 분류한다. 

선형 자료구조 (Linear Data Structure)는 데이터를 순서대로 정렬하고, 비선형 자료구조 (Nonlinear Data Structure)는 데이터를 순서 없이 비연속적으로 연결한다.

 

예를 들어, 배열이나 스택/큐를 생각해보면 순서가 정해져 있어 index를 통해 조회와 조작이 가능하기도 하는 선형 자료구조인 반면, 그래프는 각 요소가 다른 여러 요소와 연결 될 수 있는 형태인 비선형 자료구조이다. 

 

자료구조 순회(Traverse)는 자료구조의 첫 번째 요소에서 출발해 마지막 요소로 이동하는 것을 말한다. 선형 자료구조와 같은 경우는 순서가 있으므로 쉽게 순회할 수 있지만, 비선형 자료구조에서는 백트래킹(Back-tracking)을 사용해서 회귀를 하며 순회를 해야한다. 

 

이러한 특징을 이용해서 선형/비선형 자료구조를 알맞게 선택해서 알고리즘을 구현해야한다. 개별 요소에 접근하는 작업을 해야하거나, 데이터를 순회하는 작업이 많을 때 선형 자료구조가 적합하다. 반면에 네트워크 연결, 그래프를 표현할 때와 같은 특수한 경우에 선형 자료구조로 저장하면 비효율적이고 비선형 자료구조가 적합하다. 

 

---

그렇다면 JAVA에서의 자료구조는?

Java Collection Framework(JCF)

자바에서 자료구조는 Java Collection Framework(JCF)이다. 컬렉션 프레임워크는 JDK 1.2 버전부터 java.util 패키지에서 지원한다. 

 

자바 컬렉션 프레임워크는 List, Set, Map 등의 인터페이스와 이를 구현하는 클래스를 제공해서 일관된 API로 개발할 수 있다. 따라서 자료구조를 직접 구현하지 않아도 되고, 이미 구현된 컬렉션 클래스를 import java.util을 통해 가져다가 사용하면 된다. 제공되는 API 코드는 검증된, 고도로 최적화되어 있다는 장점 또한 있다. 

 

https://hudi.blog/static/1bacac1babc556100455a8c64e7658da/02d09/2.png

 

 

Java Collection Framework(JCF)의 종류

자바 컬렉션 프레임워크는 위의 그림처럼 크게 List, Queue, Set, Map 4가지로 분류된다. 대표적으로 이 4가지 인터페이스가 제공되고, 세부적으로 여러 클래스가 인터페이스를 구현하거나, 다른 인터페이스가 상속받는 구조이다.

 

이때 특이점은 Queue와 같은 경우는 인터페이스는 존재하지만 직접 구현된 클래스는 존재하지 않는다. Queue는 인터페이스는 존재하나, 직접 구현된 클래스는 존재하지 않는다. LinkedList 가 List 인터페이스와 Deque 인터페이스를 둘다 구현한다. 따라서 Queue 를 구현하려면 LinkedList 를 사용하여 구현해야한다.

Queue<Integer> queue = new LinkedList<>();

 

또, Map 인터페이스는 구조상 특징이 다르기 때문에 List , Queue , Set 과 달리 Collection 를 상속받지 않는다. 

 

---

출처

 

[C언어로 쉽게 풀었느 자료구조 - 생능 출판]

https://hudi.blog/java-collection-framework-1/

https://m.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS2832062046