1. 데이터의 선형적 배치와 관리, 선형 자료구조의 개요
정의: 데이터 요소들을 순차적으로 나열시킨 자료구조로, 하나의 요소 뒤에 하나의 요소가 이어지는 1:1 인접 관계를 가지는 구조.
특징: 자료 간의 선후 관계가 명확하며, 데이터의 저장 순서와 입출력 방식에 따라 스택, 큐, 리스트 등으로 구분됨.
2. 선형 자료구조별 입출력 원리 및 핵심 메커니즘
가. 스택 (Stack): 후입선출(LIFO)의 구조
입출력 원리: 한쪽 끝에서만 데이터의 삽입과 삭제가 일어나는 LIFO(Last-In, First-Out) 방식.
주요 연산: * Push: 데이터 삽입 ($Top$ 포인터 증가)
Pop: 데이터 추출 및 삭제 ($Top$ 포인터 감소)
활용 사례: 함수 호출의 복귀 주소 관리(System Stack), 수식의 후위 표기법 변환, 실행 취소(Undo).
나. 큐 (Queue): 선입선출(FIFO)의 구조
입출력 원리: 한쪽 끝(Rear)에서는 삽입만, 다른 쪽 끝(Front)에서는 삭제만 일어나는 FIFO(First-In, First-Out) 방식.
주요 연산: * Enqueue: 데이터 삽입 ($Rear$ 포인터 이동)
Dequeue: 데이터 추출 및 삭제 ($Front$ 포인터 이동)
활용 사례: OS 스케줄링(Ready Queue), 프린터 스풀링, 네트워크 패킷 버퍼링.
다. 리스트 (List): 위치 기반의 유연한 구조
입출력 원리: 순서가 있는 데이터의 집합으로, 특정 위치(Index)를 기반으로 임의의 위치에서 삽입과 삭제가 가능한 구조.
유형별 특징: * 선형 리스트(Array List): 연속된 메모리 공간 배치, 인덱스 접근 빠름, 삽입/삭제 시 오버헤드 발생.
연결 리스트(Linked List): 포인터를 통한 논리적 연결, 동적 크기 조절 용이, 삽입/삭제 시 포인터 변경만으로 가능.
활용 사례: 동적 메모리 할당 관리, 다항식 계산, 그래프의 인접 리스트 구현.
3. 선형 자료구조 3종 비교 분석
| 구분 | 스택 (Stack) | 큐 (Queue) | 리스트 (List) |
| 입출력 방식 | LIFO (후입선출) | FIFO (선입선출) | 임의 위치 접근 가능 |
| 접근 지점 | 상단 (Top) | 양단 (Front, Rear) | 전체 (Index/Pointer) |
| 포인터 관리 | $Top$ 1개 | $Front$, $Rear$ 2개 | $Head$, $Next$, $Tail$ 등 |
| 삽입/삭제 시간 | $O(1)$ | $O(1)$ | $O(1)$ ~ $O(n)$ |
| 주요 특징 | 재귀적 구조에 적합 | 대기행렬 관리에 적합 | 데이터의 유연한 관리 |
4. 알고리즘 설계 시 자료구조 선택의 기술사적 제언
공간 복잡도 최적화: 데이터의 최대 크기가 정해진 경우 배열 기반 구조를, 가변적인 경우 연결 리스트 기반 구조를 선택하여 메모리 낭비 방지.
시간 복잡도 고려: 빈번한 삽입/삭제가 발생하는 경우 큐나 연결 리스트를, 빠른 검색이 필요한 경우 인덱스 기반 리스트를 활용하는 Trade-off 분석 필수.
결언: 선형 자료구조는 복잡한 비선형 구조(Tree, Graph)를 구현하는 기초 단위임. 기술사는 문제 도메인의 데이터 흐름을 분석하여 최적의 자료구조를 선정함으로써 소프트웨어의 성능과 확장성을 확보해야 함.
