CODEWITHSUNDEEP
c
Jeremy Fisher
Jeremy Fisher

Reputation: 2782

Efficiency of an unsorted vs sorted linked list in C

For a programming project, I created two linked list programs: an unsorted linked list and a sorted linked list. The unsorted linked list program adds values to the end of the list as long as the value is not found in the list. If the value is found in the list, the node containing the value is removed. The only difference in the sorted linked_list program is that if a value is not found in the list, instead of just adding the value to the end, the program looks for the proper space to insert the value so that the repository is consistently maintained in sorted order. I have a "stepcounter" variable that basically increments each time a pointer in my program is reassigned to a point to a different pointer, even during traversal of the linked list. I output this variable to the screen to give me an idea of the efficiency of my program. What's strange is that if I run the same operation on the sorted list and on the unsorted list, the number of steps, or, effort of the unsorted list is MORE than the sorted list. This seems very counter-intuitive to me but I looked through my code and I'm pretty sure I incremented in all the same places, so I can't come up with an explanation as to why the unsorted linked list operations would have more steps than the sorted. Is there something I'm missing?

Upvotes: 0

Views: 3770

Answers (2)

Meino Cramer
Meino Cramer

Reputation: 11

Suppose you have 1000 data to insert in both lists and the data is pure random order but of the values of 1 up to 1000.

Additionally suppose both lists are filled already with 500 data items of pure random order for the unsorted list and of sorted order in case of the sorted list.

For the unsorted list you have to check each item to find possible doubles, which lead to a pointer stepping forward for each visited node.

For the sorted list you only have to search forward this way until the first element appears in the list which has a greater value.

The chance of such hits is 50% by 1000 elements being inserted into a list already filled with 500 items for a total range of 1 to 1000 for the values. This creates 50% of all operations being inserts for replaces, which let the unsorted list being checked for additional items compared to the sorted list. Insertion itself is more cheap with the unsorted list (1 step instead of 4 steps).

Upvotes: 1

dmckee --- ex-moderator kitten
dmckee --- ex-moderator kitten

Reputation: 101259

If you are really keeping track of pointer assignments, then walking like

while (p && (p.value != input) && (p.next != NULL)) p = updatePointer(p.next);

(assuming updatePointer takes care of your counting) performs one of those for each node you examine.

  • To know if a item is in the unsorted list you have to look at every node in the list. (That is, you have to use the code I had above)

  • To do the same thing on the sorted list you only have to keep looking until you pass the space where the item is questions would have been. This implies code like

    while (p && (p.value < input) && (p.next != NULL)){ 
    p = updatePointer(p.next);
}
if (p.value == input) //...

Assuming randomly distributed (i.e. unordered input) you expect the second to case to require about 1/2 as many comparisons.

Upvotes: 2

Related Questions