✍️ 내 코드가 느렸던 이유: LinkedList를 배열로 바꾸고 생긴 일

 

 

🐣 시작은 코드 비교에서

 

최근에 백준 14002번: 가장 긴 증가하는 부분 수열 5 문제를 풀다가,

다른 사람의 풀이와 내 풀이 사이에서 속도 차이가 유독 크게 나는 걸 발견했다.

로직은 같았다.

LIS(Longest Increasing Subsequence) 구하고, 실제 수열을 역추적해서 출력한다.

 

그런데 나는 이렇게 썼다:

LinkedList<Integer> result = new LinkedList<>();
while (idx != -1) {
    result.addFirst(arr[idx]);
    idx = prev[idx];
}

반면, 다른 사람의 코드는 이렇게 배열로 처리하고 있었다:

int[] result = new int[length];
int pos = length - 1;
while (idx != -1) {
    result[pos--] = arr[idx];
    idx = prev[idx];
}

🤔 코드 차이? 단순히 addFirst()냐, 배열 인덱스냐.

그런데 실행 속도는… 차원이 달랐다!

 

🔍 궁금증: 왜 이렇게 느리지?

 

처음엔 의아했다.

LinkedList.addFirst()는 O(1)인데? → 근데 왜 느릴까?

 

---

📦 자료구조 관점에서 분석해보자

 

 

1. 🧱 배열 (Array)

 

• 연속된 메모리 블록에 저장됨
• 특정 인덱스로의 접근이 O(1)
• CPU 캐시 적중률이 높음 → 속도 빠름

 

💡 고속도로처럼 달림. 배열[1000000] 해도 즉시 도착.

 

2. 🔗 LinkedList

 

• 각 노드는 값 + 다음 노드 주소를 가짐
• 메모리상에 흩어져 있음 → 접근 시 참조 따라가야 함
• 포인터 연결 때문에 GC와 메모리 관리 부하 있음

 

💡 집집마다 방문하는 택배차 느낌. 느림.

 

 

3. 💣 addFirst()의 실체

result.addFirst(value); // O(1)

이론상 O(1)이지만 현실은 다름.

 

• 객체 생성 (Node)
• 포인터 변경
• 힙에 흩어진 구조
• GC 트래킹 부담

 

💥 반복되면 캐시도 안 먹고, 참조 부하도 쌓이고, 결국 느려짐.

⚠️ 데이터가 많아질수록 차이는 기하급수적으로 커진다.

 

 

 

✅ 결론: 데이터가 많아지고 변경이 없다면 배열이 훨씬 유리

비교 항목	Array	LinkedList
메모리 구조	연속적	비연속 (포인터 기반)
접근 방식	직접 인덱싱 (빠름)	참조 따라가기 (느림)
캐시 효율	높음	낮음
GC 영향	적음	큼
대용량 데이터	강력 추천	지양

 

---

🧩 그렇다면 LinkedList는 언제 쓰는 게 좋을까?

 

앞에서는 LinkedList.addFirst() 때문에 생긴 성능 저하를 사례로 보여주며,

LinkedList의 구조적 한계에 대해 다뤘다.

 

그렇다고 해서 “LinkedList는 절대 쓰면 안 되는 자료구조야!” 라는 건 아니다.

LinkedList도 분명 배열로는 해결하기 어려운 문제들에 특화되어 있다.

---

 

🛠 LinkedList의 강점은?

1. 🧷 중간 삽입/삭제가 잦을 때

 

배열은 중간 요소를 삽입하거나 삭제할 때 모든 요소를 뒤로 밀거나 당겨야 한다.

// 배열에서 인덱스 2에 삽입
for (int i = size; i > 2; i--) {
    arr[i] = arr[i - 1]; // 뒤로 밀기
}

→ O(N) 시간 소요

→ 데이터 크고 중간 수정 많으면 치명적

 

📌 반면 LinkedList는 노드 간 연결만 바꾸면 되므로:

node.prev.next = newNode;
newNode.prev = node.prev;
newNode.next = node;
node.prev = newNode;

→ O(1) 삽입/삭제 가능

→ 즉, 중간 조작이 많을 때 유리

 

 

2. 📚 데이터 크기가 유동적일 때

배열은 고정된 크기로 할당되기 때문에, 크기 조정이 필요하면 복사 비용이 발생함.

int[] newArr = new int[arr.length * 2];
System.arraycopy(arr, 0, newArr, 0, arr.length);

반면, LinkedList는 새로운 노드를 하나하나 추가할 수 있으므로 크기 조정 비용이 없음.

 

3. 🎯 선형 탐색 기반 알고리즘에 유리할 때

 

• 예: 구현 문제에서 덱(Deque) 형태로 앞뒤로 원소를 추가/삭제해야 하는 상황
• Queue, Deque, Stack 자료구조를 직접 구현할 때

 

Java에서 LinkedList는 Deque 인터페이스도 구현하므로, 양방향 큐로서 아주 유용함:

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
deque.pollFirst(); // 1
deque.pollLast();  // 2

→ 배열로 구현하려면 ArrayDeque이 더 낫지만,

기능 구현 테스트나, 인터페이스 중심 코드에서는 LinkedList도 강점 있음

 

---

🔍 정리: LinkedList vs Array

상황추천 자료구조

요소 접근이 많다 (get(i))	배열 (Array)
중간 삽입/삭제가 많다	LinkedList
데이터 크기가 계속 변한다	LinkedList
대량의 원소 처리 (성능 중요)	배열
앞뒤로 추가/삭제만 한다	ArrayDeque or LinkedList (작은 데이터일 때는 큰 차이 없음)

 

 

 

✅ 한 줄 요약

 

배열은 읽고 쓸 때 빠르고, LinkedList는 중간에서 유연하다.

상황에 따라 쓰는 자료구조는 달라져야 한다.

 

 

🎁 마무리

 

이번 경험을 통해 하나 더 확실히 배운 건,

“자료구조는 도구다. 도구는 용도에 맞게 써야 진짜 값이 난다.” 는 점이다.

 

LinkedList는 느릴 수도 있지만, 때로는 배열로는 구현이 번거로운 문제를

간단하게 풀 수 있게 해주는 도구다. 성능만 볼 게 아니라 구현의 편의성, 요구되는 기능, 유연성까지 고려해서

적절한 자료구조를 선택하는 게 진짜 개발자의 센스라고 생각한다.