[자료구조] 선형 자료 구조

선형 자료구조란?

선형 자료구조(Linear Data Structure)는 데이터가 일렬로 나열된 형태로 저장되는 자료구조입니다. 요소 간의 순서가 명확하며, 앞뒤 요소와의 관계를 기반으로 연산이 수행됩니다.

---

1. 연결 리스트 (Linked List)

데이터를 노드(Node)라는 단위로 저장하고, 포인터를 통해 다음 노드와 연결하는 방식의 자료구조입니다.

• 삽입/삭제: O(1) (포인터만 조작하면 되므로 빠름)
• 탐색: O(n) (선형 탐색 필요)

종류

• 싱글 연결 리스트: next 포인터만 존재 (한 방향으로만 순회)
• 이중 연결 리스트: next, prev 포인터를 모두 가짐 (양방향 순회 가능)
• 원형 이중 연결 리스트: 마지막 노드의 next가 헤드 노드를 가리킴, 원형 순회 가능

---

2. 배열 (Array)

같은 타입의 데이터를 연속적인 메모리 공간에 저장하는 자료구조로, 크기가 고정되어 있습니다.

• 중복 허용, 순서 존재, 랜덤 접근 가능
• 접근: O(1)
• 삽입/삭제: O(n) (요소 이동 필요)

접근 방식

• 랜덤 접근: 인덱스를 통해 특정 위치의 데이터를 즉시 접근
• 순차 접근: 처음부터 차례대로 탐색

---

3. 벡터 (Vector, 동적 배열)

동적으로 크기를 조절할 수 있는 동적 배열로, C++의 vector나 Python의 list, Java의 ArrayList가 대표적입니다.

• 중복 허용, 순서 존재, 랜덤 접근 가능
• 접근/탐색: O(1)
• 맨 뒤 삽입/삭제: O(1)
• 중간 삽입/삭제: O(n) (요소 이동 필요)

---

4. 스택 (Stack)

후입선출(LIFO) 구조의 자료구조로, 가장 마지막에 들어간 데이터가 가장 먼저 나옴

• 삽입/삭제 (push/pop): O(1)
• 탐색: O(n)

활용 예시

• 함수 호출 스택
• 브라우저 방문 기록
• 수식 계산, DFS (깊이 우선 탐색)

---

5. 큐 (Queue)

선입선출(FIFO) 구조의 자료구조로, 먼저 들어온 데이터가 먼저 나감

• 삽입/삭제 (enqueue/dequeue): O(1)
• 탐색: O(n)

활용 예시

• CPU 프로세스 스케줄링
• 네트워크 요청 처리
• BFS (너비 우선 탐색)
• 캐시(선입선출 방식)

---

요약 : 선형 자료구조 시간 복잡도 (대표 연산 기준)

자료구조	삽입	삭제	탐색
연결 리스트	O(1)	O(1)	O(n)	O(n)
배열	O(n)	O(n)	O(n)	O(1)
벡터	O(1)/O(n)	O(1)/O(n)	O(n)	O(1)
스택	O(1)	O(1)	O(n)	O(n)
큐	O(1)	O(1)	O(n)	O(n)

벡터의 삽입/삭제는 맨 뒤에서 수행 시 O(1), 중간에서 수행 시 O(n)

---

마무리

선형 자료구조는 가장 기본적인 구조이지만, 적절한 선택에 따라 프로그램의 성능과 효율이 크게 달라질 수 있습니다. 상황에 따라 적합한 자료구조를 선택하는 것이 중요합니다.