二重リンクリストのスワップ関数を作成するにはどうすればよいですか？

Question

二重リンクリストのスワップ機能を作成する際に問題があります。私は単に値を変更しないでリストを "rewire"したい（これは簡単だろう）。私はback<-p->frontを保持するためにこの一時的なアイテムを作成しようとしました。これで、q =をこの前後に設定できましたが、一時アイテムはpとともに変更されます。一時的なアイテムなしでこれらのアイテムを交換するにはどうすればよいですか、または一時的なアイテムをどうやって動作させるのですか？ここで

void DLinkedList::swap(Item *p, Item *q) 
{ 
    Item* temp = p; 
    p->next = q->next; 
    p->pre = q->pre; 
    if (p->next != NULL) 
     p->next->pre = p; 
    if (q->next != NULL) 
     q->next->pre = q; 
    q->next = temp->next; 
    q->pre = temp->pre; 
    if (p->pre != NULL) 
     p->pre->next = p; 
    if (!q->pre == NULL) { 
     q->pre->next = q; 
    } 
    cout << "- The items " << p->val << " & " << q->val << " were swapped -" << endl; 
} 

Answer 1

は絵の形での状況です：

+----------+  +----------+  +----------+ 
| before_p | <-> |  p | <-> | after_p | 
+----------+  +----------+  +----------+ 

+----------+  +----------+  +----------+ 
| before_q | <-> |  q | <-> | after_q | 
+----------+  +----------+  +----------+ 

あなたは持っている問題はpにtempのポインタを保存すると、実際にp内のポインタをコピーしていないということです。だからあなたがそれらを上書きするとき、あなたは困っている。

ここでは、写真の「前」と「後」の項目が本当に必要なものです。それらをコピーしてロジックを実行する方がはるかに簡単です。

Item * before_p = p->pre; 
Item * before_q = q->pre; 
Item * after_p = p->next; 
Item * after_q = q->next; 

// Relink before and after nodes 
if(before_p) before_p->next = q; 
if(before_q) before_q->next = p; 
if(after_p) after_p->pre = q; 
if(after_q) after_q->pre = p; 

// Relink nodes themselves 
p->pre = before_q; 
q->pre = before_p; 
p->next = after_q; 
q->next = after_p; 

あなたは何行う前に、あなたはまた、健全性テストをしたい場合があります：

if(p == q || !p || !q) return; 

そして最後に、あなたが頭へのポインタを維持している場合は、次のコードはどのくらい明確に見てあなたのリストのどこかにある、そしてそれはスワップされたアイテムの1つになります。*の後にそれを更新することを忘れないでください。

if(head == p) head = q; 
else if(head == q) head = p; 

（*）tailのような他のポインタについても同じです。