자료구조 정리

자료구조는 한마디로 정의하면 데이터 값의 모임이다.

---

배열

배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장한다.

특징 

• 인덱스 사용
• 데이터 빠르게 접근
• 크기 고정

---

연결 리스트 (Linked List)

연결 리스트는 데이터를 노드(Node) 단위로 저장하며, 각 노드는 다음 노드의 주소를 포함한다.

특징

• 데이터 삽입과 삭제 용이
• 임의 접근 속도 느림

---

스택 (Stack)

스택은 후입선출(LIFO, Last In First Out) 방식으로 데이터를 처리한다.

특징

• push : 데이터 넣음
• pop : 데이터 꺼냄

활용 예시

• 웹 브라우저의 뒤로 가기 기능
• 함수 호출의 순서 저장

---

큐 (Queue)

큐는 선입선출(FIFO, First In First Out) 방식으로 데이터를 처리한다.

특징

• enqueue : 데이터 넣음
• dequeue : 데이터 꺼냄

활용 예시

• 은행 대기열
• 작업 스케줄링

---

데크 (Deque)

데크는 양쪽 끝에서 데이터를 넣거나 꺼낼 수 있는 자료구조다.

이미지 출처 : https://velog.io/@d101812/%EC%84%A0%ED%98%95-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%8D%B0%ED%81%AC

특징

• 큐와 스택의 기능 모두 포함
• pushFront, pushBack 등으로 데이터 삽입

활용 예시

• 캐싱 시스템
• 슬라이딩 윈도우 문제

---

해시 테이블 (Hash Table)

해시 테이블은 키-값 쌍(Key-Value Pair)으로 데이터를 저장한다. 키를 해싱(Hashing)하여 빠르게 데이터를 찾는다.

특징

• 검색, 삽입, 삭제가 평균적으로 O(1)
• 충돌(Collision) 문제를 해결해야 함

활용 예시

• DB 색인
• 캐시(Cache)

---

트리 (Tree)

트리는 계층적 구조를 가지며, 노드들로 이루어진 자료구조다.

종류

• 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식 노드를 가짐
• 이진 탐색 트리(Binary Search Tree): 정렬된 형태로 데이터를 저장
• 힙(Heap): 최대값이나 최소값을 빠르게 찾도록 설계

활용 예시

• 디렉토리 구조
• 데이터베이스의 B-Tree

---

그래프 (Graph)

그래프는 노드(정점, Vertex)와 노드 간의 연결(간선, Edge)로 이루어진 자료구조다.

이미지 출처 : https://pasted.tistory.com/15

특징

• 방향 그래프와 무방향 그래프가 있음
• 가중치 그래프(Weighted Graph)는 간선에 비용 부여

활용 예시

• 네트워크 연결
• 지도에서 최단 경로 찾기(Dijkstra 알고리즘)

---

힙 (Heap)

힙은 완전 이진 트리의 일종으로, 최대값이나 최소값을 빠르게 찾도록 설계되었다.

이미지 출처 : https://velog.io/@lky9303/%ED%9E%99heap-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0

종류

• 최대 힙 : 부모 노드가 자식 노드보다 크다
• 최소 힙 : 부모 노드가 자식 노드보다 작다

활용 예시

• Priority Queue
• 힙 정렬