[자료구조] 자료구조 정리

1. 배열(Array)

- 동일한 타입의 데이터 저장

- 실제 저장된 메모리 주소도 연속적, 인덱스로 데이터 접근 가능

- 일반적인 선언은 정적 배열(크기 고정), STL의 Vector는 동적 배열(가변 크기)

 

2. 연결 리스트(Linked List)

- 노드의 연결로 이루어져 있음, 노드는 값과 다음 노드를 가리키는 포인터로 구성

- 연결 리스트 가장 앞 요소는 Head, 마지막 요소는 Tail

- 인덱스로 접근이 불가능, 순차적 접근

- 하지만 삭제 및 삽입이 용이

 

3. 스택(Stack)

- 후입선출(Last In First Out, LIFO) 구조 : 가장 마지막에 추가한 데이터를 가장 먼저 꺼냄

 

4. 큐(Queue)

- 선입선출(First In First Out, FIFO) 구조 : 가장 먼저 추가한 데이터를 가장 먼저 꺼냄

 

5. 해시 테이블(Hash Table)

- 해시 함수를 통해 얻은 값을 인덱스로 삼아 Key-Value로 저장

- 삽입 및 검색이 용이

- 해시값이 같아 충돌이 일어날 수 있음

 

6. 그래프(Graph)

- 노드(Node/Vertex)와 엣지(Edge)로 구성

- 엣지에 방향이 있으면 방향 그래프, 방향이 없는 그래프의 엣지는 양방향

 

7. 트리(Tree)

- 상위 노드는 부모(Parent) 노드, 하위 노드는 자식(Child) 노드

- 최상위 노드는 루트(Root) 노드

- 이진 트리 중 힙(Heap)이라는 자료구조는 최대 힙(부모 >= 자식, 루트가 최대 값), 최소 힙(부모 <= 자식, 루트가 최소값)으로 나뉨