改进从数组向链表中插入元素的性能

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）。

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

EDIT：哨兵节点毕竟是不需要的，尽管它确实简化了其他一些列表算法。我很无聊，所以我实现了只在前面插入的方法：

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;
    }