提高从数组向链表插入元素的性能

Question

我想将数组的元素插入到链表中。以下是我正在使用的代码片段：

for (int i = 0; i<MAXSIZE; i++)
    {
        Node* n1 = new Node();
        n1->SetData(randArray[i]);
        n1->SetIndex(i);
        n1->SetNext(NULL);

        //checks if NULL
        if (start == NULL) {
            start = n1;
            start->SetNext(NULL);
        }
        else {
            //inserts the values to the end of the node
            Node *p = start;
            while (p->GetNext() != NULL) {
                p = p->GetNext();
            }
            p->SetNext(n1);
        }
    }

这里 randArray[i] 由元素组成，比如 100000 个元素。

现在我希望这个过程执行得更快。目前50000个元素需要13秒。

有人可以帮忙吗？

Answer 1

您现在每次插入新节点时都在寻找最后一个节点...但是您已经知道最后一个节点在哪里，因为您只是在上一次迭代中插入了它 - 如果您没有这样做的话把那些信息扔掉了。只需将指向它的指针存储在一个变量中，该变量在迭代结束时不会被销毁。另一种方法——对于单链表来说更典型一些——是只在列表的前面插入。如果您希望元素的顺序与数组中的顺序相同，则以相反的顺序迭代数组。

摆脱对结束的线性搜索可将算法的运行时复杂度从 O(n^2) 降低到 O(n)。

另一个对性能影响较小但会使您的代码更简单的优化：使用仅在前面插入的方法并使用哨兵节点实现您的列表。这样你就不需要在每次迭代中都有一个分支。也就是说，由于很容易预测，该分支可能影响不大。您也可以使用记住最后一个节点的方法摆脱分支，方法是将测试移到循环之外，但这不会简化您的代码。

编辑：毕竟不需要哨兵节点，即使它确实简化了其他一些列表算法。我很无聊，所以我实现了 insert-in-front-only 方法：

Node* head = nullptr;
for (size_t i = MAXSIZE; i --> 0;) {
    Node* n = new Node();
    n->SetData(randArray[i]);
    n->SetIndex(i); // †
    n->SetNext(head);
    head = n;
}

† 如果您真的想将索引存储在节点中，您可能需要重新考虑。当稍后从尾部以外的其他任何地方插入或删除节点时更新它会非常慢。

Answer 2

正在应用 user2079303 的建议，

你应该有这样的东西：

Node *p = start;
for (int i = 0; i<MAXSIZE; i++)
{
    Node* n1 = new Node();
    n1->SetData(randArray[i]);
    n1->SetIndex(i);
    n1->SetNext(NULL);

    //checks if NULL
    if (start == NULL) 
    {
        start = n1;
        start->SetNext(NULL);
        p = start;
    }
    else 
    {
        //inserts the values to the end of the node
        p->SetNext(n1);
        p = p->GetNext();
    }
}

Answer 3

这个例子是在您需要实际追加操作的情况下完成的。 get 和 set 函数阻止您使用指向指针的指针，但这只需要一个 if 语句来检查空列表。

    Node* tail;  // pointer to last node on list (if start != NULL)
    for (int i = 0; i<MAXSIZE; i++)
    {
        Node* n1 = new Node();
        n1->SetData(randArray[i]);
        n1->SetIndex(i);

        //checks if empty list
        if (start == NULL) {
            start = n1;
            tail = n1;
        }
        else {
            tail->SetNext(n1);
            tail = tail->GetNext();
        }
    }
    tail->SetNext(NULL);

Answer 4

如果你想在最后一个位置添加，你不需要每次都在链表上迭代，你只需要保持最后一个节点的引用，它会在它的下一个节点上添加节点。喜欢：-

 Node* head ;
    Node* last= null;
    for (int i = 0; i < MAXSIZE; i++) {

        Node* n1 = new Node();
        n1->SetData(randArray[i]);
        n1->SetIndex(i);
        n1->SetNext(null);
        if(last != null){
             last->SetNext(n1);
        }else{
           head = n1;
        }
        last = n;
    }

提高从数组向链表插入元素的性能

Improving the Performance for inserting elements into Linked List from an Array

c++

arrays

linked-list

data-structures

singly-linked-list