선형 자료구조(Linear Data Structures)

개요

선형 자료구조는 데이터를 순차적으로 저장하고 처리하는 구조로, 가장 기본적이고 널리 사용되는 데이터 조직 방식이다. 데이터의 삽입, 삭제, 탐색 등을 효율적으로 수행할 수 있도록 다양한 형태의 선형 구조가 존재하며, 메모리 구조와 응용 목적에 따라 적절한 자료구조를 선택하는 것이 중요하다. 본 글에서는 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue)의 개념, 구조, 특징, 활용 사례를 체계적으로 정리한다.

---

1. 개념 및 정의

자료구조	정의	특징
배열	동일한 타입의 데이터를 연속된 메모리 공간에 저장	고정 크기, 인덱스 접근 빠름
연결 리스트	포인터를 통해 노드들이 연결된 구조	동적 크기, 삽입/삭제 효율적
스택	한쪽 끝에서 삽입/삭제가 이뤄지는 LIFO 구조	후입선출(Last-In-First-Out)
큐	한쪽에서 삽입, 다른 쪽에서 삭제하는 FIFO 구조	선입선출(First-In-First-Out)

이들은 기본적인 연산을 중심으로 다양한 알고리즘과 응용 구조로 확장된다.

---

2. 배열 (Array)

항목	설명
구조	연속된 메모리 공간에 동일한 타입의 데이터 저장
인덱싱	O(1)의 빠른 접근 속도
단점	크기 고정, 삽입/삭제 비용 높음
활용	이미지 처리, 고정 길이 데이터, 이진 탐색

배열은 정적 데이터를 다룰 때 가장 효율적이다.

---

3. 연결 리스트 (Linked List)

항목	설명
구조	노드 단위로 메모리 할당, 각 노드가 다음 노드를 참조
종류	단일 연결 리스트, 이중 연결 리스트, 원형 리스트
장점	동적 크기, 삽입/삭제 O(1) (위치 알고 있을 때)
단점	임의 접근이 느림 (O(n))
활용	메모리 관리, 중간 삽입/삭제 많은 경우

포인터 기반으로 유연한 구조 설계가 가능하다.

---

4. 스택 (Stack)

항목	설명
구조	한쪽(top)에서만 push/pop 연산 수행
연산	push, pop, peek
사용 예	괄호 검사, DFS, 함수 호출 스택
구현 방식	배열 기반, 연결 리스트 기반 모두 가능

스택은 후입선출 구조로 재귀적 구조를 표현하는 데 탁월하다.

---

5. 큐 (Queue)

항목	설명
구조	앞(front)에서 제거, 뒤(rear)에서 삽입
연산	enqueue, dequeue
종류	일반 큐, 원형 큐, 우선순위 큐, 덱(Deque)
사용 예	CPU 스케줄링, BFS, 네트워크 패킷 처리

큐는 순차적 처리와 실시간 응답 처리에서 핵심적인 구조다.

---

6. 주요 연산 비교

연산	배열	연결 리스트	스택	큐
삽입	O(n)	O(1) 또는 O(n)	O(1)	O(1)
삭제	O(n)	O(1) 또는 O(n)	O(1)	O(1)
탐색	O(1) (인덱스)	O(n)	O(n)	O(n)
접근	O(1)	O(n)	제한적	제한적

선형 자료구조 선택은 연산 특성과 사용 목적에 따라 달라진다.

---

7. 활용 사례

분야	자료구조	활용 사례
컴파일러	스택	구문 분석, 함수 호출 관리
운영체제	큐	프로세스 스케줄링, 프린터 관리
그래픽 렌더링	배열	픽셀 배열, 행렬 연산
메모리 관리	연결 리스트	할당/해제 추적, 캐시 리스트 구성

선형 자료구조는 컴퓨터 과학과 실무 전반에서 기본적인 역할을 수행한다.

---

8. 결론

선형 자료구조는 모든 알고리즘 설계의 기반이 되는 가장 기본적인 데이터 구조이다. 배열, 연결 리스트, 스택, 큐는 각각의 구조적 특징에 따라 다양한 문제에 최적화된 솔루션을 제공하며, 개발자는 각 구조의 성능 특성과 활용 목적을 정확히 이해하여 적절히 선택해야 한다. 프로그래밍 실력을 향상시키기 위한 첫걸음은 선형 자료구조의 본질을 깊이 이해하는 것이다.