Week 4 Day 3 - TDD and Linked Lists

Channel:

Bill Kerney

Subscribers:

2,640

Published on February 6, 2021 5:18:53 AM ● Video Link: https://www.youtube.com/watch?v=3-ORnyP54ag

Duration: 1:30:51

201 views

3

Today we talked about Test Driven Development - your next homework assignment is pretty simply technically (you have to make two versions of the fizzbuzz program) but it will teach you how to do TDD using the Google Gtest suite. With TDD you:
1) Write your tests first and make sure you're failing them all (you will get RED results from the tests, meaning the tests fail)
2) Write your code. As you develop your code, you should start passing more and more of the test cases (turning them GREEN). Once all the tests are green, your code is correct.
3) You should REFACTOR your code, cleaning it up and polishing it (I show an example from Codewars, a neat site where you can practice your coding). Re-run the tests to make sure your refactoring doesn't break a test.


The above process is thus called RED GREEN REFACTOR.


Next we went over Big-O a little bit again, an explain why a for loop that runs 10 times is O(1), not O(N) - it's because O(1) means *constant* running time. In other words, the running time does not change based on the input size. O(1) does not mean it's just one operation.


Finally we talked about linked lists, and how to use the list class in the standard library. Due to the great design of the C++ standard library, you can swap out data structures like vectors and lists a great deal of the time, and your code will continue to work. But since they have different Big O running times for different things, which you should use in your program, well, it depends on the needs of your program. Here's the key differences:
1) Vectors can randomly access elements from the middle of the vector in O(1) time. A linked list needs O(N) time to access the same element.
2) A list can push_front() and pop_front() in O(1) time. A vector does it in O(N) time.


So which is best for your program? Well, whichever one you need to be faster. If you're doing a lot of pushes and pops from both the front and the back, then the list will be better. If you're doing a lot of random accesses in the middle of the data structure, the vector will be better.


You can use most standard library functions (like count() and find() and min_element() and so forth) with both, so often times you can just change "vector" to "list" and the code will still work, and you can just see which one is faster in practice. BUT - because lists don't have random access, some standard library functions won't work, most notably sort(). So you have to use the special list.sort() function instead.