220613_인터넷 강의_자료 구조

티스토리에 저장했던 글을 옮겼습니다.
https://mrcocoball.tistory.com/85

1. 자료 구조(Data Structure) 중요함!!

• 실제로 구현하지는 않고 JDK에 이미 구현되어 있는 것을 사용하지만 개념 알아두는 것이 좋음

(1) 선형 자료 구조 : 앞 뒤의 요소가 1:1, 한 줄로 자료를 관리

• 배열 (Array)
  • 선형으로 자료 관리, 정해진 크기의 메모리를 먼저 할당 받아 사용
  • 자료의 물리적 위치 / 논리적 위치가 같음. 따라서 중간에 요소가 비어 있으면 안됨
    (사라지거나 늘어나게 되면 물리적 위치, 논리적 위치가 일치해야 하므로
    앞으로 당기거나 뒤로 미루는 등의 작업 必)
  • 요소의 추가 / 삭제가 시간이 걸리나 인덱스 연산이므로 특정 요소의 위치를 찾는 연산이 빠름
• 연결 리스트 (LinkedList)
  • 선형으로 자료 관리, 자료가 추가될 때마다 메모리를 할당 받음
  • 자료는 링크로 연결되며, 물리적 위치와 논리적 위치가 다를 수 있음
    (배열은 자료만 가졌지만 연결 리스트는 포인터가 있어 요소를 가리키는 방향이 있음)
  • 요소의 추가 / 삭제가 쉬우나 특정 요소의 위치를 찾는 연산이 느림
• 스택 (Stack)
  • 가장 나중에 입력된 자료가 가장 먼저 출력되는 자료 구조 (Last in First Out, 후입 선출)
  • 요소 추가(push) / 꺼내어 삭제(pop)가 top에서 이뤄짐
  • 배열, 연결 리스트 등으로도 구현 가능
• 큐 (Queue)
  • 가장 먼저 입력된 자료가 가장 먼저 출력되는 자료 구조 (First in First Out, 선입 선출)
  • 맨 뒤 (rear) 에서 추가 (enqueue) 하고 맨 앞 (front) 에서 삭제 (dequeue)
  • 배열, 연결 리스트 등으로도 구현 가능

(2) 비선형 자료 구조

• 트리 (Tree)
  • 부모 노드와 자식 노드 간의 연결로 이루어진 자료 구조
  • 이진 트리(binary tree, 부모 노트에 자식 노트가 두 개 이하인 트리 ) 를 많이 사용
  • 힙(heap) : 우선 순위가 높은 값(key)을 꺼냄 (Priority Queue)
    • Max heap : 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우
    • Min heap : 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우
  • 이진 검색 트리 (binary search tree) : 검색을 위해 만들어졌으며 힙과 달리 중복되는 값(key)을 허용하지 않음
    • 왼쪽 자식 노드는 부모 노드보다 작은 값
    • 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐
    • 자료 검색 시간이 평균 log(n) 이며 선형 자료 구조보다 빠른 편
    • inorder traversal (left를 보고 부모를 먼저 보고, right를 보는 형식) 탐색을 하게 되면 자료가 정렬되어 출력
      -> TreeSet, TreeMap 클래스
• 그래프 (Graph)
  • 정점과 간선들의 유한 집합 G = (V,E)
  • 정점 (vertex) : 여러 특성을 가지는 객체, 노드 (node)
  • 간선 (edge) : 이 객체들을 연결 관계를 나타냄, 링크 (link)
  • 간선은 방향성이 있는 경우와 없는 경우가 있음
  • 그래프 구현 방법 : 인접 행렬 (adjacency matrix), 인접 리스트 (adjacency list)
  • 그래프 탐색 방법 : BFS(bread first search), DFS(depth first search)
• 해싱 (Hashing)
  • 자료를 검색하기 위한 자료 구조
  • 키(key)에 대한 자료를 검색하기 위한 사전 (dictionary) 개념의 자료 구조
  • key는 유일하게 이에 대한 value를 쌍으로 저장
  • index = h(key) : 해시 함수가 key에 대한 인덱스를 반환해주며 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨
    (자료를 넣는 순서와 무관)
  • 해시 함수에 의해 인덱스 연산이 산술적으로 가능
  • 저장되는 메모리 구조를 해시 테이블이라 함 (버켓 x 슬롯, 슬롯이 배열 형식)
    -> 버켓이 커지게 되면 이에 따른 슬롯이 늘어나 빈 공간이 많아질 수 있으므로 LinkedList를 활용해 체이닝을 진행 (다만 구현이 복잡해짐)
    -> HashMap, Properties 클래스