자료구조와 알고리즘

• 자료구조는 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조
• 알고리즘이란 자료구조에 쌓인 데이터를 활용해 문제를 해결하기 위한 여러 동작들의 모임

선형 구조 - 배열, 스택, 큐, 리스트

Array

• 배열의 크기는 최초에 결정되고 변경 불가능
• 순차적으로 저장되어 인덱스가 있기 때문에 데이터의 삽입, 삭제에 취약
• 데이터에 대한 접근 속도가 매우 빠름

Linked List

• 크기가 가변적
• 인덱스가 없고, 현재 위치에 대한 이전, 다음 위치에 대한 정보가 있음
• 데이터의 삽입, 삭제는 용이하지만 데이터 접근 자체는 느림

→ 데이터를 자주 조회시 Array, 데이터 잦은 삽입, 삭제시 Linked List
→ 특정 요소에 접근할 때, 배열의 인덱스를 알 경우 O(1)의 시간 복잡도를 갖지만, 인덱스를 모른다면 O(N)의 시간 복잡도 (Random Access)
→ 링크드리스트는 항상 순차적으로 접근을 해야한다 그래서 O(N) (Sequential Access)

Stack

• 데이터의 삽입과 삭제가 데이터의 한쪽 끝에서만 일어나는 자료구조
• 가장 마지막에 삽입된 데이터가 가장 먼저 사용되거나 삭제 됨(후입선출, LIFO, Last in First Out)
• 데이터를 넣고 빼는 걸 자주하는 자료 구조

Queue

• 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조.
• 순서대로 처리되어야 하는 일에 필요, First In First Out(FIFO)

스택과 큐의 구현

• Stack : Array로 구현하면 삭제할 필요없이 index를 줄이고 초기화만 하면 됨
  → List로 구현하면 객체를 제거하는 작업이 필요
• Queue : List로 구현시 객체 1개만 제거하면 되므로 LinkedList로 구현
  → Array로 구현하면 poll 연산 이후 객체를 당기는 작업 필요

비선형 구조 - 그래프, 트리

Graph

• 연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조
• 연결 관계에 초점이 맞춰져 있음

- 노드(Node): 연결 관계를 가진 각 데이터. 정점(Vertex)이라고도 함
- 간선(Edge): 노드 간의 관계를 표시한 선.
- 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)

Tree

• 정점과 간선을 이용한 Graph의 특수형태, 계층형 비선형 자료 구조(계층적 혹은 망 구조)
• 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있음
  (트리는 계층이 있는 데이터를 표현하는 데에 적합)
• 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등
  
  

Heap

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
• 각 노드의 키값이 자식의 키값보다 작지않거나(최대힙), 그 자식의 키값보다 크지 않은(최소힙) 완전 이진 트리

---

Reference

https://mangkyu.tistory.com/89