LinkedList 내부 구조
LinkedList의 이중 연결 노드 구조와 시간 복잡도 특성을 살펴봅니다.
LinkedList 내부 구조은(는) CoddyKit의 무료 Java Academy 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Java Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
LinkedList 내부 구조
Java의 LinkedList는 이중 연결 목록입니다. 각 Node는 이전 Node와 다음 Node에 대한 참조와 요소 값을 보유합니다. ArrayList와 달리 backing array가 없으며 메모리가 Node별로 할당됩니다.
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) { this.data = data; }
}시간 복잡도 특성
LinkedList의 성능 특성은 ArrayList와 크게 다릅니다.
- addFirst / addLast: O(1)
- get(index): O(n) — 첫 Node나 마지막 Node부터 순회해야 합니다
- remove(index): 위치를 찾는 데 O(n), 연결을 해제하는 데 O(1)
- 반복자 순회: O(n)
무작위 접근이 아니라 첫 부분이나 마지막 부분에 자주 삽입해야 할 때 LinkedList를 사용합니다.
LinkedList 생성 및 순회
LinkedList를 생성하고 순회하는 방식은 이미 알고 있는 동일한 List 인터페이스를 따릅니다. 차이점은 내부 구조입니다.
import java.util.LinkedList;
LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");
for (String name : list) {
System.out.println(name);
}
System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: " + list.getLast()); // CaroladdFirst, addLast, removeFirst, removeLast
LinkedList는 ArrayList가 효율적으로 제공하지 못하는 첫 부분/마지막 부분 연산을 제공합니다.
LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10); // [10]
nums.addLast(20); // [10, 20]
nums.addFirst(5); // [5, 10, 20]
System.out.println(nums.removeFirst()); // 5 → [10, 20]
System.out.println(nums.removeLast()); // 20 → [10]Node 연결 해제: 찾은 후 O(1) 삭제
반복자를 통해 Node에 대한 참조를 얻으면 제거는 O(1)입니다. next/prev 포인터만 갱신하면 되므로 ArrayList처럼 요소를 이동할 필요가 없습니다.
import java.util.*;
LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
String t = it.next();
if (t.equals("B") || t.equals("D")) {
it.remove(); // O(1) unlink
}
}
System.out.println(tasks); // [A, C]ArrayList와 비교한 메모리 오버헤드
각 LinkedList Node는 두 개의 추가 참조(prev, next)와 요소 참조를 가지므로 64비트 JVM에서 항목 하나당 약 48바이트를 사용합니다. ArrayList는 연속 배열에 요소 참조 하나만 저장하므로 8바이트를 사용합니다.
대규모 읽기 중심 데이터셋에서는 ArrayList가 일반적으로 캐시 친화적이며 메모리도 적게 사용합니다.
덱 연산: 스택과 큐
LinkedList는 Deque 인터페이스를 구현하므로 스택과 큐 모두로 사용할 수 있습니다.
import java.util.LinkedList;
import java.util.Deque;
// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first
// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // topPriorityQueue 개요
PriorityQueue는 힙 기반 큐로, 자연 순서나 비교자에 따라 가장 작은 요소가 항상 먼저 큐에서 제거됩니다. 연결 목록을 기반으로 하지 않으며, 이진 힙 배열을 사용합니다.
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);
System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40사용자 지정 비교자를 사용하는 PriorityQueue
순서를 반전하거나 사용자 지정 필드를 기준으로 정렬하려면 Comparator를 전달합니다.
import java.util.*;
record Task(String name, int priority) {}
PriorityQueue<Task> tasks = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));
while (!tasks.isEmpty()) {
System.out.println(tasks.poll().name());
}
// High, Med, LowLinkedList와 ArrayList 중 선택하기
일반적인 선택 기준:
- 무작위 접근, 순회 및 대부분의 상황에는 ArrayList를 사용합니다.
- 양 끝에서 O(1) 삽입/제거를 자주 수행하고 인덱스 접근이 필요하지 않다면 LinkedList를 사용합니다.
- 순서에 따른 처리가 필요할 때(작업 일정 관리, 다익스트라 알고리즘) PriorityQueue를 사용합니다.
흔한 실수
LinkedList에서 반복문으로 get(i)를 호출하지 마십시오. 전체 시간 복잡도가 O(n²)이 됩니다.
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);
// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
int val = list.get(i); // slow!
}
// GOOD: O(n) — use iterator
for (int val : list) {
// process val
}빠른 확인
목록의 크기와 관계없이 O(1)인 LinkedList 연산은 무엇입니까?
복습: LinkedList와 덱
핵심 내용:
- LinkedList는 양 끝 연산이 O(1)인 이중 연결 목록입니다
- 무작위 접근(인덱스를 통한 get/set)은 O(n)입니다
- Deque를 구현하므로 스택이나 큐로 사용할 수 있습니다
- PriorityQueue는 힙 순서에 따른 처리를 제공합니다
- 대부분의 사용 사례에서는 ArrayList를 우선하고, 첫 부분/마지막 부분의 변경이 잦을 때 LinkedList를 사용합니다
자주 묻는 질문
“LinkedList 내부 구조” 강의는 무료인가요?
네 — “LinkedList 내부 구조” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Java Academy 강의 전체를 잠금 해제할 수 있습니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“LinkedList 내부 구조”에서 뭘 배우나요?
LinkedList의 이중 연결 노드 구조와 시간 복잡도 특성을 살펴봅니다. 브라우저에서 직접 실행하는 실습 코드로 Java Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Java Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Java Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“LinkedList 내부 구조” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Java Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Java Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.