[CS] 자료구조 (for 기술면접 대비)

선형 구조

• List
  • Array List
    - 배열 이용하여 구현
    - 장점 : index 통한 순차적 접근 유리
    - 단점 : 삽입, 삭제 시 계산량 많아짐 (해당 index 기준으로 앞/뒤 shift 연산 필요)
  • Linked List
    - node = data + next로 구성 : next에 다음 node 위치 저장
    - 단일 연결 (Singly Linked List)
       : 동적 메모리 사용하지만, 특정 데이터를 찾으려면 head부터 찾아야 함
    - 이중 연결 (Doubly Linked List)
       : 양방향으로 각 node의 전, 후 알 수 있지만, pointer를 2개 보유해야 함
    - 원형 연결 (Circular Linked List)
      : 마지막 node의 next가 첫번째 node 가리킴
• Stack
  - LIFO : 마지막에 들어온 것이 먼저 나감
  - Array / Linked List로 구현
  - 함수 호출 및 재귀 프로그램 순서 제어, 서브루틴 호출 시 주소 저장 등에서 사용
• Queue
  - FIFO : 먼저 들어간 것이 먼저 나감
  - Array / Linked List로 구현
  - 대기 행렬 처리, 운영체제 작업 스케쥴링 등에서 사용
  - 원형 Queue : 1차원 배열을 원형으로 표현, mod 연산자로 n개의 공간을 0:n-1로 운용
• Deque
  - Stack + Queue 장점으로 구성
  - 삽입, 삭제가 list의 양 끝에서 모두 가능
  - Scroll : 한쪽만 삽입 + 양쪽 삭제 가능
  - Self : 양쪽으로 삽입 + 한쪽만 삭제 가능

비선형 구조

• Graph
  - node(vertex) + edge
  - 방향 : 간선 간 방향 존재 / 무방향 : 간선 통해 양방향 이동 가능
  - 가중치 그래프 (=네트워크) : 간선에 가중치 할당
  
  • DFS (Depth First Search) : 깊이 우선 탐색
    - Stack 이용
  • BFS (Breath First Search) : 너비 우선 탐색
    - Queue 이용

• Tree
  - 방향 그래프 중 하나, 순환 불가능
  - node, edge / root node, leaf node, internal node 구성
  
  • 이진 트리 (Binary Tree) : 모든 node의 자식이 2개
    - 포화 이진 트리 (Full Binary Tree) : 모든 node의 child node가 0개 또는 2개 
    - 완전 이진 트리 (Complete Binary Tree) : 왼쪽부터 차례대로 삽입하는 트리
    - Perfect Binary Tree = Full + Complete
  • Heap : 최대/최소 연산 빠르게 하기 위한 완전 이진 트리
    - 배열로 변환 시 중간에 null이 없음
    

• Hash 
  - 특정 input 대한 일정 output 존재
  - 파이썬의 Dictionary
  
  • Hash Table : thread safe + null 넣을 수 없음
  • Hash Map : thread non-safe + null 사용 가능