linked structures

리스트 트리 조작 기준

head, link, insert, delete, traverse의 순서로 포인터 구조의 핵심 조작을 점검합니다.

조작 순서

시작 노드를 잃지 않도록 첫 포인터를 따로 관리합니다.

각 노드가 다음 노드 주소를 갖는지 양방향 링크가 있는지 확인합니다.

새 노드의 연결을 먼저 잡은 뒤 기존 링크를 바꿉니다.

앞 노드가 삭제 대상 다음을 보게 한 뒤 메모리를 해제합니다.

트리는 루트를 언제 방문하는지로 순회 이름이 갈립니다.

구조별 판단

배열은 임의 접근이 빠르고, 리스트는 중간 삽입과 삭제가 유리합니다.

head가 null인지, 마지막 노드의 next가 null인지가 기본 조건입니다.

next와 prev를 모두 맞춰야 양쪽 이동이 깨지지 않습니다.

root, parent, child, leaf, level을 그림 위에 표시하면 조건 해석이 쉬워집니다.

전위는 root 먼저, 중위는 가운데, 후위는 마지막에 root를 방문합니다.

pointer cue

포인터 문제는 바꾸기 전 연결과 바꾼 뒤 연결을 두 줄로 그려 보며 head 손실을 먼저 막으세요.