リンクされたリストの削除

Question

削除されるノードへのポインタのみが与えられている場合、リンクされたリストのノードを削除するにはどうすればよいですか？

Answer 1

質問があまりにも曖昧であり、その理由（たとえば、データ構造の実際の知識をテストするのではなく、会話を生成するなど）の可能性があります。彼らはあなたに「これは二重にリンクされたリストですか、単独でリンクされたリストですか？」と尋ねることを期待しています。それは二重にリンクされたリストである場合は、その単純な問題：それは単独リンクリストである場合は、リスト内の前のノードを見つけることができるように

curr->prev->next = curr->next; 
curr->next->prev = curr->prev; 
delete curr; 

は、あなたがヘッドノードを持っている必要があります。だから彼らはあなたがヘッドノードへのポインタを持っているかどうか尋ねることを期待しているでしょう。擬似コードは次のようになります。また

loop from head to end until test->next == curr 
test->next = curr->next; 
delete curr; 

、あなたは（ヘッドノードなし）のリストを変更することができた場合：

temp = curr->next; 
curr->data = temp->data; 
curr->next = temp->next; 
delete temp; 

Answer 2

リストヘッドを指すポインタがないと、単独リンクリストではほとんど不可能だと思います。常にリンクされたリストの先頭ポインタを持つべきです。

Answer 3

標準のリンクリストの実装では、にはがあり、削除するノードを指すノードを変更します。それを変更するには、最初にそれを見つける必要があります。リストヘッドへのポインタ、または削除される前の要素があれば、そのリストをトラバースすることで見つけることができます。そうでない場合、この問題に対する一般的な解決策はありません。

リンクされたリストの定義を変更して、削除されたノードを何らかの形で（たとえば、ブール値属性deletedで）マークし、そのようなノードをスキップするようにリストトラバーサルを変更することができます。

Answer 4

まあ、それは単なるトリックです。

to_delete = curr->next 
curr->data = to_delete->data 
curr->next = to_delete->next 
delete to_delete 

本質的にこれだけデータをコピーし、リスト内の次のノードの次のポインタ現在のノードの次のノードを削除しますcurrを仮定

は擬似コードであろう次の、与えられたアドレスです。

Answer 5

You have a pointer to that node (say, node N). Meaning, you have access on that node. 
If that node has pointer to it's front node and it's back node, then simply point the back node to the front node. And the front node to the back of your node N. 

To illustrate: 
step 1: 
---> [ node ] ---> [ node ] ---> [ node ] ---> 
<--- [ M ] <--- [ N ] <--- [ O ] <--- etc... 

step 2: 
---> [ node ] -----------------> [ node ] ---> 
<--- [ M ] <--- [node N] <--- [ O ] <--- etc... 

step 3: 
---> [ node ] -----------------> [ node ] ---> 
<--- [ M ] <----------------- [ O ] <--- etc... 

            [ node ] ---> (still points to node O) 
     (still points to node M) <--- [ N ] 

step 4: 
just point Node N to NULL 
            [ node ] ---> NULL 
          NULL <--- [ N ] 

result: 
---> [ node ] -----------------> [ node ] ---> 
<--- [ M ] <----------------- [ O ] <--- etc... 

Answer 6

これが尾でない場合は解決策があります。

単独リンクのリストの場合は、自分の隣のノードと「交換」して、代わりにそのノードを削除します。

void freeNode(Node * node) 
{ 
    Node * next = node->next; 
    if(next) 
    { 
     node->value = next->value; 
     node->next = next->next; 
     free(next); 
    } 
    // else I'm stuck! 
} 

CおよびC++の擬似ミックスの上記の並べ替え：私は

struct Node 
{ 
    T value; 
    Node * next; 
}; 

ソリューションのようなものになるだろう持っていると仮定すると、

。

私たちが持っているノードがテールであり、テールがnode-> next == NULLによって示されていると仮定すると、前のノードをテールにすることができないため、解決できません。