자바와 자료구조

자료구조 (Data Structure) 란?

자료구조란 데이터를 효율적으로 사용할 수 있도록 메모리에 어떻게 적재하느냐 하는 데이터 구성 방법이다.

대표적인 자료구조

• 배열 (Array) : 동질성을 갖는 데이터의 연속적 나열
• 연결 리스트 (Linked List) : 노드와 포인터를 이용하여 데이터 저장
• 스택 (Stack) : Last In First Out
• 큐 (Queue) : First In First Out
• 해시 (Hash)
• 트리 (Tree)
• 힙 (Heap)
• 그래프 (Graph)

자료구조의 분류

Primitive vs Non-primitive

• Primitive : 원시 타입으로 이루어진 자료구조
  • int, char, float, double, point 등이 있다.
  • 원시 타입이므로 하나의 값만 가질 수 있다.
• Non-primitive : 원시 타입이 아닌 자료구조

Non-primitive : Linear vs Non-linear

• Linear : 선형. 즉 데이터가 순서대로 나열되어 있는 자료구조
  • Array, Linked List, Stack, Queue 등이 있다.
  • 하나의 원소는 다른 하나의 원소와 연결되어 있다. 즉 선형 구조이다.
• Non-linear : 비선형
  • Tree, Graph 등이 있다.
  • 하나의 원소가 다른 원소 몇 개와 연결될 수 있다.

Linear : Static vs Dynamic

• Static : 자료구조의 크기가 컴파일시 결정되는 자료구조
  • 실행 전이므로 최대 크기가 고정된다.
  • Array
• Dynamic : 자료구조의 크기가 런타임에 결정되는 자료구조
  • 실행 후이으로 크기는 가변이다.
  • Queue, Stack, Linked List

자료구조는 주로 어디에 사용하는가

• 검색 (Searching) : 자료구조 내에서 데이터 찾기
• 정렬 (Sorting) : 데이터를 오름차순 또는 내림차순으로 정렬하기
• 삽입 (Insertion) : 자료구조 내에 새 데이터 추가
• 수정 (Updation) : 자료구조를 수정하거나, 자료구조 내 데이터 치환
• 삭제 (Deletion) : 자료구조 내 데이터 삭제

자료구조의 장점

• 효율성 (Efficiency) : 알맞은 자료구조를 선택하면, 시간상(실행 시간) 그리고 공간상(메모리) 많은 이득을 취할 수 있다.
• 재사용성 (Reusability) : 다른 프로그램에서도 동일한 자료구조를 사용한 구현이 가능하다.
• 추상화 (Abstraction) : 클라이언트는 자료구조 내부가 어떻게 동작하는지 알 수 없지만, 자료구조의 동작방식만 알면 프로그래밍을 할 수 있다.

References

• https://roadmap.sh/java
• https://www.javatpoint.com/data-structure-tutorial
• https://www.geeksforgeeks.org/data-structures/