19. 커널 자료 구조(kernel data structure) 1

자료 구조의 가장 기초적인 형태는 배열(array)이다. 배열의 각 원소의 크기는 일정하다. 이러한 성질 덕분에 원소의 주소를 (원소 번호) * (원소 크기)로 쉽게 구할 수 있다. 다만, 이러한 성질은 데이터의 추가/삭제가 용이하지 않다는 점과 함께 배열의 단점이 되기도 한다.

연결 리스트(linked list)는 배열의 이러한 단점을 보완하는 자료 구조로, 각 원소에 다른 원소를 가리키는 부분이 추가된 형태이다. 이 중 단일 연결 리스트(singly linked list)는 다음 원소의 주소를 붙여놓은 형태이고, 이중 연결 리스트(doubly linked list)는 다음 자료와 이전 자료의 주소를 붙여 놓은 형태이다. 환형 연결 리스트(circularly linked list)는 연결 리스트의 마지막 항목에 첫 항목의 주소를 붙여 놓은 형태이다. 연결 리스트는 n개의 자료를 탐색하는 데에 최대 n개의 자료를 살펴봐야 한다. 이는 연결 리스트가 탐색에 있어서 비용이 크다는 것을 의미한다. 연결 리스트는 직접 쓰이기 보다는 후에 서술할 스택, 큐 등을 구현하는 데에 더 많이 쓰인다.

스택(stack)은 LIFO(Last In, First Out)형식의 자료 구조이다. LIFO는 나중에 들어간 자료가 먼저 나온다는 것을 의미한다. 스택의 자료는 push로 입력하고 pop으로 출력한다. 이 구조는 함수에서 주로 쓰인다. 함수가 실행되는 것을 push, 함수가 종료되는 것을 pop으로 볼 수 있다.

큐(queue)는 FIFO(First In, First Out)형식의 자료 구조이다. FIFO는 먼저 들어간 자료가 먼저 나온다는 것을 의미한다. 큐는 CPU 스케쥴링, 프린터 대기열 등 운영체제의 전반적인 부분에 쓰인다.