기초 CS

Array vs List

Array :

• 연속된 메모리 공간에 순서대로(연속적으로) 원소 저장
• 정적 크기 (생성될 때 크기 지정)
• 배열 중간에 원소 삽입/삭제하려면, 모든 원소 하나씩 이동
• 인덱스로 직접 접근은 List에 비해 빠른 편

List :

• 개별적 메모리에 원소 저장, 각 원소는 다음 원소를 가리키는 포인터 가짐

• 동적 크기

• 각 원소가 개별적 메모리에 저장되어 있어 삽입/삭제 용이

• 특정 위치 원소에 직접 접근 불가, 첫 번째부터 순서대로 찾아야 함

  Array는 메모리를 연속적으로 사용할 때, list는 삽입/삭제 연산이 빈번한 경우 유리

Stack vs Queue

Stack :

• Last in First Out (후입선출)
• 데이터 삽입(push), 삭제(pop)가 스택의 맨 위에서 발생
• 스택에 쌓일 수 있는 데이터 한정, stack overflow 가능

Queue :

• First in First Out (선입선출)
• 큐의 데이터 삽입은 rear에서 enqueue, 삭제는 front에서 dequeue

메모리 할당 방식에 있어 차이, 스택과 큐는 모두 선형 데이터 구조

Graph vs Tree

Graph :

• 임의 개수 노드와 간선으로 구성 (directed/undirected)
• 트리와 달리 사이클이 있을 수도 있음
• 인접 리스트/인접 행렬을 통해 저장
  
  인접리스트 : 각 노드의 이웃 노드를 LinkedList로 저장
  인접행렬 : 노드 간 연결 여부를 이차원 행렬로 저장

Tree :

• 계층 구조로, 각 노드는 한 개의 부모 노드와 여러 개의 자식 노드 가질 수 있음
• 부모-자식 노드 간 연결을 포인터/참조로 저장

(종류)

• Binary Tree : 각 노드가 최대 두 개의 자식 노드를 갖는 트리 >> Binary Search Tree
• Binary Search Tree : 이진 트리의 일종, 임의 노드 기준 왼쪽 서브 트리는 모두 현재 노드 보다 작고 역도 성립. 데이터 검색/갱신 효율적
• Completely Binary Tree : 마지막 레벨을 제외한 모든 레벨의 노드가 꽉 차있는 이진 트리 >> Heap
• Heap : BST 일종, 우선순위큐 구현(MaxHeap, MinHeap), 삽입/삭제 시 힙 특성 유지 : 시간 복잡도 O(logn)