CODEWITHSUNDEEP
c++arraysdata-structureslinked-listsingly-linked-list
Vamsi
Vamsi

Reputation: 679

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

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?

Upvotes: 3

Views: 1763

Answers (4)

VikasGoyal
VikasGoyal

Reputation: 3376

You do not need to iterate on linked list every time if you want to add at last position you just keep hold the reference of last node and it will add the node on its next. Like:-

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

Upvotes: 0

eerorika
eerorika

Reputation: 238371

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.

Upvotes: 3

rcgldr
rcgldr

Reputation: 28826

This is example was done in case you want an actual append operation. The get and set functions prevent you from using a pointer to pointer, but this just requires one if statement to check for an empty list.

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

Upvotes: 1

m_pOatrix
m_pOatrix

Reputation: 150

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

Upvotes: 2

Related Questions