1.9 Kernel Data Structure - 64

Lists, Stacks, Queues

Lists

• 배열은 직접 접근 가능하지만, 크기 변화가 자유롭지 않음
• 리스트는 순차적으로 접근하는 자료구조이며, 삽입과 삭제가 용이함
• 형태
  • Singly linked list: 각 노드가 다음 노드를 가리킴
  • Doubly linked list: 이전, 다음 노드를 모두 가리킴
  • Circular linked list: 마지막 노드가 첫 노드를 가리킴
• 단점
  • 원소 탐색은 O(n)

Stacks

• LIFO 구조
• push: 삽입
• pop: 삭제
• 함수 호출 시 매개변수, 지역 변수, return address 저장에 활용

Queues

• FIFO 구조
• 프린터 작업 큐, CPU ready queue 등에서 활용
• 삽입한 순서대로 제거됨

Trees

기본 개념

• 부모-자식 관계를 이용한 계층적 자료구조