[ Data Structure ] 연결 리스트(linked list)

Single Linked list

• 컨테이너는 자료를 관리할 수 있는 구조이다.
• 연결 리스트는 여러 구조체 인스턴스를 체인처럼 줄줄이 포인터로 연결한 자료구조이다.
• 연결에 사용된 포인터 숫자가 한 개이고 자기 다음을 가리키는 것이 특징이다.

연결 리스트 코딩 요령

• 구조체 배열로 테스트한다.
• 연결 순서를 임의로 변경해본다.
• 리스트 출력은 별도 함수로 분리한다.
• 디버거로 노드 하나씩 따라가며 메모리 위치를 확인한다.

활용 사례

Free Block List on File Systems

(a) 자유 블록 리스트(free block list)

• 연결 리스트 형태로 사용되지 않는 디스크 블록의 번호들을 관리한다.
• 새로운 파일을 저장할 때 이 리스트에서 빈 블록을 할당받는다.
• 파일이 삭제되면 해당 블록 번호가 이 리스트에 추가된다.

(b) 비트맵(bitmap)

• 비트 배열로 전체 디스크 블록의 사용 여부를 추적한다.
• 각 비트는 해당 블록이 사용 중인지(1) 아니면 비어있는지(0)를 나타낸다.
• 비트맵을 통해 전체 디스크 공간의 사용 현황을 쉽게 파악할 수 있다.

이 두 가지 자료 구조를 병행하여 사용함으로써 효율적인 디스크 공간 관리가 가능해진다. 자유 블록 리스트는 빈 블록들을 빠르게 찾을 수 있게 해주고, 비트맵은 전체 디스크의 통계 정보를 제공한다. 데이터를 저장하거나 삭제할 때 두 자료구조를 함께 업데이트하여 일관성을 유지한다.