1. 선형 자료구조
선형 자료구조란 요소가 일렬로 나열되어 있는 자료구조를 의미한다.
1-1. 연결 리스트
연결리스트란 ? 데이터를 감싼 노드를 포인터(Pointer)로 연결해서 공간 효율성을 극대화시킨 자료구조
삽입과 삭제가 O(1)이 걸리며, 탐색에는 O(n)이 걸린다.
- 싱글 연결 리스트
- 이중 연결 리스트
- 원형 이중 연결 리스트
1-2. 배열
배열이란 ? 여러 개의 데이터를 연속적인 공간에 저장한 자료구조
삽입과 삭제에는 O(n)이 걸리지만, 탐색에는 O(1)이 걸린다.
👉🏻 따라서 데이터 추가와 삭제가 많은 경우에는 '연결 리스트'를, 탐색을 많이 하는 경우에는 '배열'을 사용하는 것이 좋다.
1-3. 스택
스택이란 ? 마지막에 들어간 데이터가 가장 먼저 나오는 후입선출(LIFO) 구조을 가진 자료구조
재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록등에 사용된다.
삽입 및 삭제에는 O(1)이 걸리며, 탐색에는 O(n)이 걸린다.
1-4. 큐
큐란 ? 먼저 들어간 데이터가 가장 먼저 나오는 선입선출(FIFO) 구조를 가진 자료구조
삽입 및 삭제에는 O(1)이 걸리며, 탐색에는 O(n)이 걸린다.
2. 비선형 자료구조
비선형 자료구조란 일렬로 나열 되어있지 않고, 자료의 순서나 관계가 복잡한 자료구조를 의미한다.
2-1. 그래프(Graph)
그래프란 ? 정점과 간선의 집합으로 이루어진 자료구조
가중치 : 간선과 정점 사이에 드는 비용(Cost)
2-2. 트리(Tree)
트리란 ? 그래프의 한 종류로 계층적인 데이터를 표현하는데 사용되는 자료구조
루트 노드, 내부 노드, 리프 노드 등으로 구성되어 있다.
트리의 특징
- 부모와 자식이라는 계층 구조를 가진다. ⭐️
- 간선의 개수는 노드의 개수 -1 이다.(E = V - 1)
- 임의의 두 노드 사이의 경로는 유일무이하게 존재한다.
이진트리
이진트리란 ? 자식 노드의 수가 2개 이하인 트리
이진 탐색 트리
이진 탐색 트리(BST)는 노드의 오른쪽 서브 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 서브 트리에는 '노드 값보다 작은 값'이만 포함된 트리이다.
👉🏻 대체적으로 탐색을 효율적으로 할 수 있지만(O(log n)), 최악의 경우 O(n)이 걸린다. (왜냐하면 이진 탐색 트리는 삽입 순서에 따라서 선형적일 수 있기 때문이다.)
AVL트리
AVL트리란 앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고, 스스로 균형을 잡는 이진 탐색 트리이다.
두 자식 서브 트리의 높이는 항상 최대 1 만큼 차이난다는 특징이 있다.
이진 탐색 트리는 선형적인 트리 구조를 가질 때 최악의 경우 O(n)의 시간복잡도를 가지지만, AVL 트리는 탐색, 삽입, 삭제 모두 O(log n)의 시간복잡도를 가진다.
레드 블랙 트리(RBT)
레드 블랙 트리란 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 O(log n)의 시간복잡도를 가지는 트리이다.
각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 bit를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 할 때 사용된다.
2-3. 힙(Heap)
힙이란 ? 최댓값이나 최솟값을 빠르게 탐색하기 위한 '완전 이진 탐색 트리' 기반의 자료구조이다. 최소 힙과 최대 힙 2가지가 있다.
- 최대 힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 크다.
- 최소 힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작다.
2-4. 우선순위 큐(Priority Queue)
우선순위 큐란 ? 대기열에서 우선순위가 가장 높은 요소가 먼저 나가는 자료구조
우선순위 큐는 힙(Heap)을 기반으로 구현된다. ✨
2-5. 해시 테이블
해시 테이블이란 ? 해시함수를 사용해서 변환한 값을 index로 삼아 Key와 Value를 저장하는 자료구조
다시 말해 해시 테이블은 어떤 특정 값을 받아서 해시 함수에 입력하고, 함수의 출력값을 인덱스로 삼아 데이터를 저장한다.
삽입, 삭제, 탐색 시에 평균적으로 O(1)의 시간복잡도를 가진다.