운영체제 서론(4) - 자료 구조

 이번 글은 운영체제 서론으로서 자료 구조(Data structure)에 대해서 다루겠습니다.  

 

자료 구조에 속하는 것은 다음과 같은 것이 있습니다.

- 배열, 리스트, 스택, 큐, 트리, 해시 함수, 해시 맵, 비트맵

(1) 배열(Array)
- 배열은 각 원소가 직접 접근할 수 있는 가장 단순한 자료 구조입니다. 

  예를 들어, 주 메모리는 하나의 배열로 구축됩니다.

  하지만 크기가 변하는 데이터를 저장하거나, 한 데이터를 제거하고 나머지 데이터들을 유지해야 하는 경우

  에는 배열 대신 다른 자료 구조가 필요합니다. 

(2) 리스트(List)

- 리스트는 배열에 이어 컴퓨터 과학의 가장 기본적인 자료 구조입니다.

  배열의 각 항은 직접 접근할 수 있으나, 리스트의 항들은 특정 순서로 접근 해야 합니다. 

  즉, 리스트는 데이터 값들의 집단을 하나의 순서로 표시합니다. 

  이 구조를 구현하는 가장 일반적인 방법이 연결 리스트(linked list)입니다. 

  연결 리스트에는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있습니다. 

  연결 리스트의 장점은 가변 수의 항들을 수용하며 항의 삭제와 삽입이 쉽다는 점입니다.

  반면, 단점은 크기가 n인 리스트에서 특정 항을 인추랄 때의 성능이 O(n)이라는 점입니다. 

(3) 스택(Stack)

- 스택은 순차적 순서를 가진 자료구조로서, 후입선출(LIFO, Last In First Out)을 사용합니다. 

  즉, 스택의 마지막에 삽입된 항이 먼저 인출됩니다. 

  스택에 항을 삽입하거나 인출하는 일은 각각 푸쉬(push), 팝(pop)이라고 합니다. 

   

(4) 큐(Queue)

- 큐는 순차 순서의 자료구조로서, 선입선출(FIFO, First In First Out)을 사용합니다. 

   즉, 각 항들은 큐에 삽입된 순서대로 제거됩니다. 

(5) 트리(Tree)

- 트리는 데이터의 서열을 표시하는데 사용 가능한 자료구조입니다. 

   트리에서 데이터 값들은 부모-자식 관계에 의해 연결됩니다. 

   일반 트리는 부모가 임의의 수의 자식을 가질 수 있으며, 

   이진 트리는 부모가 최대 2개의 자식을 가질 수 있습니다. 

(6) 해시 함수(Hash function)

-  해시 함수는 데이터를 입력 받아 이 데이터에 산술 연산을 수행하여 하나의 결과값을 내놓는 함수입니다.

   해시 함수의 결과값은 하나의 테이블에 저장될 수 있습니다.

   해시 함수의 장점은 테이블에서 해시 함수를 사용하여 데이터를 인출할 경우 O(1)으로 가능하다는 점입니다.

   반면 크기 n인 리스트는 특정 항을 검색 시 O(n)의 시간이 필요합니다.

(7) 해시 맵(Hash map)

- 해시 맵은 해시 함수를 사용하여 키-값(key-value)을 매핑 시킨 것을 의미합니다. 

  매핑이 성립되면 키에 해시 함수를 적용 했을 때, 해시 맵으로부터 그 값을 얻을 수 있습니다. 

(8) 비트맵

- 비트맵은 n개의 항의 상태를 나타내는데 사용 가능한 n개의 이진 비트의 스트링입니다. 

  예를 들어, 다수의 자원이 있을 때 각 자원의 가용 여부를 이진 비트의 값으로 표시할 수 있습니다.     

  001011101 

  이 때, 0은 자원이 사용 가능함을 표시하고, 1은 사용 불가능함을 표시합니다.

  따라서 자원 0,1,3,7은 사용 가능하고, 자원 2, 4, 5, 6은 사용 가능하지 않습니다. 

이 글의 내용은 다음 운영체제 책(https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=46380306)을 참조했습니다.