Research Challenges

Often programmers must look up how to do things because no one can know all there is to know in coding. These challenges test in part your ability to research how to do particular things. For all these questions provide references for where you learned what you needed to know to solve the problem. $-20\backslash \%[2\mathrm{.}4$ hour$]$

$3.$ Besides a Linked$-$list, there is also something called a Doubly Linked$-$list. In a Doubly Linked$-$list, each element of the list has two references. Instead of just the one reference pointing to the next element in the list, it also has a second reference pointing back to the previous element of the list. This is sometimes called a deque. The advantage of this type of list is that it is easy to add and remove elements from either end of the list and inserting and removing elements becomes easier as well.

Your friend has written a Python program that uses several deque objects. After finishing it$,$ he realized that he really didn't need deques because he doesn't do any operations at the beginning of the list. So he's thinking of changing his deques to queues, but is wondering if fiddling with all the code is really worth the effort.

What advice would you give him? It's not enough to say $"...$ is smaller" or $"...$ is faster." You need to back up your advice with evidence $--$ show how much smaller or faster by using the Python runtime $($sys$.$getsizeof, timeit.timeit$)$ to justify your claims with some solid numbers. Show your experiments here.

Your friend is also not certain about how big the deques$/$queues might get, so be sure that you test your hypotheses over several magnitudes of sizes. $[2\mathrm{.}4$ hour challenge$]$