linked list

연결 리스트 링크 무결성표

단일/이중 연결 리스트에서 노드를 잃지 않도록 포인터 변경 전후 조건을 고정합니다.

링크 순서

첫 노드가 바뀌는 삽입과 삭제는 head 갱신을 먼저 의심합니다.

삭제·삽입 직전의 이전 노드를 따로 들고 있어야 링크를 끊거나 다시 잇는 위치가 분명합니다.

이중 리스트는 next와 prev를 같은 단계에서 맞춰야 합니다.

새 노드가 기존 다음 노드를 가리킨 뒤 이전 링크를 바꿉니다.

대상을 건너뛴 뒤 더 이상 참조하지 않도록 연결을 정리합니다.

디버깅 기준

뒤로 돌아갈 수 없으므로 삭제 대상의 이전 노드를 따로 들고 있어야 합니다.

양방향 링크 중 하나만 고치면 순회 방향에 따라 다른 버그가 납니다.

더미 노드는 빈 리스트와 첫 노드 삭제의 예외 처리를 줄입니다.

기존 링크를 먼저 덮어쓰면 남은 리스트 일부를 잃을 수 있습니다.

앞에서 뒤로, 뒤에서 앞으로 순회 결과가 같은지 확인하면 단절을 찾기 쉽습니다.

link cue

연결 리스트는 시간 복잡도보다 포인터를 바꾸는 순서가 먼저 틀리는 자료구조입니다.