高效算法遍歷所有鏈表（使用C++）

Question

假設我有一個雙向鏈表，並且每個元素都有一個字節。維基百科擁有良好的視覺效果;假裝的數字是十六進制數字：

現在，天真（「立竿見影」）的方式來建立從列表中給出一個指向字符串中的最後一個節點一個字符串，（在這個例子中，在37節點），是：

using std::string; 

string node::makeString() 
{ 
    return this->prev->makeString() + this->data; 
} 

的目標是字符串"\0x12\0x99\0x37"。然而，這個函數需要大量重新分配正在構建的字符串和大量的函數調用開銷（它不能被tail-call優化）;無疑還有其他的我沒有意識到的低效率。

有沒有更好的方法？當然，我不只是想盡量減少理論上的時間複雜性，我真的試圖找到一種方法，將在實踐中最快。

Answer 1

從空的std::string開始，回到列表的前面，然後循環遍歷節點和push_back到字符串上。這需要線性時間，這對於這個問題是最佳的。

如果您知道列表有多長時間，可以進一步優化。在這種情況下，您可以從適當長度的字符串開始，並直接在其中插入字符。

Answer 2

解決方案中的低效率是由遞歸引起的。對於鏈表，設置一個字符串並使用一個簡單的while循環。這將導致更好的性能，因爲每個字符串不會有一個函數調用的開銷。

string makeString() { 
    Node* p = l.end(); //l is the linked list. end is its tail node 
    string s = ""; 
    while(p != NULL) { 
    s = p.value() + s; //append the value to the string 
    p = p.prev(); //advance p to the prev node 
    } 
    return s; 
} 

課程甚至更好的性能，我會考慮不使用鏈接的數據結構，因爲它們可能會導致與本地內存處理效率低下。

Answer 3

考慮到手頭有一些限制（你基本上被卡在反向列表中），最好還是建立一個反向的字符串，然後當所有的字符被添加時，反轉字符串。

你現在正在做的事情的方式是獲得二次複雜性 - 每次插入另一個字符時，將該字符放入一個字符串中，將所有現有字符複製到新字符串中，以便每次插入是線性的，並且N個插入大致爲O（N ）。 [注意：實際上，我會誤解代碼 - 這很糟糕，但不是很糟糕]現在，我們可以期望每個角色至少被複制兩次 - 一次到堆棧，一次目標字符串。就內存帶寬而言，低效率可能最爲明顯。至少，每個調用都必須讀取一個指針，將當前字符寫入堆棧並寫入一個返回地址，全部從鏈接列表中複製一個字節到目標字符串。假設一個64位的實現，我們在讀取和寫入指針（以及其他開銷）方面與複製我們真正關心的數據的比例看起來像18：1。

通過向後生成字符串，然後反轉它，您可以在字符串的末尾添加新字符，您可以期望它快速發生。然後，你爲所添加的每個角色只做一次額外的移動，而不是一次。

如果您使用的是std::vector<char>，則可以明確聲明在字符串的末尾添加字符是分期固定的複雜性。使用std::string我們沒有（我記得）得到了一個複雜性保證，但它需要一個非常糟糕的實現，它與複製一個字符的遞歸調用一樣糟糕。

另一種可能性是使用std::deque<char>而不是string。通過一個德克，你可以在前面插入角色，而不用移動所有其他角色來騰出空間。這有兩個缺點：結果通常不是連續的內存塊，而且通常會獲得額外的間接級別，因此在構建數據後訪問數據的速度稍微慢一些。

Answer 4

就我個人而言，我會創建一個字符串鏈接列表，或者說，創建一個char數組，然後向後填充每個節點。

struct StringNode 
{ 
    char buffer [20]; 
    struct StringNode *next; 
}; 

StringNode *node = new StringNode; 
node->buffer [19] = '\0'; 
node->next = 0; 
size_t output = 18; 
size_t count = 1; 

for (ptr = last item ; ptr ; ptr = ptr->prev) 
{ 
    node->buffer [output] = ptr->character; 
    ++count; 
    if (output) 
    { 
    --output; 
    } 
    else 
    { 
    StringNode *newnode = new StringNode; 
    newnode->buffer [19] = '\0'; 
    newnode->next = node; 
    output = 18; 
    node = newnode; 
    } 
} 

string output (count); // preallocate enough storage for whole string and initialise to an empty string 

while(node) 
{ 
    output += &node->buffer [output+1]; 
    // or: cout << &node->buffer [output+1]; 
    StringNode *nextnode = node->next; 
    delete node; 
    node = nextnode; 
    output = -1; 
} 

Answer 5

瓶頸正在重新分配字符串。所以我首先要計算節點的數量，然後再構建字符串。例如

std::string::size_type n = 1; 
for (; node->prev; node = node->prev) ++n; 
std::string s; 
s.reserve(n); 
for (; node->next; node = node->next) s.push_back(node->data); 

Answer 6

有沒有更好的辦法？

當然。

1. 定位列表的開頭。 查找列表的開頭時，計算總節點數（如果它尚不可用）並且計算最終字符串的總字符串大小。
2. 預分配串使用std::string::reserve()
3. 走過該列表從第一個節點到最後一個所需尺寸的，將數據添加到先前預分配字符串的末尾。你可以使用std::string::append()。