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

Question

I want to insert the elements of an array into Linked List. The following is the piece of code that I am using:

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

Here randArray[i] consists the elements say 100000 elements.

Now I want this process to be executed faster. At present it is taking 13 seconds for 50000 elements.

Can someone help out in this?

Answer 1

You're now looking for the last node every time you insert a new node... but you would already know where the last node is because you just inserted it in the last iteration - if only you hadn't thrown that information away. Simply keep a pointer to it stored in a variable that isn't destroyed at the end of the iteration. Another way - which is a bit more typical for singly linked lists - is to only insert at the front of the list. If you want the elements in the same order as in the array, then iterate the array in reverse order.

Getting rid of the linear search for end reduces your algorithm's runtime complexity from O(n^2) to O(n).

Another optimization that will have less impact on performance, but will make your code simpler: Use the insert-in-front-only-approach and implement your list using a sentinel node. That way you don't need a branch in every iteration. That said, the branch probably has little effect due to being easily predictable. You can get rid of the branch with the remember-last-node approach too, by moving the test outside of loop, but that won't simplify your code.

EDIT: sentinel node is not needed after all, even though it does simplify some other list algorithms. I was bored, so I implemented the insert-in-front-only approach:

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

† You may want to reconsider if you really want to store the index in a node. Updating it when nodes are later inserted or removed from anywhere else other than the tail is going to be quite slow.

Answer 2

Applying user2079303 advice,

You should have something like that:

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