단방향 연결 목록
연속 배열 없이 Node를 연결하고 head부터 getNode·getLast·add까지 참조 이동 규칙을 구현합니다.
연결 목록은 원소를 연속된 칸에 복사하지 않고 각 Node가 다음 Node의 참조를 가집니다.
그래서 i번째 값을 얻으려면 head부터 i번 next를 따라가야 합니다.
순회 코드는 현재 Node와 next 참조를 분리하며 null을 목록의 끝 표식으로 사용합니다.
null 종단을 지나친 순회가 실패하는 지점
두 노드만 있는 체인에서 세 번 이동합니다.
null이 정상 종료 표식인데도 이동 횟수를 검증하지 않아 마지막 출력에서 NullPointerException이 납니다.
public final class BrokenNodeTraversalFailure {
public static void main(String[] args) {
Node first = new Node("node", new Node("link", null));
Node current = first;
for (int i = 0; i <= 2; i++) {
current = current.next;
}
System.out.println(current.value);
}
private record Node(String value, Node next) {}
}java.lang.NullPointerException배열의 length처럼 자동으로 알려 주는 구분이 없습니다.
목록이 size를 관리하고 getNode(index)가 유효 범위를 검사해야 합니다.
순회는 current를 한 칸씩 바꾸되 원래 head 참조를 잃지 않아야 합니다.
head·current·next의 역할 분리
Node는 현재 값과 다음Node참조를 묶어 한 연결 단위를 표현합니다.head는 첫 원소를 가리키며 빈 목록에서는null이라는 상태를 명시합니다.- getNode는
head에서 출발해 정확히index번next를 따라가므로 O(n)입니다. getLast는current.next가null인 노드를 반환하고current가null인 경우를 먼저 처리합니다.- 끝 추가는 마지막
Node의next를 새Node로 연결하며size를 한 번만 증가시킵니다. - toString 순회는 구조를 변경하지 않고
null에 도달하면 반드시 종료해야 합니다.
getNode·add 기반 단방향 체인
LinkedNodeWalk는 head를 고정하고 current라는 지역 참조만 이동합니다.
add는 빈 목록과 기존 목록을 분리하고, get은 경계 검사를 통과한 뒤 getNode를 호출합니다.
size가 구조와 어긋나지 않도록 연결 성공 뒤 한 번 증가시킵니다.
public final class LinkedNodeWalk {
public static void main(String[] args) {
NodeChain chain = new NodeChain();
chain.add("node");
chain.add("next");
chain.add("head");
System.out.println(chain.get(1));
System.out.println(chain);
}
private static final class NodeChain {
private Node head;
private int size;
void add(String value) {
Node added = new Node(value);
if (head == null) head = added;
else getNode(size - 1).next = added;
size++;
}
String get(int index) {
check(index);
return getNode(index).value;
}
private Node getNode(int index) {
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current;
}
private void check(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
}
public String toString() {
StringBuilder out = new StringBuilder("[");
for (Node current = head; current != null; current = current.next) {
if (out.length() > 1) out.append(", ");
out.append(current.value);
}
return out.append(']').toString();
}
}
private static final class Node {
String value;
Node next;
Node(String value) {
this.value = value;
}
}
}head 보존과 current 이동
head는 목록의 영구 시작점입니다.
조회를 위해 head 자체를 다음 Node로 바꾸면 앞부분을 다시 찾을 방법이 없습니다.
순회에는 지역 변수 current를 만들고 current = current.next만 반복합니다.
순회가 끝나도 head가 첫 Node를 가리켜야 합니다.
인덱스 0의 Node는 head이고 인덱스 i의 Node는 next를 i번 따라간 결과입니다.
따라서 연결 목록 get의 비용은 위치에 비례합니다.
마지막 원소 조회를 반복하는 코드가 있다면 각 호출마다 전체 체인을 걷는다는 점을 놓치지 않습니다.
null 종단 표식
빈 목록은 head가 null이고 마지막 Node의 next도 null입니다.
두 의미를 문맥으로 구분합니다.
toString은 current가 null이 되면 종료하고, getNode는 사전에 index를 검사했기 때문에 순회 중 null을 만나지 않아야 합니다.
size와 실제 Node 수가 어긋나면 경계 검사를 통과했는데 current가 null이 되는 내부 결함이 발생합니다.
add에서 연결이 성공한 뒤 size를 늘리고 remove에서 연결을 바꾼 뒤 줄이는 순서를 지키는 이유입니다.
getLast와 끝 추가의 비용
꼬리 노드 필드가 없는 첫 구현의 getLast는 head부터 next가 null인 Node까지 이동합니다.
끝 추가 한 번은 O(n)이며 n개를 연달아 넣으면 전체 순회가 커집니다.
이 버전은 연결 원리를 드러내는 데는 좋지만 대량 끝 추가의 최종 설계는 아닙니다.
순환 참조가 생기면 null에 도달하지 못하므로 toString도 끝나지 않습니다.
직접 구현을 확장할 때는 방문 Node 수가 size를 넘는지 진단하거나 Floyd 순환 탐지 같은 별도 검사를 고려할 수 있습니다.
연결 순서 출력
CLI 결과는 여전히 입력 순서와 합계를 보여 줍니다.
연결 저장소로 바꾸더라도 사용자는 next나 head를 알 필요가 없습니다.
이 분리는 자료 구조 내부 참조와 애플리케이션 명령을 섞지 않게 합니다.
public final class PostRepositoryCliCH144 {
public static void main(String[] args) {
PostRepository repository = new PostRepository();
repository.add("node-chain", 38);
repository.add("linear-walk", 47);
repository.print();
System.out.println("total=" + repository.totalViewCount());
}
private static final class PostRepository {
private Entry[] entries = new Entry[2];
private int size;
void add(String title, int viewCount) {
if (title == null || title.isBlank()) throw new IllegalArgumentException("title");
if (viewCount <= 0) throw new IllegalArgumentException("viewCount");
ensureCapacity(size + 1);
entries[size++] = new Entry(title, viewCount);
}
private void ensureCapacity(int required) {
if (required <= entries.length) return;
Entry[] grown = new Entry[Math.max(required, entries.length * 2)];
System.arraycopy(entries, 0, grown, 0, size);
entries = grown;
}
int totalViewCount() {
int total = 0;
for (int i = 0; i < size; i++) {
total += entries[i].viewCount();
}
return total;
}
void print() {
for (int i = 0; i < size; i++) {
Entry entry = entries[i];
System.out.println(i + ":" + entry.title() + "=" + entry.viewCount());
}
}
}
private record Entry(String title, int viewCount) {}
}이 CLI는 배열을 사용하지만 출력 규칙은 연결 목록에서도 그대로 적용됩니다.
연결 저장소를 실험할 때 head부터 방문한 Entry 수가 size와 같고 마지막 next가 null인지 먼저 검사합니다.
합계 계산은 모든 Node를 정확히 한 번 방문해야 85를 냅니다.
단방향 연결이 유리한 연산
| 질문 | 관찰할 값 | 선택 또는 조치 |
|---|---|---|
| 임의 조회가 많은가 | 평균 index | 배열 목록 우선 |
| 끝 참조를 저장하는가 | 끝 추가 횟수 | 꼬리 노드 필드 검토 |
| 노드 오버헤드가 허용되는가 | 원소당 참조 수 | 메모리 측정 |
| 순회 중 변경하는가 | 구조 수정 횟수 | 반복자 정책 필요 |
연결 목록은 “삽입 O(1)”로만 선택할 수 없습니다.
삽입 위치의 Node를 찾는 시간이 포함되면 전체가 O(n)입니다.
이미 Node 참조를 가진 알고리즘인지, 임의 조회가 필요한지 먼저 묻습니다.
연습 문제
세 Node를 직접 연결하고 head부터 순회해 개수와 마지막 값을 출력하세요.
head가 null인 입력도 처리할 수 있는 메서드로 분리합니다.
정답과 해설
current를 이동하기 전에 last를 갱신하면 반복 종료 뒤 마지막 방문 값을 보존할 수 있습니다.
빈 체인의 last는 null로 남습니다.
public final class NodeChainSummarySolution {
public static void main(String[] args) {
Node head = new Node("node", new Node("next", new Node("end", null)));
Summary result = summarize(head);
System.out.println("count=" + result.count() + ", last=" + result.last());
}
private static Summary summarize(Node head) {
int count = 0;
String last = null;
for (Node current = head; current != null; current = current.next()) {
count++;
last = current.value();
}
return new Summary(count, last);
}
private record Node(String value, Node next) {}
private record Summary(int count, String last) {}
}결과는 count=3, last=end입니다.
summarize는 head를 재대입하지 않아 호출자의 체인을 손상하지 않습니다.
단방향 순회 종료 기준
빈 목록의 head는 null, 비어 있지 않은 목록의 마지막 next도 null입니다.
getNode(i)는 i번만 이동하고 공개 get이 먼저 범위를 검사합니다.
구조를 읽는 메서드가 head나 next를 변경하지 않는지 확인하면 단방향 순회의 기반이 닫힙니다.