Array(배열)
- 동일한 타입의 데이터들을 저장하며, 고정된 크기를 가지고 있음
- 인덱싱이 되어 있어 인덱스 번호로 데이터에 접근할 수 있음
핵심: 메모리에 연속 배치
->배열 목록, 힙, 해시 테이블, 벡터 및 행렬과 같은 기타 데이터 구조를 구축하기 위한 빌딩 블록으로 사용
->삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘에 사용
대량 데이터 처리에서 캐시 적중률이 좋아 연속 스캔이 빠름(LinkedList보다 실무에서 보통 유리)
Linked List(연결 리스트)
- 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조
- 동적인 데이터 추가/삭제에 유리
핵심: 데이터와 다음 노드 주소를 포인터로 이어 붙인 구조
- 각 요소는 Node
- 각 Node에는 key와 다음 노드를 가리키는 포인터가 포함
- 첫 번째 요소는 Head
- 마지막 요소는 Tail
종류
1. 단순 연결 리스트
- 각 노드가 다음 노드만 가리킴
2. 원형 연결 리스트
- 마지막 노드가 첫 노드를 다시 가리킴
3. 이중 연결 리스트
- 각 노드가 이전, 다음 노드를 모두 가리킴
배열 vs 연결 리스트
배열
- 고정된 크기, 연속된 메모리 할당
- 삽입, 삭제 연산이 느림
- 인덱스를 통한 직접 접근(O(1))
- 메모리 사용 낮음(포인터 사용 X)
연결 리스트
- 동적 할당, 각 노드가 개별적으로 할당
- 빠름(포인터 조정만 필요)
- 순차 접근(O(n))
- 높음(포인터 정보를 추가로 저장)
Stack(스택)
- 쌓아놓은 더미
- 후입선출(LIFO: Last-In First-Out)
주요 연산
push(x)-맨 위(top)에 원소 삽입
pop()-맨 위(top) 원소 제거 후 반환
peek()-맨 위 원소 확인
isEmpty()-비어있는지 확인
구현 방식
배열 기반(ArrayStack)
- 단순, 인덱스 접근 빠름
- 크기 제한 있음(꽉 차면 재할당 필요)
연결 리스트 기반(LinkedStack)
- 노드 단위로 push/pop
- 동적으로 크기 조절 가능
- 메모리 포인터 오버헤드 있음
-> 데이터 외에도 다음 노드(혹은 이전 노드)의 주소를 저장해야 하기 때문에 생기는 여분의 메모리 사용
Queue(큐)
- 대기 줄
- 선입선출(FIFO: First In First Out)
주요 연산
enqueue(x)-맨 뒤(rear)에 원소 추가
dequeue()-맨 앞(front)에서 원소 제거 후 반환
peek()-맨 앞 원소 확인
isEmpty()-비어있는지 확인
- 멀티스레딩에서 스레드를 관리
- 대기열 시스템
변형 큐
원형 큐(Circular Queue)
- 배열로 큐를 만들면 front/rear가 배열 끝에 닿을 수 있음
- 이를 해결하기 위해 원형 구조로 돌려 사용
우선순위 큐(Priority Queue)
- 단순 FIFO가 아니라 우선순위가 높은 데이터 먼저 처리
- 보통 힙(Heap)으로 구현
- 예: 운영체제 스케줄러
덱(Deque: Double-ended Queue)
- 앞/뒤 양쪽에서 삽입, 삭제 가능
