자료구조 - 8가지 자료구조

Data Structure(자료구조)

데이터 값의 모임. 정의된 규칙에 의해 나열되어있고, 자료에 대한 처리를 효율적으로 수행하기 위해 자료를 구분하여 표현한 것.

메모리 공간의 효율성과 실행 시간의 효율성을 고려한다.

---

자료구조와 알고리즘의 관계

알고리즘은 어떤 문제를 해결하기 위한 방법이라고 할 수 있다.
자료구조가 효율적인 알고리즘을 사용할 수 있게 하기에, 자료구조와 알고리즘은 매우 밀접한 관계를 가진다.

문제풀이에 필요한 계산절차 또는 처리과정의 순서

---

필수 자료구조 8개

Array, Linked List, Stack, Queue, Hash table, Graph, Tree, Heap

1. Array(배열)

• 동일한 타입의 데이터 저장, 고정된 크기
• 인덱싱 되어있음.
  - 장점 : 데이터에 빠르게 접근할 수 있다.
  - 단점 : 삽입, 삭제 연산에서 다른 데이터들을 이동해야하기에 시간이 오래 걸린다.
  

2. Linked List(연결 리스트)

• 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조(각 데이터가 다음 데이터의 주소를 가지고 있다)
  - 장점 : 동적인 데이터 추가/삭제에 유리(다른 데이터에 영향 주지 않음)
  - 단점 : 데이터 접근 시 매번 다음 데이터를 탐색해야 하기 때문에 시간이 오래 걸린다.

  각 요소 : Node -> key, next(다음 노드를 가리키는 포인터)
  첫 번째 요소 : Head
  마지막 요소 : Tail

3. Stack(스택)

• 순서가 보존되는 선형 데이터 구조
• Last In First Out(LIFO) 마지막으로 들어온 요소가 가장 먼저 나가는 구조
  - 장점 : 삽입, 삭제 시 데이터 이동이 필요 없음
  - 단점 : 중간에 위치한 데이터에 접근하기 위해 모든 데이터를 삭제해야 한다.

4. Queue(큐)

• First In First Out(FIFO) 먼저 들어온 요소가 먼저 나가는 구조
• 삽입 (Enqueue) 삭제 (Dequeue)
  - 장점 : 삽입, 삭제 시 데이터 이동이 필요 없음
  - 단점 : 중간에 위치한 데이터에 접근하기 위해서 모든 데이터를 삭제해야 한다.
  스택과 비슷하게 삽입,삭제

5. Hash table(해시 테이블)

• 해시함수를 사용하여 변환한 값을 색인(index)삼아 key,value를 저장하는 자료구조
  - 장점 : 데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적
  - 단점 : 충돌이 발생하는 경우 성능 저하

  충돌이 자주 일어날 수 있으며, 이를 위해 다양한 방법으로 해시 함수를 개선하거나 해시 테이블의 구조개선 등의 방법이 사용된다.

6. Graph(그래프)

• nodes/verticles(노드) 사이에 edge(엣지)가 있는 collection
• directed : 방향그래프는 일방통행
• undirected : 무방향 그래프는 양방향 통행
  - 장점 : 복잡한 상호관계 표현 가능
  - 단점 : 너무 복잡한 경우 연산 속도가 느리다.
  

7. Tree(트리)

• 그래프가 계층적 구조를 가진 형태
• 최상위 노드(루트)를 가진다
• 상위 노드를 부모(parent)노드, 하위 노드를 자식(child)노드라 한다.
  - 장점 : 데이터를 효율적으로 검색할 수 있다.
  - 단점 : 삽입, 삭제 시 많은 수의 노드를 이동해야하기에 시간이 오래 걸린다.

8. Heap(힙)

• Binary Tree(이진 트리)
• 최소 힙 : 부모의 키 값이 자식의 키 값보다 작거나 같다.(루트 노드의 키 값이 트리의 최솟값)
• 최대 힙 : 부모의 키 값이 자식의 키 값보다 크거나 같다.(루트 노드의 키 값이 트리의 최댓값)
  - 장점 : 최소 혹은 최댓값을 빠르게 찾을 수 있음
  - 단점 : 특정 값을 검색하는 것은 느리다.