I just finished pset6 following the videos of Zamyla and the section. At the end I realized that my code implements a sorted linked list (via strcmp) but then I don't take advantage of that in my check function. However, “check” seems to work rapidly. I wanted to ask if you used a sorted list or not and if that has had an impact in the performance of the code? Any advice on how to take advantage of a sorted linked list in the check function would be also appreciated. Right now, I don't see how.
If we're NOT using a sorted linked-list, then every time we search for a node in that list, we have to traverse through the whole list in the worst case (if the node we're searching for is the last node in the list or it's not in the list at all).
The advantage of using a sorted linked-list is that we can quit searching as soon as we hit a larger/smaller node (depending on how our list is sorted). For example, given the following list
2, 4, 6, 8, 10
If we're searching for
7 for example, we don't have to check the value of each node in our list, but rather, we can stop searching as soon as we hit the
8 (because if
7 was in the list, we'd certainly find it before the
8 since the list is sorted) and that definitely saves time.
Notice that the searching operation could still be a O(n) operation in case we were searching for values greater than or equal to
On the other hand, a disadvantage of the sorted linked-list approach is the insertion process. To keep the list sorted, the insertion process is a O(n) — it takes n steps, at the worst case, to insert a new node into the list.
At the same time, the insertion process is regarded as a O(1) (aka constant time) operation when using the unsorted linked-list approach. Since we don't really care about our list being sorted, every time we insert a new node, we can insert it at the first position in the list.