63

最近のSlashdot のインタビューで、Linus Torvalds は、一部の人々がポインターを正しく使用する方法を本当に理解していないことを示す方法で使用する例を示しました。

残念ながら、私は彼が話している人の 1 人であるため、彼の例も理解できませんでした。

「前の」エントリを追跡して単一リンクリストエントリを削除し、次のようなことをしてエントリを削除する人が多すぎるのを見てきました

if (prev)
    prev->next = entry->next;
else
    list_head = entry->next;

そして、そのようなコードを見るたびに、「この人はポインターを理解していません」と言います。そして悲しいことに、それは非常に一般的です。ポインターを理解している人は、「エントリ ポインターへのポインター」を使用し、それを list_head のアドレスで初期化します。そして、リストをトラバースするときに、次のようにするだけで、条件を使用せずにエントリを削除できます。

*pp = entry->next

このアプローチが優れている理由と、条件文なしでどのように機能するかについて、誰かがもう少し説明できますか?

4

8 に答える 8

43

最初に、あなたはします

pp = &list_head;

そして、リストをトラバースすると、この「カーソル」を次のように進めます。

pp = &(*pp)->next;

このようにして、「あなたがどこから来たのか」を常に追跡し、そこにあるポインタを変更することができます。

したがって、削除するエントリを見つけたら、次のことを実行できます。

*pp = entry->next

このようにして、AfaqNULLが別の回答で言及している3つのケースすべてを処理し、のチェックを効果的に排除しprevます。

于 2012-10-16T12:44:37.597 に答える
12

ノードが削除されると、リストを再接続する方が興味深いです。少なくとも3つのケースを考えてみましょう。

1.ノードを最初から削除します。

2.ノードを中央から削除します。

3.ノードを最後から削除します。

最初から削除する

リストの先頭にあるノードを削除する場合、最初のノードには先行するノードがないため、実行するノードの再リンクはありません。たとえば、次のノードを削除します。

link
 |
 v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------

ただし、リストの先頭へのポインタを修正する必要があります。

link
 |
 +-------------+
               |
               v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------

真ん中から外す

途中からノードを削除するには、前のノードが削除されるノードをスキップする必要があります。たとえば、bでノードを削除します。

link
 |
 v
---------     ---------     ---------
| a | --+--+  | b | --+---> | c | 0 |
---------  |  ---------     ---------
           |                ^
           +----------------+

これは、削除するノードの前にノードを参照する方法が必要であることを意味します。

最後から削除

末尾からノードを削除するには、前のノードがリストの新しい末尾になる必要があります（つまり、その後のノードを指さない）。たとえば、cでノードを削除します。

link
 |
 v
---------     ---------     ---------
| a | --+---> | b | 0 |     | c | 0 |
---------     ---------     ---------

最後の2つのケース（中央と最後）は、「削除するノードの前のノードは、削除するノードが指定する場所を指している必要があります」と言うことで組み合わせることができることに注意してください。

于 2012-10-16T14:16:56.310 に答える
6

最初のアプローチでは、リストからノードのリンクを解除してノードを削除します。

2 番目の方法では、削除するノードを次のノードに置き換えます。

どうやら、2 番目のアプローチはコードを洗練された方法で単純化します。間違いなく、2 番目のアプローチでは、連結リストと基礎となる計算モデルをよりよく理解する必要があります。

注：これは非常に関連性がありますが、コーディングに関する質問とは少し異なります。理解度をテストするのに適しています: https://leetcode.com/problems/delete-node-in-a-linked-list/

于 2016-05-20T03:35:43.453 に答える
3

私はダミー ノード アプローチ、レイアウトの例を好みます。

|Dummy|->|node1|->|node2|->|node3|->|node4|->|node5|->NULL
                     ^        ^
                     |        |
                    curr   curr->next // << toDel

次に、削除するノードにトラバースします (toDel = curr>next)

tmp = curr->next;
curr->next = curr->next->next;
free(tmp);

そうすれば、最初の要素は常にダミーであり、削除されることはないため、最初の要素かどうかを確認する必要はありません。

于 2012-10-16T13:22:43.287 に答える