자료구조 간단 정리

Array

• 여러개의 데이터를 저장할 수 있는 자료형
• 선언할 때 고정된 크기로 선언한다. 이후에 변경할 수 없다.
• 인덱스로 데이터에 접근하면 O(1)이다.

List

• 배열과 마찬가지로 여러개의 데이터를 저장할 수 있으나 크기가 고정되지 않아 자유롭게 추가하거나 삭제할 수 있다.
• 대표적으로 ArrayList와 LinkedList가 있다.
• 둘은 논리적, 물리적 저장 순서가 일치하느냐의 차이이다.

ArrayList

• 논리적, 물리적 저장순서가 일치한다.
• 즉 일반 배열 처럼 데이터가 메모리상에 인접하여 저장된다.
• 인덱스로 데이터에 접근하면 O(1)이다.
• 삽입, 삭제 시 기존 원소들을 삽입, 삭제된 원소 갯수 만큼 이동시켜야하므로 O(n)의 시간이 걸린다.

LinkedList

• 논리적, 물리적 저장 순서가 일치하지 않는다.
• 즉 개념상으로는 데이터가 연결되서 저장되어있지만 실제로는 메모리 상에 랜덤한 위치에 있으며, 원소가 다음 저장위치를 가리키는 주소를 가지고 있다.
• 데이터를 처음 노드 부터 찾아야 하므로 접근 속도가 O(n)이다.
• 삽입 삭제도 O(n)이다.
  • 삽입, 삭제 자체는 다음 노드를 가리키는 주소만 변경하면 되기 때문에 O(1)이지만 삽입할 위치, 삭제할 노드를 찾으려면 O(n)이 걸리므로 결국 O(n)이다.

Stack

• 후입선출(LIFO): 나중에 입력된 데이터가 먼저 출력된다.

Queue

• 선입선출(FIFO): 먼저 입력된 데이터가 먼저 출력된다.

Tree

• 노드(Node)와 간선(Edge)으로 이루어진 자료구조.
• 계층적인 형태로 표현할 때 사용한다. 즉 사이클이 없다.
• 검색, 최대최소값, 우선순위 등을 구현할때 사용한다.
• 노드를 순회하는 방식은 크게 세 가지 전위, 중위, 후위 순회가 있다.
• 트리의 종류

Binary Tree

• 자식 노드를 최고 두 개까지 갖는 트리

Complete Binary Tree

• 마지막 레벨을 제외하고, 모두 자식 노드의 갯수가 두 개인 트리.
• 마지막 레벨은 모두 채워질 필요는 없으나 왼쪽에서 오른쪽으로 채워져 있어야 한다.

Binary Search Tree

• 부모와 자식의 데이터의 크기가 다음 규칙을 만족하는 트리이다.
• 왼쪽 자식 < 부모 < 오른쪽 자식
• 원하는 데이터를 탐색하는 데 트리의 높이(h)만큼의 O(h)가 소요된다.
• 균등하게 데이터가 들어간다면 O(log(n))이지만 편향된 트리라면 O(n)으로 일반 리스트와 같아진다.
• 편향된 트리를 개선하기 위해 AVL 트리, Red Black 트리가 있다.

Heap

• 완전 이진 트리의 한 종류.
• 최대값과 최소값을 빠르게 찾는 데 사용한다.
• 부모 노드의 값이 자식 노드의 값 보다 크면 최대힙, 작으면 최소힙이라고 한다.
• 즉 루트 노드가 최대값이거나 최소값이 된다. 따라서 최대값(최소값) 탐색은 O(1)

Priority Queue

• 우선순위 큐: 큐에 pop을 하면 먼저 들어온 순서부터 나오지만, 우선순위 큐는 우선순위가 높은 데이터가 출력된다.
• 힙으로 구현한다.

B-Tree

• 이진 트리를 개선하여 탐색 성능을 높인 트리.
• 균형있게 높이를 유지하는 Balanced Tree. 모든 leaf 노드가 같은 레벨로 유지되도록 자동으로 밸런스를 맞춘다.
• 항상 균형된 높이를 유지하므로 탐색 시간은 O(log(n))이다.
• 자식 노드 수가 2개 이상이며 노드의 키(데이터)가 1개 이상이다. 한 노드의 키들은 항상 정렬되어있다.

Hash Table

• 키, 값 형식의 자료 구조. 키로 값에 O(1)의 빠르게 접근할 수 있는 구조이다.
• 해시 함수를 사용해서 인덱스를 구한다.
• 해시 함수로 구한 인덱스는 충돌, 즉 같은 값이 나올 수 있으며 이를 해결하기 위한 방법으로 두 가지가 있다.
  • 분리 연결볍(Seperate Chaining): 충돌난 주소에 리스트 형태로 값을 저장하는 방법
  • 개방 주소법(Open Addressing): 해시 테이블 내 비어있는 주소가 나올때 까지 주소를 다시 구하는 방법