자료구조? 그게 뭔데?

* 개념 복습과 학습 정도를 파악하고자 포스팅합니다!
* Claude, ChatGPT를 활용하여 이미지를 생성하고 활용합니다.

 

자료구조(Data Structure)

1. 자료구조란?

데이터를 효율적으로 저장하고 관리하는 방식.

같은 데이터라도 어떤 자료구조에 담느냐에 따라 탐색, 삽입, 삭제 속도가 크게 달라집니다!

 

자료구조별로 약간 비유를 해보자면, 

• 책을 그냥 바닥에 쌓아두는 것 - 배열
• 번호표 순서대로 줄 세우는 것 - 큐
• 탑처럼 쌓는 것 - 스택
• 나무처럼 가지 치는 것 - 트리

이렇게 되겠네요! 그래서 데이터를 담는 구조 자체가 자료구조라고 합니다.

 

뒤에 나올 내용들에 대한 코드는 모두 자바로 작성하였습니다. (주 언어를 자바로 하여 학습중)

---

2. 선형 자료구조

배열(Array)

같은 타입의 데이터를 연속된 메모리 공간에 순서대로 저장합니다. 인덱스로 즉시 접근할 수 있어요!

int[] arr = {10, 20, 30, 40, 50};

// 접근 O(1)
int x = arr[2];       // 즉시 30

// 탐색 O(n)
for (int i = 0; i < arr.length; i++) { ... }

// 삽입·삭제 O(n) — 뒤 요소를 전부 밀거나 당겨야 함

 

연결 리스트(Linked List)

각 데이터(노드)가 다음 노드의 주소를 가지고 있는 구조입니다.

메모리가 연속되지 않아도 되고 삽입 / 삭제가 빨라요!

연결리스트는 배열과 달리 메모리가 흩어져 있어도 돼요. 각 노드가 다음 노드의 주소를 들고 있어서 체인처럼 연결됩니다.

중간에 노드를 삽입하거나 삭제할 때 앞뒤 노드의 포인터만 바꾸면 되기 때문에 O(1)입니다.

단, 특정 위치에 접근하려면 Head부터 순서대로 따라가야 해서 O(n)이 됩니다.

 

스택(Stack)

나중에 넣은 것이 먼저 나오는(LIFO, Last In First Out) 구조입니다. 접시를 쌓는 것처럼 맨 위에서만 넣고 빼요.

Stack<Integer> stack = new Stack<>();

stack.push(1);   // [1]
stack.push(2);   // [1, 2]
stack.push(3);   // [1, 2, 3]

stack.pop();     // 3 꺼냄 → [1, 2]
stack.peek();    // 2 확인 (꺼내지 않음)

 

큐(Queue)

먼저 넣은 것이 먼저 나오는(FIFO) 구조에요. 줄 서기처럼 앞에서 꺼내고 뒤에서 넣습니다.

Queue<Integer> queue = new LinkedList<>();

queue.offer(1);   // [1]
queue.offer(2);   // [1, 2]
queue.offer(3);   // [1, 2, 3]

queue.poll();     // 1 꺼냄 → [2, 3]
queue.peek();     // 2 확인 (꺼내지 않음)

---

3. 비선형 자료구조

트리(Tree)

계층 구조를 표현하는 자료구조입니다. 부모-자식 관계가 있고 사이클이 없어요.

트리의 핵심 용어는 루트(최상단 노드), 부모/자식(연결된 상하 노드), 리프(자식이 없는 끝 노드), 깊이(루트에서의 거리)에요.

이진 탐색 트리(BST) 는 왼쪽 < 부모 < 오른쪽 규칙으로 정렬된 트리이고, 탐색할 때마다 절반씩 제거되므로 O(log n)입니다.

 

해시 테이블(Hash Table)

키(Key)를 해시 함수로 변환해서 인덱스를 구하고, 해당 위치에 값을 저장하는 구조에요. 평균적으로 모든 연산이 O(1)입니다!

 

그래프(Graph)

노드(정점)와 엣지(간선)로 이루어진 자료구조입니다. 트리는 그래프의 특수한 형태에요.

소셜 네트워크, 지도 최단 경로, 네트워크 연결 등에 사용됩니다!

---

4. 자료구조와 알고리즘의 연관성

제가 생각했을 때, 자료구조와 알고리즘은 정말 뗄 수 없는 관계로 보여요..!

어떤 자료구조를 선택하느냐에 따라서 사용할 수 있는 알고리즘이 결정되고 성능이 달라지니까요.

 

상황별로 사용할 수 있는 자료구조와 알고리즘을 한번 정리해보았어요!

---

마무리

실전 예시를 하나 보면서 마무리하면 좋을 것 같습니다.

 

예시 - 자료구조 선택에 따른 성능 변화

배열에서 중복 숫자를 찾아라

// 방법 1 — 배열만 사용 O(n²)
for (int i = 0; i < arr.length; i++)
    for (int j = i+1; j < arr.length; j++)
        if (arr[i] == arr[j])
            System.out.println("중복: " + arr[i]);

// 방법 2 — 해시셋 사용 O(n)
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
    if (!seen.add(num))
        System.out.println("중복: " + num);
}

 

포스팅을 하면 할수록 드는 생각인데, 깊이있는 학습과 복습이 참 중요한 것 같아요..

개발자에게 있어서 자료구조와 알고리즘은 정말 기본중의 기본이라고 들었습니다. 전 그동안 기본도 제대로 익히지 않고 무작정 개발을 했던 '패션 개발자' 였던 것 같네요..!

꾸준한 학습과 포스팅을 통해 확실하지만 그렇다고 느리게 성장하지는 않는 꾸준한 상승곡선을 그리는 개발자가 되어보겠습니다 !

이 글을 읽어주시는 모든 분들께 감사의 말씀을 올립니다.

빠르게 알고리즘글도 작성해보겠습니다 !!