Page 373 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 373
a 연결 리스트에 4개의 노드가 A → B → C → D 순서대로 나열되어 있는 상태입니다. 이때
배열에 데이터가 들어 있는 순서는 A → B → C → D가 아니라 머리부터 차례대로 C → A →
D → B입니다. 이런 순서로 데이터가 배열에 저장되는 이유는 다음과 같습니다.
1. 머리 노드를 가리키는 head의 값은 노드 A가 들어 있는 인덱스 1입니다.
2. 노드 A의 커서 값은 3입니다. 다음 노드 B가 인덱스 3인 요소에 들어 있기 때문입니다.
3. 노드 B의 커서 값은 0입니다. 다음 노드 C가 인덱스 0인 요소에 들어 있기 때문입니다.
4. 노드 C의 커서 값은 2입니다. 다음 노드 D가 인덱스 2인 요소에 들어 있기 때문입니다.
5. 노드 D의 커서 값은 꼬리 노드이기 때문에 –1입니다.
b 연결 리스트의 머리에 노드 E를 삽입한 다음의 상태입니다. 인덱스가 4인 위치에 노드 E가
들어 있습니다. 바뀐 배열의 상태는 다음과 같습니다.
1. 머리 노드를 가리키는 head의 값은 노드 E가 들어 있는 인덱스의 값인 4로 바뀌었습니다.
2. 삽입한 노드 E는 다음 노드 A가 인덱스 1에 들어 있으므로 커서의 값을 1로 지정합니다.
이렇게 삽입한 노드는 물리적으로는 ‘배열의 꼬리 인덱스 위치’에 들어 있는 것 같지만 ‘연결
리스트의 꼬리’에 추가한 것이 아니라 머리에 삽입한 것입니다. 다시 말해 배열에 저장한 데
이터의 물리적인 위치(1, 2, 3번째)는 연결 리스트에 저장된 데이터의 논리적인 순서와 다릅니
다(연결 리스트 상으로 n번째 노드가 배열의 n번째 요소에 들어 있지 않습니다). 앞으로 연결 리스트의
순서와 배열의 순서를 구별하기 위해 배열의 n번째 인덱스에 들어 있는 노드를 ‘n번째 레코
드’라고 하겠습니다. 예를 들어, 그림 9-15에서 삽입한 노드 E는 4번째 레코드에 있습니다.
c 3번째 노드 B를 삭제한 다음의 상태입니다. 노드를 삭제하면 3번째 레코드가 비어 있는 상
태가 됩니다. 이때 노드 B를 삭제하면 노드 A의 다음 노드는 C로 바뀝니다. 따라서 노드 A의
커서 값도 3에서 0으로 업데이트합니다.
이렇게 삭제를 여러 번 하면 배열은 빈 레코드가 너무 많아져 효율이 떨어집니다. 즉, 비어 있
는 레코드를 효율적으로 활용해야 합니다. 지금은 1개의 레코드만 삭제했기 때문에 ‘삭제한
인덱스를 다른 변수에 넣어 관리하면 돼’라고 생각할 수도 있지만 실제로는 많은 레코드를 삭
제하기 때문에 이런 방법으로 해결하면 안 됩니다.
09•리스트 373
