C 더블링크드 리스트

조회수 475회

더블 링크드 리스트에서의 노드 삭제에 대해서 궁금한 점이 있습니다.

소스코드)

void DLL_RemoveNode( Node** Head, Node* Remove )
{
    if ( *Head == Remove )          
    {
        *Head = Remove->NextNode;  

        if ( (*Head) != NULL )               
        (*Head)->PrevNode = NULL; 
    }
    else // 삭제할 노드가 리스트의 헤드가 아닌 경우
    {
          Node* Temp = Remove;

          if ( Remove->PrevNode != NULL )
             Remove->PrevNode->NextNode = Temp->NextNode;

          if (Remove->NextNode != NULL)
             Remove->NextNode->PrevNode = Temp->PrevNode;
    }    

    Remove->PrevNode = NULL;   
    Remove->NextNode = NULL;   
}

출처) 뇌를 자극하는 알고리즘 - 더블 링크드 리스트 파트

노드 삭제의 경우 2가지로 나누어 처리합니다.

삭제할 노드가 리스트의 헤드일 경우와 아닐 경우로 나누어집니다.

첫번째로, 삭제할 노드가 리스트의 헤드일 경우입니다.

삭제할 노드(헤드)가 가리키는 다음 노드가 존재할 경우 삭제할 노드(헤드)가 가리키는 다음 노드가 가리키는 이전 노드 포인터를 NULL로 초기화시켜줍니다.

두번째로, 삭제할 노드가 리스트의 헤드가 아닌경우입니다.

삭제할 노드가 가리키는 다음 노드가 가리키는 이전 노드 포인터를 삭제할 노드가 가리키는 이전 노드를 가리켜줍니다. 그리고, 삭제할 노드가 가리키는 이전 노드가 가리키는 다음 노트 포인터를 삭제할 노드가 가리키는 다음 노드를 가리켜줍니다.

그런 후, 삭제될 노드가 가리키는 이전 노드와 다음 노드 포인터를 NULL로 초기화 시켜줍니다.


여기서 궁금한 점이 생깁니다.

2번쨰의 단계에서 삭제할 노드가 리스트의 헤드가 아닌 경우입니다. 여기서 삭제할 노드의 이전 노드의 존재성은 확보 된 거 아닌가요 ? 삭제할 노드의 다음 노드의 존재성은 확보를 못하구요.

그래서 소스코드에서도 삭제할 노드의 다음 노드의 존재성을 체크합니다.

해당 부분 소스코드) if (Remove->NextNode != NULL)

그런데 전자의 경우는 소스코드에서는 삭제할 노드의 이전 노드가 있는지 없는지(NULL 체크)를 왜 하는건가요 ? 단순히 가독성때문인가요 ?

해당 부분 소스코드)
    if ( Remove->PrevNode != NULL )

그리고 1~2단계를 거친 후 삭제할 노드가 가리켰던 이전 노드, 다음 노드의 포인터를 NULL로 초기화 시켜줍니다. 왜 초기화 시켜주나여 ? 어쩌피 free로 정리해줄 건데 말이죠 ? 가독성의 문제인가요 ?

해당 부분 소스코드)
   Remove->PrevNode = NULL;   
   Remove->NextNode = NULL;   

Temp라는 임시변수도 왜 쓰는지 모르겠네요. 변수 스왑할때처럼 필요한 경우도 아닌 것 같은데 말이죠. 임시변수 없이 소스코드 고쳐도 정상 작동하더라구요.

  • (•́ ✖ •̀)
    알 수 없는 사용자
  • 안전한 코드를 위해서 그런 것 같은데요. 전체 로직상에서 Head가 아닌 노드의 포인터에는 NULL을 할당 할 수 없는 상황이라면 모르겠지만 강제로 외부에서 양쪽 링크 노드에 NULL을 할당할 경우를 상정한 것 같습니다. 노드의 포인터를 NULL로 초기화 시켜주는 것 또한 안전한 코드를 위해서 같은데, 함수를 호출해도 그것을 호출한 외부에서는 아직 삭제된 노드의 참조를 들고 있으니, (질문자분께서는 이 시점에서 free를 해 주실 생각이시겠지만) 그거 양쪽 모두 끊긴 노드이니 밖에서 사용하지 말라고 명확하게 표시해 주는 것 같네요. 좀 더 안전한 코드를 위해서요. doodoji 2019.4.23 22:03
  • 리스트의 특성상 줄이 지어있잖아요 ? 따라서 삭제할 노드가 헤드가 아니라 즉, 2번째 이상의 노드라는걸 의미하잖아요. 그러면 삭제할 노드 앞에 적어도 하나의 노드는 존재하니깐, RemoveNode의 PrevNode가 Null일 순 없단는걸 말하고 싶었어요. 알 수 없는 사용자 2019.4.24 00:23
  • Temp라는 변수는 왜 임시변수 느낌이 나지만 전혀 그런 것 같지 않은데, 왜 쓰는건가여 ? 없어도 바로 써도 상관없는 것 같아서요 알 수 없는 사용자 2019.4.24 00:24
  • HEAD와 TAIL빼고 노드끼리만 이어져 있다는게 보장된다면 말씀하신게 맞습니다. 다만 DLL을 사용하는 입장에서는 강제로 한 노드의 좌우 노드 중 어느쪽을 NULL로 강제 지정할 수 있어서 (상황에 따라서는 이걸 잘못된 사용이라고 볼 수도 있고, 의도적으로 (그래프처럼) 한 방향 edge 를 가지는 노드를 만드려고 한 것이라 볼 수도 있고요.) 저런 예외처리 코드를 넣은 것 같습니다. temp 사용에 대해서는 저도 마찬가지 생각입니다. 굳이 쓰지 않아도 되지 않을까 싶네요. doodoji 2019.4.24 14:25
  • 보장된게 맞군요. 원치 않은 경우까지 모두 포괄하여 처리한거라고 보면 되겠구요. Temp는 필요 없다고 봐도 되구요. 답변 정말 감사합니다 ! 알 수 없는 사용자 2019.4.24 18:28

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)