Part05. 자바와 자료구조

01. 자료구조

자료구조란?

• Data Structure
• 프로그램에서 사용하는 데이터를 메모리 상에서 관리하는 여러 구현방법
• 알고리즘의 기반
• 프로그램의 수행속도에 영향을 준다.
• 프로그램 구현에 있어서 자료구조에 대한 이해도가 중요하다.

자료구조의 종류

• 선형 자료구조
  한줄로 자료를 관리한다.
  배열(Array) : 선형으로 자료를 관리한다. 정해진 크기의 메모리를 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같다.
  연결 리스트(LinkedList) : 선형으로 자료를 관리한다. 자료가 추가될 때마다 메모리를 할당받고 자료는 링크로 연결된다. 자료의 물리적 위치와 논리적 위치가 다를 수 있다.
  스택(Stack) : 가장 나중에 입력된 자료가 가장 먼저 출력되는 자료구조 (LIFO)
  큐(Queue) : 가장 먼저 입력된 자료가 가장 먼저 출력되는 자료구조 (FIFO)
  트리(Tree) : 부모 노드와 자식 노드간의 연결로 이루어진 자료구조
  힙(heap) : 우선순위 큐를 구현한다.
  이진트리(binary tree): 부모노드에 자식노드가 두개 이하이다.
  이진검색트리(binary search tree) : 자료(key)의 중복을 허용하지 않는다.
  jdk클래스 : TreeSet, TreeMap
  그래프(Graph) : 정점과 간선들의 유한 집합 G = (V,E)