[Index] 자료구조 목차 정리

자료구조 목차 정리 페이지다. 아래 표에서 이름에 링크가 걸린 자료구조는 상세 설명과 구현 코드를 쓴 글로 넘어간다. 지금 글이 있는 것은 배열과 동적 배열 둘뿐이고, 링크가 없는 줄은 아직 쓰지 않은 글이다. 설명 칸에 나오는 O(1) · O(log n) 같은 표기는 빅오 표기이고, 입력이 커질 때 시간이 얼마나 늘어나는지를 나타낸다.

자료구조

선형 자료구조 (Linear Data Structures)

값을 한 줄로 늘어놓는 자료구조다. 여기서는 값들이 메모리에 빈틈없이 붙어 있는 배열 계열을 묶었다. 같은 한 줄이라도 칸끼리 위치를 적어 이어 붙이는 쪽은 아래 「연결 자료구조」에 따로 묶었다.

자료구조 이름	설명
배열 (Array)	고정 길이 연속 메모리 블록(칸들이 메모리에 빈틈없이 붙어 있는 한 덩어리). 인덱스로 O(1) 접근.
동적 배열 (Dynamic Array)	가변 길이 배열. 미리 잡아 둔 칸 수(용량)가 다 차면 더 큰 배열을 새로 잡아 옮기는 리사이즈를 한다. 자바의 ArrayList 가 이것이다.

연결 자료구조 (Linked Data Structures)

값 하나하나(노드)가 다음 노드의 위치를 들고 줄줄이 이어진 연결 리스트 계열이다. 메모리에 붙어 있을 필요가 없다는 점이 위의 배열 계열과 다르다. 아래 「포인터」는 다음 노드를 가리키는 위치 정보를 말하고, 자바에서는 객체를 담은 변수(참조)가 이 자리다(포인터).

자료구조 이름	설명
단일 연결 리스트 (Singly Linked List)	한 방향 포인터로 노드 연결. 각 노드가 다음 노드만 가리킨다.
이중 연결 리스트 (Doubly Linked List)	각 노드가 다음 노드와 이전 노드를 둘 다 가리켜서 앞으로도 뒤로도 따라갈 수 있다.
원형 연결 리스트 (Circular Linked List)	마지막 노드가 첫 노드를 가리키는 순환 구조.

스택

자료구조 이름	설명
스택 (Stack)	LIFO(Last In First Out, 나중에 넣은 것을 먼저 꺼냄) 구조. 메서드를 부를 때마다 호출 기록을 쌓고 끝나면 위에서부터 걷어 내는 호출 스택, 여는 괄호를 쌓아 두었다가 닫는 괄호가 나오면 짝을 맞춰 꺼내는 괄호 짝 검사 등에 사용.

큐

자료구조 이름	설명
큐 (Queue)	FIFO(First In First Out, 먼저 넣은 것을 먼저 꺼냄) 구조. 먼저 들어온 작업부터 차례로 처리하는 작업 대기열에 사용.
덱 (Deque)	양쪽에서 삽입/삭제가 가능한 큐.
우선순위 큐 (Priority Queue)	넣은 순서가 아니라 우선순위 기준으로 꺼내는 큐. 아래 「힙」 섹션의 힙 자료구조로 구현.

트리 (Tree)

한 점(루트)에서 아래로 가지가 갈라지는 모양의 자료구조다. 점 하나를 노드, 한 노드 바로 아래에 달린 노드를 자식이라 한다. 자세한 뜻은 트리에 있다.

자료구조 이름	설명
이진 트리 (Binary Tree)	각 노드가 최대 두 자식.
이진 탐색 트리 (BST)	어느 노드에서 보든 왼쪽 아래 값 < 그 노드 값 < 오른쪽 아래 값인 정렬 성질을 가진 이진 트리.
AVL 트리 / 레드-블랙 트리	자가 균형 BST로 찾기 · 넣기 · 빼기를 최악의 경우에도 O(log n)에 보장.
세그먼트 트리 (Segment Tree)	배열의 구간(예: 3번째~7번째 칸) 값을 묻는 질의와 값 업데이트용 트리.
펜윅 트리 (Fenwick / BIT)	누적 합(배열 앞에서부터 어느 칸까지의 합)을 O(log n)으로 처리.
B-트리 / B+트리	메모리보다 느린 디스크에 데이터를 두는 데이터베이스에 적합한 균형 트리. 한 노드에 키를 많이 담아 트리가 납작하니, 값 하나를 찾는 동안 디스크를 읽는 횟수가 적다.
힙 트리 (Heap Tree)	완전 이진 트리로, 부모가 자식보다 항상 작거나(최소 힙) 항상 큰(최대 힙) 속성을 유지. 아래 「힙」 섹션과 같은 자료구조이고, 트리 모양이라 여기에도 적었다.

그래프 (Graph)

점(노드, 정점)과 점을 잇는 선(간선)으로 관계를 나타내는 자료구조다. 자세한 뜻은 그래프에 있다. 아래 표의 앞 두 줄은 그래프를 메모리에 담는 방법이고, 뒤 두 줄은 그래프의 종류다.

자료구조 이름	설명
인접 리스트 (Adjacency List)	노드 수에 비해 간선이 적은 희소 그래프 표현에 적합.
인접 행렬 (Adjacency Matrix)	간선이 많은 조밀 그래프나, 두 노드 사이에 간선이 있는지 빠른 확인에 적합.
방향/무방향 그래프	간선의 방향성 여부에 따른 구분. 방향 그래프의 간선 A→B는 A에서 B로만 갈 수 있고, 무방향 그래프의 간선은 양쪽으로 다 갈 수 있다.
가중 그래프	간선에 가중치(거리 · 비용 같은 숫자)가 있는 그래프.

힙 (Heap)

위 트리 표의 「힙 트리」와 같은 힙 자료구조다. JVM의 메모리 영역인 힙과는 이름만 같다.

자료구조 이름	설명
최소 힙 / 최대 힙	루트가 트리 전체에서 최소/최대값임을 보장. 우선순위 큐 구현.
피보나치 힙	두 힙을 하나로 합치는 연산을 효율화한 힙.

해시 기반 자료구조 (Hash-based Data Structures)

자료구조 이름	설명
해시 테이블	키를 숫자로 바꾸는 해시 함수를 이용한 평균 O(1) 탐색. 서로 다른 키가 같은 칸에 몰리면(해시 충돌) 느려질 수 있어 「평균」이다.
체이닝 (Chaining)	해시 충돌 시 연결 리스트로 버킷(해시 테이블의 칸) 관리. 자료구조라기보다 해시 테이블이 충돌을 처리하는 방법이다.
개방 주소법 (Open Addressing)	충돌 시 정해진 순서로 다른 버킷을 차례로 들여다보는 탐사로 빈 버킷을 찾는 방식. 이것도 충돌 처리 방법이다.

집합 및 맵 (Set & Map)

자료구조 이름	설명
HashSet / HashMap	해시 기반 집합/맵. 평균 O(1) 연산.
TreeSet / TreeMap	균형 BST 기반. 키 크기 순으로 정렬된 상태를 유지, O(log n) 연산.
Ordered Map	삽입 순서를 보존하는 맵 구현. 자바에서는 LinkedHashMap 이 기본으로 삽입 순서를 지킨다.

특수 목적 자료구조 (Specialized Data Structures)

자료구조 이름	설명
트라이 (Trie)	문자열 접두사 검색(예: 「app」으로 시작하는 단어 찾기)에 최적화된 트리.
유니온-파인드 (Disjoint Set)	집합 합치기(union)와 어떤 원소가 속한 집합 찾기(find) 연산을 거의 O(1)에 처리. 정확히는 O(1)보다 아주 조금 크지만, 실제로 다루는 어떤 크기에서도 상수처럼 작아서 「거의」다.
블룸 필터 (Bloom Filter)	확률적 집합 판단(「아마 있다」 또는 「확실히 없다」로 답함). 오탐 가능, 누락 없음 — 「아마 있다」는 틀릴 수 있지만(오탐) 「확실히 없다」는 틀리지 않는다(넣은 값을 빠뜨리는 누락이 없다).

---

자신만의 철학을 만들어가는 중입니다.

---

최상단으로 이동했습니다!