linked list 연결 리스트 링크 무결성표 포인터를 바꾸기 전과 후에 head, next, prev, null 경계를 같은 기준으로 확인하면 노드를 잃는 실수를 줄일 수 있다.
빠른 확인 시간 복잡도보다 포인터를 바꾸는 순서가 먼저 틀리기 쉬운 자료구조다.
무결성 점검 기준
Head 첫 노드 변경맨 앞 삽입과 삭제는 head가 새 첫 노드를 가리키는지 먼저 확인한다.
Next 이전 노드 보존삭제나 삽입 직전의 이전 노드를 따로 들고 있어야 링크를 잇는 위치가 분명하다.
Prev 역방향 일치이중 리스트는 next와 prev 중 하나만 고치면 순회 방향마다 다른 결과가 난다.
Sentinel 예외 축소더미 노드는 빈 리스트와 첫 노드 삭제의 분기 처리를 줄인다.
Verify 왕복 순회앞에서 뒤로, 뒤에서 앞으로 본 결과가 같은지 확인하면 단절을 찾기 쉽다.
링크 순서 새 노드가 기존 다음 노드를 가리킨 뒤 이전 링크를 바꾼다. 삭제는 대상을 건너뛴 뒤 남은 참조를 정리한다.