Section 2.3:Implementing the Stable Matching Algorithm Using Lists and Arrays

  This chapter discusses the importance of picking the right data structures in terms of run-time. For instance, it reviewed how linked lists are constant for search and deletion yet not for access while arrays have constant access time but linear, O(n) addition. Overall, linked lists are therefore better for dynamic data subject to change whereas arrays are best when the data maintains its size. We can convert between arrays and lists in O(n) time and it is often worth it such as when the input comes in an inefficient format. We apply out learnings to the stable matching algorithm. To make the algorithm O(n^2), all components in the loop must run in constant time. To achieve this, we can represent free men as a linked list, we build an array to represent the indexes of the next choices of women,and use an array to hold women's current matches. Finally, we create a 2d array for men's preferences and a 2d array for women's preferences. To check who women would pick between two men, we just access two arrays which is in constant time. Overall, this section was quick and easy to read and understand. I would rate it at 8/10 to 9/10. One question I have is why the book didn't discuss possibly using other data structures for men and women such as stacks or dictionaries. Also, I am curious how memory would factor into this design in a real world scenario.