Manipulate Linked List to reduce insertion time complexity

Arrays is a collections of items stored at contiguous memory location. It stores multiple data of same type.

Now the retrieving data from a arrays is very easy, all we have to do is to get the data from the position.
arr[pos];

But insertion and deletion is very costly.
As arrays are static every time a new element has to be inserted at the end , a new array is created and the we have to loop through the whole array inserting the all the previous elements an then the new element is reached at the end.
The time complexity is always n as it has to traverse the array.

This problem could be solved using linked list if we can manipulate it.


class Node{
Node* head=NULL;
Node* tail=NULL; // Maintaining a pointer that points to the end
void insert(int data){
Node* node= new Node;
node->data=data;
if(head==NULL){
head=node;
}else{
// no need to traverse the complete linked list as we already
// have a pointer pointing to the end
// all we have to do add a pointer after that pointer
tail->next=node;
tail=tail->next;
}
}
};


By maintaining a pointer that points to the end of the linked list we can reduce the time complexity of the insertion. Now we can insert at linear time.