3.1.1. 기본 자료구조 활용: 연결 리스트, 스택, 큐, 트리

'3.1.1. 기본 자료구조 활용' 파트는 소프트웨어 설계 및 구현의 기초가 되는 가장 중요한 부분입니다. 필기 시험에서는 각 자료구조의 운영 방식(LIFO/FIFO), 삽입/삭제 알고리즘, 그리고 트리 순회 방법이 매회 출제됩니다.

 

1. 연결 리스트 (Linked List)

데이터를 노드(Node) 단위로 저장하며, 각 노드가 다음 노드의 주소를 가리키는 방식입니다.

• 구조: 데이터부(Data) + 포인터부(Link)
• 특징:
  • 동적 메모리 할당: 필요할 때마다 노드를 생성하므로 메모리 낭비가 적습니다.
  • 삽입/삭제 용이: 포인터만 변경하면 되므로 데이터의 이동이 필요 없습니다. (배열과의 가장 큰 차이점)
  • 단점: 포인터 저장 공간이 추가로 필요하며, 특정 노드를 찾기 위해 처음부터 차례대로 검색해야 하므로 접근 속도가 느립니다.
• 종류: 단일 연결 리스트, 이중 연결 리스트, 환형(원형) 연결 리스트.

---

2. 스택 (Stack)

한쪽 끝으로만 데이터의 삽입과 삭제가 이루어지는 자료구조입니다.

• 운영 방식: LIFO (Last-In, First-Out, 후입선출) - 가장 나중에 들어온 데이터가 가장 먼저 나갑니다.
• 용어:
  • PUSH: 데이터를 넣는 연산.
  • POP: 데이터를 꺼내는 연산.
  • TOP: 데이터가 삽입/삭제되는 지점.
• 활용 사례 (★필기 단골):
  • 함수 호출의 복귀 주소(Return Address) 저장.
  • 재귀(Recursive) 호출 관리.
  • 역순 문자열 만들기.
  • 후위 표기법(Postfix Notation) 연산.
  • 깊이 우선 탐색(DFS).

---

3. 큐 (Queue)

한쪽에서는 삽입, 다른 한쪽에서는 삭제가 이루어지는 자료구조입니다.

• 운영 방식: FIFO (First-In, First-Out, 선입선출) - 가장 먼저 들어온 데이터가 가장 먼저 나갑니다.
• 용어:
  • ENQUEUE: 데이터를 넣는 연산 (Rear/Tail에서 발생).
  • DEQUEUE: 데이터를 꺼내는 연산 (Front/Head에서 발생).
• 활용 사례:
  • 운영체제의 작업 스케줄링(FCSF).
  • 프린터 스풀(Spool) 관리.
  • 너비 우선 탐색(BFS).
• 데크(Deque): 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐의 변형 구조.

---

4. 트리 (Tree)

계층형 구조를 표현하는 비선형 자료구조입니다.

• 용어:
  • 노드(Node): 트리의 구성 요소.
  • 루트(Root): 부모가 없는 최상위 노드.
  • 리프(Leaf/Terminal): 자식이 없는 단말 노드.
  • 차수(Degree): 특정 노드의 자식 수 (트리의 차수는 노드 중 최대 차수).
• 이진 트리 순회 방식 (★무조건 출제):
  1. 전위 순회(Pre-order): Root → Left → Right
  2. 중위 순회(In-order): Left → Root → Right
  3. 후위 순회(Post-order): Left → Right → Root
• 이진 탐색 트리(BST): 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 트리.

---

필기 시험 핵심 요약

1. LIFO는 스택, FIFO는 큐임을 절대 헷갈리지 마세요.
2. 스택의 활용 문제에서 '복귀 주소', '재귀 호출' 단어가 나오면 스택이 정답입니다.
3. 트리 순회 문제는 실제 트리를 주고 "전위 순회 결과를 고르시오"와 같은 형태로 나옵니다. (루트의 위치만 잘 파악하면 쉽습니다.)
4. 배열 vs 연결 리스트: 삽입/삭제가 빈번하면 연결 리스트, 특정 인덱스 접근이 중요하면 배열이 유리합니다.