[OS] Kernel 자료구조

▶ Kernel 자료구조

▷ Linked List

Singly Linked List	Doubly Linked List	Circular Linked List
단방향(단일) 연결리스트	양방향(이중) 연결리스트	원형 연결리스트
다음 원소의 주소를 붙여놓은 형태	다음 자료와 이전 자료의 주소를 붙여 놓은 형태	연결 리스트의 마지막 항목에 첫 항목의 주소를 붙여 놓은 형태

▷ BST, Binary Search Tree (이진 탐색 트리)

• 자료 간의 부모-자식 관계(상하 관계)를 표현하는 자료 구조이다.
  • 왼쪽 서브트리 ≤ 자신
  • 오른쪽 서브트리 ≥ 자신

• 이진 탐색 트리가 검색할 때 효율적이라는 것을 알 수 있다!

  	선형 검색	이진 탐색 트리
  검색 성능	O(n)	O(lg n)
  시간 복잡도	선형 시간 복잡도	로그 시간 복잡도

▷ HashFunction & HashMap (해시함수 & 해시맵)

• 자료를 입력 받아 결과를 출력하는 함수이다.
• 함수의 형태이기 때문에 어떤 자료든 빠르게 탐색할 수 있다는 장점이 있다.
• 검색할 키값을 주면 hash function에 의해 검색된다.

▷ Bitmap

• 이진수 형태의 자료 구조이다.
• 0은 사용가능, 1은 불가능을 나타낸다.

---

📎참조

• 성결대학교 강영명 교수님 운영체제 (2023)
• https://heavenxworld.tistory.com/21
• https://pwnkidh8n.tistory.com/114
• https://heavenxworld.tistory.com/22