리눅스 커널 프로그래밍 - 커널 자료구조 (1)

리눅스 커널 코드에서 사용 내장 자료 구조에 대해 소개 하도록 하겠습니다.

 

커널 개발자들은 해결책을 스스로 고안하기 보다는 이런 자료구조를 최대한 활용해야 합니다.

 

앞으로 다룰 자료구조는

• 연결 리스트
• 큐
• 맵
• 이진트리

연결리스트는

• 리눅스 커널에서 가장 많이 사용하는 간단한 자료구조
• 노드라고 부르는 가변적인 개수의 데이터를 저장하고 관리하는 기능을 제공
• 동적으로 데이터를 생성해 리스트에 추가
• 그러므로 컴파일 시접에 미리 개수를 알 수 없는 데이터 관리 가능
• 데이터가 인접한 메모리 공간에 모여 있지 않으며
• 따라서 , 데이터를 서로 연결시킬 방법이 있어야 하므로 next라는 포인터 사용

단일 연결 리스트와 이중 연결 리스트

 

 

연결 리스트 내에서 이동

• 연결 리스트내의 이동은 선형으로 일어난다.

• 한 항목을 참조하고 다른 포인터를 따라가 다음 항목을 참조한다.

• 이 과정을 반복하며 해당 데이터에 접근한다.

• 임의순서로 데이터에 접근하는 동작이 중요한 상황에는 연결리스트는 부적절

• 전체 리스트를 차례대로 훑는 작업이나 항목으을 동적으로 삽입하고 제거하는 작업에 적합

• 연결리스트 구현에서 리스트의 '시작' 부분에 접근하기 쉽게 리스트의 첫번째 항목을 헤드(head)라고 부르는 특별한 포인터로 표시하는 경우가 많다

• 환형이 아닌

   

  리스트라면 다음항목을 가라크니는  포인터가 Null인 경우 마지막 항목이 된다.

• 환형 리스트는 첫번째 항목이 마지막 항목이 된다.

리눅스 커널의 구현 방식

리눅스 커널은 구조체를 연결리스트로 바꾸는 대신 구조체에 연결리스트의 노드를 넣는 방식을 사용

 

연결 리스트 구조체