1.9 Kernel Data Structure - 64
Lists, Stacks, Queues
Lists
- 배열은 직접 접근 가능하지만, 크기 변화가 자유롭지 않음
- 리스트는 순차적으로 접근하는 자료구조이며, 삽입과 삭제가 용이함
- 형태
- Singly linked list: 각 노드가 다음 노드를 가리킴
- Doubly linked list: 이전, 다음 노드를 모두 가리킴
- Circular linked list: 마지막 노드가 첫 노드를 가리킴
- 단점
Stacks
- LIFO 구조
- push: 삽입
- pop: 삭제
- 함수 호출 시 매개변수, 지역 변수, return address 저장에 활용
Queues
- FIFO 구조
- 프린터 작업 큐, CPU ready queue 등에서 활용
- 삽입한 순서대로 제거됨
Trees
기본 개념