[TIL] 자료구조 : 데큐, 링크드리스트, 해시테이블, 힙트리

👏🏻 Deque

 - 양방향 대기열이라고도 불리는 자료구조

 - Stack과 Queue의 혼합구조로 Queue와 외형적으로 비슷한 구조

---

📍 Deque의 특징

 ① Stack및 Queue를 모두 사용 가능

  - 양쪽으로 데이터를 추가하고 삭제할 수 있어서 Stack과 Queue 구현 가능

  - 추가와 삭제를 양쪽에서 제어 가능 (ex. 데이터 추가는 한쪽에서만 가능하고 삭제는 양쪽 가능)

 ② 양방향 끝에서 데이터 추가 삭제 용이

  - 데이터의 인덱스 정보를 가지고 있어 양쪽에서 데이터 접근, 추가, 삭제 용이

 ③ 임의의 데이터만 추가하거나 삭제는 불가

  - 데큐는 양방향 끝의 인덱스 정보를 가지고 있어 양방향이 아닌 중간에 있는 데이터 접근은 어려움

---

👏🏻 Linked List : 연결 리스트

 - 선형으로 그룹화된 데이터의 집합

 - 데이터와 다음 데이터의 주소를 포함하고 있는 하나의 노드가 연결된 구조

 - 배열은 연속된 공간 안에 메모리를 차지하고 인덱스로 각각의 요소의 데이터를 읽거나 쓸 수 있는 자료구조

    - 연속된 메모리 주솟값 안에 데이터를 넣는 구조로 위치를 바꾸려면 데이터가 이동해야 함

  - 연결 리스트는 흩어진 공간에 노드들의 연결로 이루어진 자료구조 

 

---

📍 Linked List 의 특징

 ① 노드의 추가와 삭제가 빠르고 쉬움

  - 배열(추가 삭제시 재할당)과 달리 순서가 없어 어디서나 손쉽게 추가 삭제 가능

 ② 노드의 값을 찾으러면 최대 전체를 순회해야 함

  - 배열(연속적으로 이어져 있음)과 달리 메모리에 흩어져 있어 쉽게 접근이 어려움

---

👏🏻 Hash Table

 - 해시 함수를 사용하여 변환한 해시를 색인으로 삼아 키와 데이터를 저장하는 자료구조

 - 전화번호 단축키 지정과 비슷한 개념으로 저장명을 key로, 단축키를 hash로, 전화번호를 value라고 생각하면 됨

---

📍 Hash Table 의 특징

 ① 저장, 삭제, 검색 과정

  - 저장, 검색, 삭제 평균적으로 O(1)의 시간 복잡도를 가지고 있어 데이터를 다루는 작업이 매우 빠름

  - 해시함수에 키 값을 넣어 해시 값을 만들고 해시 값과 일치하는 인덱스를 찾아 검색, 삭제, 저장

  - 해시함수를 거쳐 해시를 찾아내는 시간은 고려하지 않음

 ② 대표적인 해시 알고리즘

   (1) Division Method

     - Number type의 키를 저장소의 크기로 나누어 나온 나머지를 색인으로 사용

     - key 값이 23일 때 테이블 크기가 7이라면 인덱스는 2 ! :: 23 % 7 = 2

   (2) Digit Folding

     - 키의 문자열을 아스키코드로 바꾸고 그 값을 합해 저장소에서 인덱스로 사용

   (3) Multiplication Method

     - 숫자로 된 키 값(K)과 0과 1 사이의 실수(A), 2의 제곱수인 (M)을 사용하여 (KA mod 1)m으로 인덱스 계산

   (4) Universal Hashing

     - 다수의 해시함수를 만들어 특정 장소에 넣고 무작위로 해시함수르 선택하여 해시 값 선정

---

📍 해시 충돌 해결 방법

  💡 해시 충돌 Hash Conflict 

    : 서로 다른 키가 같은 해시가 되는 경우

 

 ① 개방 연결법 Open Addressing

  - 해시 충돌 발생 시, 다른 인덱스에 해당 자료를 삽입

   (1) Linear Probing

    - 현재 중복된 색인으로 부터 고정된 숫자만큼 이동하여 비어있는 저장소에 데이터 저장

   (2) Quadratic Probing

    - 현재 중복된 색인으로 부터 이동할 숫자를 제곱으로 사용 ( 첫 충돌은 : 1^1, 두번째 충돌은 : 2^2, 세번재 충돌은 : 3^3 )

   (3) Double Hasing Probing

    - 하나의 해시함수에서 충돌이 발생한다면 미리 지정해 둔 다른 해시 함수를 이용해 새로운 주소를 받아 사용

 ② 분리 연결법 Seperate Chaining

  - 동일한 인덱스의 데이터에 대해 연결 리스트, 트리 등의 자료구조를 활용해 데이터의 주소 저장

 ③ 저장소 확장 Resize

  - HashMap이라는 자료구조로 저장소의 크기를 두 배 이상 늘려 성능 감소 문제 해결

---

👏🏻 Heap Tree

 - 우선 순위에 따라서 빠르게 자료를 검색할 수 있는 구조

 - 응급실에 응급환자부터 치료하는 것과 비슷한 개념

 - 느슨한 정렬구조로 구현

   * 느슨한 정렬구조 ? 부모는 자식보다 항상 크거나 작게 정렬 & 자식끼리는 값 크기 중요 x

---

📍 Heap Tree 의 특징

 ① 완전 이진 트리

  - 삽입 삭제 시 성능을 위해 완전 이진 트리로 구현

 ② 중복된 값 저장 

  - 일반적인 이진 탐색 트리와 달리 중복된 값 저장 가능

  - 힙트리는 단순히 최댓값과 최솟값을 찾아내기 위한 구조

 ③ 최대 / 최소 힙

  - 루트 노드가 가장 큰 값이고 점점 작은 값으로 구현 한다면 최대 힙

  - 루트 노드가 가장 작은 값이고 점점 큰 값으로 구현 한다면 최소 힙

---

📍 Heap Tree 데이터 처리 방식

 ① 데이터 검색

  - 시간 복잡도는 0(1)

 ② 데이터 삽입

   (1) 가장 마지막 노드에 새로운 값 저장

   (2) 삽입된 노드와 부모의 값 비교

   (3) 최대 힙일 경우 부모가 더 크다면 유지, 삽입된 노드가 더 크다면 위치 변경

   (4) 계속해서 (1)-(3) 과정 반복

③ 데이터 삭제

   (1) 루트 노드의 값 제거

   (2) 루트 자리에 마지막 노드 값 삽입

   (3) 올라간 노드의 값과 자식 노드의 값 비교하며 값 위치 변경

---