Cのリンクリストで単一のノードのみを解放するにはどうすればよいですか?

c
Cのリンクリストで単一のノードのみを解放するにはどうすればよいですか?

リンクリストで単一のノードのみを解放するにはどうすればよいですか? 以下はリンクリスト全体を解放しますが、リンクリスト内のノードを1つだけ解放したかったのです。

//Here's my code for delete

while(headPtr!=NULL)
{
    temp = headPtr;
    headPtr = headPtr->next;
    if(strcmp(temp->fname, stdfname) ==0 &&
       strcmp(temp->sname, stdsname) ==0  )
    {
        free(temp);
    }
}

  0  1


ベストアンサー

最初に前のノードを知る必要があります。 そのため、削除するノードに到達するまで繰り返す必要があります。 そのプロセスでは、前のノードを覚えておく必要があります。 次に、前のノードと次のノードを接続する必要があるため、削除するノードを「リンク解除」します。

currentNode = headNode;
previousNode = NULL;
while (currentNode != NULL) {
    if (currentNode != nodeToDelete) {
        // Not the node we want to delete yet,
        // go on to next node.
        previousNode = currentNode;
        currentNode = currentNode->next;
        continue;
    }

    // We've now hit the node to delete and know the
    // previous node. Fix the structure.
    if (previousNode) {
        previousNode->next = nodeToDelete->next;
    } else {
        // No previous node means it's the head node.
        headNode = nodeToDelete->next;
    }

    // The node is now delinked from list. Delete it.
    free(nodeToDelete);
    // Stop the loop.
    break;
}

これはパフォーマンス上かなり悪いので、二重リンクリストがあるのはこのためです。 そこでは、操作全体は次のようになります。

if (nodeToDelete->previous) {
    nodeToDelete->previous->next = nodeToDelete->next;
}
if (nodeToDelete->next) {
    nodeToDelete->next->previous = nodeToDelete->previous;
}
if (nodeToDelete == headNode) {
    headNode = nodeToDelete->next;
}
free(nodeToDelete);

ご覧のように、各ノードはその前のノードと次のノードを知っているため、ここでは繰り返しは必要ありません。

ところで、これらのことを解決するには(かなり基本的です)、紙に短いリンクリストを描画すると役立ちます。 ボックスを描画し、各ボックスにメンバー名(「前へ」や「次へ」など)を書き込み、これらのメンバーから対応する他のボックスに線を引きます。 次に、ノードを削除するために必要なことを考えます。 これがどのように機能するかを理解するのに本当に役立ちます。

1


削除するノードがヘッドでない限り、リストのヘッドは変更されません。 一時ポインタをリストの下に移動する必要があります。 また、ノードを削除するときにリンクを修正する必要があります。注意する必要があるのは3つの場合と、最初のノードである場合に特別な処理が必要なことに注意してください。 コードのスケルトンを提供しますが、リストが単一リンクか二重リンクかがわからないので、ポインターの更新はそのままにします。

temp = headPtr;
prev = NULL;
while (temp != NULL)
{
     if (strcmp(temp->fname, stdfname) == 0)
         && strcmp(temp->sname, stdsname) == 0)
     {
         if (prev == NULL) { // head node
            ...
         }
         else if (temp->next == NULL) { // tail node
            ...
         }
         else {  // interior node
            ...
         }
         break;  // stop when done
     }
     prev = temp;
     temp = temp->next;
}

0


タイトルとURLをコピーしました