What will be the complexity of the operation to remove an element from the end of the singly linked list ?

Question

What will be the complexity of the operation to remove an element from the end of the singly linked list ? I have implemented linked-list in C. Here is the code for removing a element from the end of linked-list. Now my query is that how to calculate the complexity of this snippet. What are the factors involved. There are other operations involved too like

1. Insert at begin
2. Insert at middle
3. Insert at end
4. Delete at begin ,middle ,end
5. Reverse the list

How will I be able to calculate them ?

struct node {
       int val;
       struct node * next;
    };

    typedef struct node item;
    item * head = NULL;

 /* DELETION AT THE END OF THE LIST */     
        deleteatend() {
        item * temp, * curr;
        if(head == NULL) {
            printf("\n Linked list is Empty ");
            return;
          }
        temp = head;
        if(head->next == NULL) { /* When There is atleast 1 NODE */
            head=NULL;
         } 
        else {
            while(temp->next != NULL) { /* Traversing the list upto second-last NODE */ 
              curr=temp;
              temp=temp->next;
              } 
            curr->next =NULL;  /* When TEMP points to last NODE */ 
        }
        free(temp);
       }    

code for Reverse the list :

 /* Reverse Printing of list */
      reverselist() {
          item * curr, * nextnode, * prev;
          curr = head;
          nextnode = curr-> next; /* NEXTNODE traverses till the end of the list */
          prev = NULL;
          curr-> next = NULL; /* Making the first Node as Last node */
          while(nextnode != NULL) {
            prev = curr; /* Generally holding the last element of the reversed list */
            curr = nextnode; 
            nextnode = curr-> next;
            curr-> next = prev;
           } /* End of WHILE */
          head = curr;
        }  

Answer 1

The complexity of a plain linked list operation is constant if it is implemented without a loop or recursion and linear if is implemented with a loop.

Answer 2

With a list it is linear to length of the list, so Θ(n), while direct access, like an array is Θ(1).

Answer 3

I will give some kitchen recipes to find out the (apparent) complexity of an algorithm. It is not mathematically rigorous, for that you will have to consult your schoolbooks.

1. Find the parameters on which your analysed code depends. N for number of elements of your list. Other algos have other parameters, number of characters, number of elements in an array.

2. Find the loops. See on what parameter they depend on.

   1. To insert the first element of a list you don't need to loop, so it's the same operation if your list contains 1 or 1 billion elements.

   2. To insert in the middle you have to loop once completely through the list and depending on how you implement it, you have to loop a second time to the middle, so you have 1.5 times N iterations. The complexity depends only on the length of the list, its complexity is therefore O(N). If you implement it by only looping once, you will have N iterations and still complexity O(N). The choice of which way to implement it may depend on the individual time of each iteration (and the time to implement it).

   3. Same as above, you have to go through the entire list once, so complexity O(N).

   4. Same as for insert.

   5. To reverse the list, you need only to loop once over the list so again complexity O(N).

   6. Just for the example of another complexity. If you want to eliminate all double entries of your list. You have to check for every element if it is equal to any other element of the list, this means you have to loop through all elements, take the element and compare it to every other element in the list. In the worst case no doubles are in the list meaning the list doesn't shrink so you tend to have N*(N-1) comparisons. In O notation O(N*(N-1)) = O(N²-N) N² dominates so we have a complexity of O(N²) a quadratic algorithm.

PS: I wrote at the beginning apparent because sometimes there are terms depending on N that are not visible in the program itself but are part of the abstraction you're working on. In the case of your list, if it gets so big that your system starts swapping, you hit one of those hidden terms of the real complexity, one that was burried in the virtual memory abstraction of your operating system.