자료구조(Data Structure)

자료구조(Data Structure)

• 데이터를 조직하고 효율적으로 관리하고 접근하며 수정할 수 있도록 설계된 구조
  •    관리란? -> 저장, 삭제, 탐색...
• 데이터의 효율적인 저장과 처리는 프로그램의 성능과 직결되며, 적절한 자료구조의 선택은 문제 해결에 있어서 핵심적인 요소가 됨
• 목적에 맞게 사용한 좋은 자료구조는, 실행시간 단축 or/and 메모리 용량 절감 효과가 있음

 

 

자료구조의 구현

추상 자료형(Abstract Data Type; ADT)

• 데이터와 이 데이터를 다루는 연산들에 대해 명세를 제공하는 이론적인 모델
• 구체적인 구현 방법은 명시하지 않음 ( like 추상클래스, 인터페이스 )

ex) 스택이나 큐와 같은 자료구조는 ADT의 일종으로, 데이터가 어떻게 저장되고 처리되는지에 대한 규칙만을 정의하며, 실제 구현 방법은 ADT의 정의에 포함되지 않음

 

**대부분의 자료구조는 자바에서 클래스로 제공됨

 

 

자료구조의 분류

선형 자료구조 : 데이터가 순차적으로 나열되어 있는 구조로, 데이터 간의 관계가 일직선으로 연결되어 있어 서로 1:1로 대응되는 관계  

• 배열(Array): 고정된 크기의 연속적인 메모리 공간에 데이터를 저장하며, 인덱스를 통해 접근할 수 있는 자료구조
• 연결 리스트(Linked List): 각 요소가 다음 요소의 주소를 포함하는 노드로 이루어진 자료구조로, 동적으로 크기가 변할 수 있음
• 스택(Stack): LIFO(Last In, First Out) 구조로, 가장 최근에 삽입된 데이터가 먼저 삭제되는 구조
• 큐(Queue): FIFO(First In, First Out) 구조로, 가장 먼저 삽입된 데이터가 먼저 삭제되는 구조
• 데크(Deque): 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐의 일반화된 형태
• 해시테이블(Hash Table) : 키(Key)를 값(Value)에 매핑(mapping)하는 자료구조로, 데이터를 효율적으로 저장하고 검색하는 데 사용

 

 

비선형 자료구조 : 데이터가 계층적이거나 그물망처럼 연결되어 있어, 선형 자료구조와는 달리 데이터 간의 관계가 1:N 이거나 N:N 관계

• 트리(Tree): 계층 구조를 표현하는 자료구조로, 루트 노드에서부터 시작해 자식 노드들로 확장됩니다. 이진 트리, AVL 트리, 힙(Heap) 등이 포함됩니다.
• 그래프(Graph): 정점과 정점 사이를 연결하는 간선으로 구성된 자료구조로, 네트워크 구조를 표현할 때 주로 사용됩니다.
• 힙 (Heap): 이진 트리 기반의 자료구조로, 최댓값이나 최솟값을 빠르게 찾아내기 위해 사용
• 우선순위 큐:  각 요소가 우선순위를 가지며, 높은 우선순위의 요소가 먼저 처리되는 큐