DATA STRUCTURE - 1. Outline

1. 자료구조(Data Structure)란?

• 프로그램내 데이터를 메모리상에서 관리하는 여러가지 구현방법들
• 자료구조에 따라 로직(알고리즘)의 설계, 구현방식이 달라지므로 프로그램의 수행속도와 밀접한 관련이 있음
• 구현하려는 프로그램에 맞는 최적의 자료구조를 활용하기 위해서는 자료구조에 대한 이해가 필수
  *JAVA ,C++에는 자료구조를 구현할 다양한 라이브러리가 존재
  
  
  

2. 자료구조의 종류

1) 선형구조 :

• 배열(Array) :
  • 정해진 크기의 메모리를 먼저 할당받아 사용
  • 메모리에 연속적으로 연결되어, 자료의 물리적 위치와 논리적 위치가 동일
    -> 자료 검색에 용이(with Index)
    • 자료검색 : O(1)
    • 자료 추가/삭제 : O(N)
      

• 연결리스트(Linked-List) :
  • 자료가 추가될 때마다 메모리를 할당
  • 자료는 next/prev 요소를 가르키는 링크로 연결
  • 실제 메모리에는 연속적으로 연결 X 논리적으로 연속O
    -> 자료 추가와 삭제에 용이
    • 자료검색 : O(N)
    • 자료 추가/삭제 : O(1)
  
• 스택(Stack) :
  • LIFO(Last In, First Out), 나중에 들어간 놈이 먼저 나온다
  • top에 해당하는 자료가 push(추가)/pop(삭제)
    
  
• 큐(Queue) :
  • FIFO(First In, First Out), 먼저 들어간 놈이 먼저 나온다
  • rear(맨뒤)를 이용해 enqueue(추가)/ front(맨앞)를 이용해 dequeue(삭제)

*스택/큐는 배열 OR 링크드리스트로 구현하여 사용

• 데크(Deque, Double Ended QUEue) :
  • 스택과 큐의 특징을 모두 갖고 있는 복합자료형
  • 리스트의 양쪽 끝에서 노드의 삽입과 삭제가 모두 가능한 선형리스트
  • 입력이 한쪽만 가능한 입력제한 데크 : Scroll / 출력이 한쪽에서만 가능한 출력제한 데크 : Shelf

• 우선순위 큐(Priority Queue) :
  • 어떠한 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형
  • EX) 최댓값 추출하는 우선순위 큐 : [1,4,5,3,2] -> 5-4-3-2-1 순으로 데이터가 추출됨
  • Heap 자료구조와 연관이 깊음(힙 정렬을 이용해 리스트를 정렬하기 때문)

2) 비선형구조 :

• 트리(Tree) : 부모 노드와 자식 노드간의 연결로 이루어진 자료 구조
  - 트리는 특수한 형태의 그래프의 일종 (트리 ⊂ 그래프)
  즉, 그래프는 단방향, 양방향 모두 가리킬 수 있지만, 트리는 단방향만 가능 즉, 부모노드에서 자식노드만을 가리킬 뿐
  ∴ 트리는 순환구조 (cyclic)를 가지지않음 + 하나의 부모노드, 하나의 Root를 가짐 *가장 널리 사용되는 트리 자료구조 : 이진트리 - 힙(Heap), 이진탐색트리(Binary Search Tree)
  
  

• 그래프(Graph) : 정점(Vertex)과 간선(Edge)의 유한집합, G = (V,E)
  - 정점(Vertex) : 어떤 특성을 갖는 객체(Node)
  - 간선(Edge) : 정점간의 연결관계 (=링크,Link)
  *방향성(1->2)이 있는 경우/없는 경우가 존재
  
  
  • 그래프 구현방법 : 인접행렬(Adjacency Matrix), 인접리스트(Adjacency List)
  • 그래프 탐색방법 : BFS(Breadth First Search), DFS(Depth First Search)