연결 목록의 삽입과 삭제

연결 목록의 변경은 값을 밀지 않지만 참조를 한 번 잘못 대입하면 뒤쪽 체인 전체를 잃습니다.

변경 전 이전 노드, 제거할 노드, 다음 노드를 지역 변수에 보존해야 합니다.

head가 바뀌는 인덱스 0은 이전 노드가 없으므로 별도 분기로 다룹니다.

successor를 보존하지 않은 중간 삽입

A와 C 사이에 B를 넣으면서 이전 노드의 next만 바꿉니다.

출력에서 C가 사라졌습니다.

새 Node가 기존 다음 노드를 먼저 가리키지 않았기 때문입니다.

lab/LinkedInsertionDisconnectBug.java

public final class LinkedInsertionDisconnectBug {
    public static void main(String[] args) {
        Node first = new Node("A");
        first.next = new Node("C");
        Node inserted = new Node("B");
        first.next = inserted;
        System.out.println(first.value + "->" + first.next.value + "->" + first.next.next);
    }

    private static final class Node {
        String value;
        Node next;

        Node(String value) {
            this.value = value;
        }
    }
}

관찰 결과

A->B->null

대입 순서는 새 노드의 next에 이전 노드의 next를 넣는 것이 먼저이고, 이전 노드의 next에 새 노드를 넣는 것이 다음입니다.

삭제도 이전 노드의 next를 제거할 노드의 next로 우회 연결한 뒤 제거한 노드의 참조를 끊어야 진단이 쉽습니다.

head와 predecessor 경로 구분

인덱스 0 삽입은 새 Node의 next를 기존 head로 둔 뒤 head를 교체합니다.
중간 삽입은 이전 Node를 찾아 기존 다음 노드를 새 Node에 먼저 보존합니다.
인덱스 0 삭제는 제거할 head를 저장한 다음 head를 제거할 노드의 next로 바꿉니다.
중간 삭제는 이전 노드의 next를 제거할 노드의 next로 연결해 나머지 체인을 유지합니다.
제거한 Node의 next를 null로 비우면 디버깅에서 소유권 종료가 명확해집니다.
모든 성공 변경은 size를 정확히 한 번 조정하고 실패 경로에서는 건드리지 않습니다.

add·remove의 대입 순서

SinglyLinkedListMutation은 add와 remove에서 head 변경을 명시합니다.

중간 경로는 index-1 Node를 찾아 한 번의 연결 대입으로 다음 노드를 보존합니다.

제거값을 반환해 호출자가 어떤 항목이 빠졌는지도 확인할 수 있습니다.

src/SinglyLinkedListMutation.java

public final class SinglyLinkedListMutation {
    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<>();
        list.add(0, "A");
        list.add(1, "C");
        list.add(1, "B");
        System.out.println(list.remove(1));
        System.out.println(list.get(1));
    }

    private static final class MyLinkedList<E> {
        private Node<E> head;
        private int size;

        void add(int index, E value) {
            checkAdd(index);
            if (index == 0) head = new Node<>(value, head);
            else {
                Node<E> prev = node(index - 1);
                prev.next = new Node<>(value, prev.next);
            }
            size++;
        }

        E remove(int index) {
            check(index);
            Node<E> removed;
            if (index == 0) {
                removed = head;
                head = head.next;
            } else {
                Node<E> prev = node(index - 1);
                removed = prev.next;
                prev.next = removed.next;
            }
            removed.next = null;
            size--;
            return removed.value;
        }

        E get(int index) {
            check(index);
            return node(index).value;
        }

        private Node<E> node(int index) {
            Node<E> n = head;
            for (int i = 0; i < index; i++) {
                n = n.next;
            }
            return n;
        }

        private void check(int i) {
            if (i < 0 || i >= size) throw new IndexOutOfBoundsException(i);
        }

        private void checkAdd(int i) {
            if (i < 0 || i > size) throw new IndexOutOfBoundsException(i);
        }
    }

    private static final class Node<E> {
        final E value;
        Node<E> next;

        Node(E v, Node<E> n) {
            value = v;
            next = n;
        }
    }
}

세 위치의 개별 그림

앞 삽입에는 이전 노드가 없습니다.

새 Node가 기존 head를 next로 가리킨 뒤 head가 새 Node로 바뀝니다.

중간 삽입은 이전 노드의 next를 먼저 새 Node의 next에 보존하고, 그다음 이전 노드의 next를 새 Node로 바꿉니다.

끝 삽입도 중간 공식과 같지만 다음 노드가 null입니다.

삭제 역시 앞과 나머지를 나눕니다.

앞 삭제는 제거할 노드로 head를 보존하고 head를 제거할 노드의 next로 이동합니다.

중간 또는 끝 삭제는 이전 노드를 찾아 그 next를 제거할 노드로 보존한 뒤, 이전 노드의 next를 제거할 노드의 next로 우회합니다.

대입 순서에 따른 데이터 보존 결정

삽입에서 이전 노드의 next를 먼저 덮어쓰면 기존 다음 노드 참조를 잃습니다.

삭제에서 제거할 노드를 보존하지 않으면 반환할 값과 끊을 참조를 잃습니다.

지역 변수는 불필요한 장식이 아니라 변경 전 그래프의 필요한 간선을 잠시 보관하는 장치입니다.

제거된 Node의 next를 null로 만드는 것은 GC에 반드시 필요한 것은 아닐 수 있지만 구조 검사에 유리합니다.

제거 객체를 디버거로 봤을 때 더 이상 목록 뒤쪽을 소유하지 않는다는 사실이 분명해집니다.

위치 탐색과 재배선 비용 분리

이전 노드 참조가 이미 있으면 삽입과 삭제는 상수 개수의 대입으로 끝납니다.

그러나 List API가 index만 받으면 index-1까지 순회해야 합니다.

“LinkedList 중간 삽입 O(1)”이라는 문장은 위치 Node를 얻는 비용을 제외한 조건부 설명입니다.

size는 연결 성공 뒤 증가하고 연결 해제 뒤 감소합니다.

범위 검사 실패에서는 size나 head가 달라지지 않아야 호출자가 예외를 잡은 뒤 목록을 계속 사용할 수 있습니다.

기록 순서를 유지한 삽입·삭제

게시글 저장소에서 수정 명령을 추가할 때 내부 Node를 반환하지 않습니다.

외부에는 Entry 값만 주고, 참조 재배선은 저장소 책임으로 남깁니다.

그래야 UI나 CLI가 연결 구조에 결합되지 않습니다.

app/PostRepositoryCliCH145.java

public final class PostRepositoryCliCH145 {
    public static void main(String[] args) {
        PostRepository repository = new PostRepository();
        repository.add("link-insert", 41);
        repository.add("link-remove", 49);
        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는 Node를 노출하지 않고 숫자 index만 받습니다.

따라서 사용자 요청의 전체 비용에는 이전 노드 탐색이 포함됩니다.

삭제 결과로 Entry 값을 돌려주고 다음 목록 출력이 끊기지 않는지 확인하는 것이 재배선 회귀 기준입니다.

탐색 비용을 포함한 연결 목록 선택

질문	관찰할 값	선택 또는 조치
앞 변경이 집중되는가	`index` 0 비율	연결 목록 강점
위치를 탐색해야 하는가	node 탐색 거리	전체 비용에 포함
제거 후 참조가 남는가	제거한 노드의 `next`	명시적 단절
빈 목록 전이가 있는가	`size` 1→0	`head` `null` 확인

Node 참조를 이미 가진 상태라면 삽입과 삭제가 일정한 대입 수로 끝납니다.

인덱스만 전달받는 List API에서는 그 위치를 찾는 순회까지 비용에 포함해야 공정한 비교가 됩니다.

연습 문제

A가 C를 가리키는 두 Node 체인이 있습니다.

새 B를 사이에 넣고 순서가 A, B, C인지 검사하세요.

각 대입 직후 기존 C에 도달할 수 있어야 합니다.

정답과 해설

B.next에 기존 A.next를 먼저 저장하고 A.next를 B로 바꿉니다.

이 순서를 뒤집으면 C의 참조가 사라집니다.

exercise/LinkedSpliceIntegritySolution.java

public final class LinkedSpliceIntegritySolution {
    public static void main(String[] args) {
        Node a = new Node("A");
        Node c = new Node("C");
        a.next = c;
        Node b = new Node("B");
        b.next = a.next;
        a.next = b;
        String order = a.value + a.next.value + a.next.next.value;
        System.out.println("order=" + order + ", end=" + (a.next.next.next == null));
    }

    private static final class Node {
        private final String value;
        private Node next;

        private Node(String value) {
            this.value = value;
        }
    }
}

출력은 order=ABC, end=true입니다.

순서와 종단을 함께 검사해야 C 뒤에 뜻하지 않은 Node가 붙은 오류도 찾을 수 있습니다.

단방향 변경 검산

인덱스 0은 head 전용 분기이고 나머지는 이전 노드를 사용합니다.

삽입은 다음 노드 보존이 선행되고 삭제는 제거할 노드 보존이 선행됩니다.

변경 뒤 head부터 센 Node 수가 size와 같으면 재배선과 논리 크기가 함께 맞은 것입니다.

이 페이지의 목차