자료구조 간단 정리

선형 자료 구조 : 요소가 일렬로 나열되어 있는 자료 구조이다.

• 연결 리스트 : 데이터를 감싼 노드를 포인터로 연결하여 공간적인 효율성을 증대시킨 자료 구조이다. 삽입에는 O(1)이 탐색에는 O(n)이 걸린다.
• 싱글 연결 리스트 : next 포인터만 가지는 연결 리스트이다.
• 이중 연결 리스트 : next, prev 포인터를 가지는 연결 리스트이다.
• 원형 이중 연결 리스트 : 이중 연결 리스트와 같은 구조를 가지고 있지만 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.
• 배열 : 같은 타입의 변수들로 이루어져 있고 크기가 정해져 있으며 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다. 탐색에는 O(1)이 걸리며 삽입과 삭제는 O(1)이 걸린다.
• 벡터 : 동적으로 요소를 할당할 수 있는 동적 배열이다. 탐색과 맨 뒤의 요소를 삭제, 삽입하는데 O(1)이 걸리고, 맨 앞/뒤이 아닌 요소를 삭제하고 삽입하는데는 O(n)이 걸린다.
• 스택 : 가장 마지막에 들어간 데이터가 가장 첫 번째로 나오는 LIFO을 가진 자료 구조이다. 삽입 및 삭제에 O(1) 탐색은 O(n)이 걸린다.
• 큐 : 먼저 들어간 데이터가 먼저나오는 FIFO 성질을 지닌 자료 구조이다. 삽입 및 삭제에 O(1) 탐색은 O(n)이 걸린다.

비선형 자료 구조 : 일렬로 나열된 구조가 아닌 순서나 관계가 복잡한 자료 구조이다.

• 그래프 : 정점과 간선으로 이루어진 자료구조이다. 양방향 그래프와 단방향 그래프가 존재하며, 간선과 정점 사이에 가중치가 존재하는 그래프도 존재한다.
• 트리 : 루트 노드, 내부 노드, 리프 노드로 구성된 트리 구조의 집합이다.
• 이진 트리 : 자식의 노드 수가 두 개 이하인 트리를 의미한다.
• 정 이진 트리 : 자식 노드가 0 혹은 두 개인 이진트리이다.
• 완전 이진 트리 : 왼쪽에서부터 채워져 있는 이진 트리이다.
• 균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 파가 1 이하인 이지트리이다.
• 이진 탐색 트리 : 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어있는 트리이다. (머리속으로 <<<<<<<<<<< 를 연상하자) 이러한 BST의 특성은 검색을 하기 편리한 장점이 있다. 왼쪽과 오른쪽으로 크기들이 이미 정해져있기 때문이다. 따라서 요소를 찾을 때 BST는 O(logn)의 시간이 걸리며 최악의 경우 O(n)의 시간이 걸리게 된다.
• AVL 트리 : 두 자식의 서브트리 높이가 항상 최대 1만큼 차이가 나는 특징을 가진 트리이다. BST와 전반적인 구조는 같으나 삽입과 삭제가 일어날때마다 균형이 안맞을 경우 트리 일부를 왼쪽, 오른쪽으로 돌려가면서 균형을 잡는다.
• 레드 블랙 트리 : 균형 이진 탐색 트리로 검색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이다.
• 힙 : 완전 이진 트리를 기반으로하는 자료 구조 이며 최소힙, 최대힙 두 가지의 종류가 있다.
• 최대힙 : 루트 노드의 키는 모든 자식의 키보다 커야한다. 마찬 가지로 각 자식 노드들도 루트 노드와 같은 특징을 갖는다.
• 최소힙 : 최대힙과 반대
• 우선순위 큐 : 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조이다.