需要鏈接列表推回操作中的'返回指針'

我想弄清楚下面的代碼來實現鏈接列表的push_back函數，但我不太清楚爲什麼我們需要back_ptr->next和back_ptr都指向p。我相信back_ptr->next可能只是指向NULL它的工作，是否有任何優勢實施它，因此我失蹤？需要鏈接列表推回操作中的'返回指針'

void LinkedList::push_back(int element) { 
    Node *p = new Node; 
    p->element = elememt; 
    p->next = 0; 
    if (empty()) { 
     front_ptr = back_ptr = p; 
    } else { 
     back_ptr->next = p; 
     back_ptr = p; 
    } 
}

以下是LinkedList類的原型。 back_ptr被用於指向實現複製構造函數的列表的末尾（push_back使複製列表變得容易很多）。

class LinkedList { 
    void push_back(int element); 
    // other member functions 

    private: 
    struct Node { 
     Node *next; 
     int element; 
    }; 
    Node *front_ptr; 
    Node *back_ptr; 
};

來源

2017-02-04 pinbox

的可能的複製[鏈表推回的成員函數的實現]（http://stackoverflow.com/questions/39606977/linked- list-pushback-member-function-implementation） –

push_back(1); 
push_back(2); 
Node *p = new Node; 
p->element = 3; 
p->next = nullptr;

front_ptr  back_ptr   p 
    ↓    ↓    ↓ 
┌────┬────┐ ┌────┬────┐ ┌────┬────┐ 
| #1 |next| → | #2 |next| | #3 |next| → nullptr 
└────┴────┘ └────┴────┘↘ └────┴────┘ 
          nullptr

back_ptr->next = p;

front_ptr  back_ptr   p 
    ↓    ↓    ↓ 
┌────┬────┐ ┌────┬────┐ ┌────┬────┐ 
| #1 |next| → | #2 |next| → | #3 |next| → nullptr 
└────┴────┘ └────┴────┘ └────┴────┘

back_ptr = p;

front_ptr    back_ptr p 
    ↓       ↘ ↓ 
┌────┬────┐ ┌────┬────┐ ┌────┬────┐ 
| #1 |next| → | #2 |next| → | #3 |next| → nullptr 
└────┴────┘ └────┴────┘ └────┴────┘

來源

2017-02-04 07:11:43 ephemient

只是好奇，你是怎麼想出圖形 –

@AmitKumar我手動安排了Unicode塊繪製字符和箭頭。您可以在[修訂歷史]（http://stackoverflow.com/posts/42037632/revisions）中查看源代碼。（這不是很有趣。） – ephemient

哇，視覺效果讓它更容易理解。我想我錯過了'back_ptr-> next'和'back_ptr'更新的順序（我認爲它們可以以任何順序寫入）。謝謝！ – pinbox

讓我解釋一下，如果列表不是在推的時候空空的回來，這是目前尾巴應指向它的下一個新的節點，最後尾部應指向新節點的節點。

 Before push back 
    tail-> node x // tail points to node x 
     x->next = null // as it is tail 
    After push back new node y 
     tail->next = y 
    As x was earlier pointed by tail ,this means x->next = p,

此步驟可確保列表保持連接狀態。

 Finally , point the tail to the new node 
    tail -> y

來源

2017-02-04 07:08:52

需要鏈接列表推回操作中的'返回指針'

回答

相關問題