데이터: 처리의 대상이 되는 모든 것
↑
데이터 타입: 데이터의 집합(ex. Integer, Double…)
↓
추상적으로 정의
↓
추상 데이터 타입(abstract data type: ADT) - information hiding
↓
프로그래밍 언어로 구현
↓
자료구조(data structure)

  • 선형 자료 구조(Linear data structure): 리스트, 스택, 큐, 덱 등
  • 계층적인 구조(Hierarchical structure): 트리, 히프, 그래프 등

리스트(List)

배열로 구현된 리스트?
메모리 안에 순차적으로 공간이 할당 (고정 크기) → 구현은 쉽지만, 삽입·삭제시 오버헤드가 따른다.

연결 리스트?
동적으로 크기가 변할 수 있고, 삽입·삭제 시 데이터를 이동할 필요가 없다. 배열과는 다르게 노드는 메모리상의 어떤 곳에나 위치할 수 있다.

  • 단순 연결 리스트(Singly linked list): 하나의 방향으로 연결된 리스트로, 마지막 노드의 링크 필드는 null이다.
  • 원형 연결 리스트(Circular linked list): 하나의 방향으로 연결된 리스트로, 마지막 노드의 링크 필드는 첫 번째 노드를 가리킨다.
  • 이중 연결 리스트(Doubly linked list): 양방향으로 연결된 리스트로, 각 노드에 링크 필드가 2개씩 존재한다.

스택(Stack)

후입선출(LIFO: Last-In First-Out)
ADT 구현 방법: 배열, 연결 리스트

활용 예

  1. Editor에서 되돌리기(undo) 기능
  2. 함수 호출에서 복귀주소 기억 (운영체제만 사용하는 시스템 스택)
  3. 중위 표기법에서 후위 표기법으로 변환, 후위 표기 수식의 계산
  4. 미로 탐색: 가장 가까운 경로가 쉽게 추출되는 자료구조 이용 (시행착오 방법)

ps. 스택이 가득 차면? Stack Overflow!

큐(Queue)

선입선출(FIFO: First-In Frist-Out)
ADT 구현 방법: 배열(선형큐 / 원형큐), 연결 리스트

활용 예

  1. 실제 상황 시뮬레이션 (ex. 은행 대기역, 데이터 패킷 모델링)
  2. CPU와 주변 기기 사이의 속도 차이 조율 (ex. 인쇄 작업 큐)
  3. 버퍼(Buffer) 역할: 서로 다른 속도로 실행되는 두 프로세서 간의 상호 작용을 조화

이진 트리(Binary Tree)

모든 노드가 2개의 서브트리를 가지고 있는 트리 (공집합도 가능)

  • 포화 이진 트리(Full binary tree): 각 레벨에 노드가 꽉 차야한다.
  • 완전 이진 트리(Complete binary tree): 마지막 레벨에 노드가 꽉 차지 않아도 되지만, 중간에 비면 안된다.
  • 기타 이진 트리

순회?
전위 순회(Preorder traversal): VLR
중위 순회(Inorder traversal): LVR
후위 순회(Postorder traversal): LRV

함수 호출을 하는 순환 구조로 작성(스택 이용): 비효율적 → 스레드 이진 트리(Threaded binary tree): 단말노드의 오른쪽 null 링크에 중위 후속자를 저장시켜 놓은 것

이진 탐색 트리(Binary Search Tree)

모든 노드의 키는 유일하다. 왼쪽 서브트리의 키는 루트의 키보다 작고, 오른쪽 서브트리의 키는 루트의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 탐색 트리이다.

  • 탐색 알고리즘: 순환적, 반복적(효율성 ↑)
  • 삽입 알고리즘: 탐색 → 끝난 지점에 추가
  • 삭제 알고리즘: 단말노드 → 삭제, 1개의 서브트리 → 삭제후 이동, 2개의 서브트리 → 삭제 후 왼쪽 서브트리의 제일 큰 값과 오른쪽 서브트리의 제일 작은 값 중 하나를 이동

우선순위 큐(Priority Queue)

우선순위가 높은 데이터가 먼저 나간다. 데이터의 우선순위에 따라서 스택이 될 수도 있고 큐가 될 수도 있다.

히프(Heap)?
배열로 구현: 노드에 번호 → 배열의 인덱스
최대 히프(Max heap): 부모 키 > 자식 키
최소 히프(Min heap): 부모 키 < 자식 키

  • 삽입: 노드를 맨 마지막에 삽입 → 부모랑 비교하면서 교환
  • 삭제: 루트 노드 삭제 → 마지막 노드를 루트로 → 자식과 비교하면서 교환