2.3 Implementing The Stable Matching Algorithm using Lists and Arrays

To asymptotically analyze the running time of an algorithm, we don't need to implement and run it, but we definitely have to think about how the data will be represented and manipulated in an implementation of the algorithm so we could bound the number of computational steps it takes. This section looks at how to implement the Gale-Shapley algorithm using lists and arrays. In the Stable Matching Problems that the algorithm solves, we need to think about how the rankings will be represented, as each man and each woman has a ranking of all members of the opposite gender. In addition, we will need to know which men and women are free, and who is matched with whom. Finally, we need to decide which data structures to use for all of the mentioned data. The goal of for the designer is to choose data structures that will make the algorithm efficient and easy to implement.

Let's focus on a single list, such as a list of women in order of preference by a single man.

• The simplest way to keep a list of n elements is to use an Array A of length n.
• In such an array, let A[i] be the i^th element of the list
• With such an array we can:
• Determine the i^thelement on the list in O(1) time,by accessing the value A[i]
• Determine if a given element e belongs to the list by checking the elements one by one in O(n) time, assuming we don't know the order in which the elements are arranged in A.
• Determine if the given element e belongs to A in O(logn) using binary search if A is sorted

For dynamically maintaining a list of elements that change a lot over time such as a list of free men, an array is less preferable. Indeed, we our collection needs to grow and shrink very frequently throughout the execution of the algorithm. Thus we choose an alternative to an array: the linked list.

In a linked list, each element points to the next in the list. Thus:

• For each element v, we maintain a pointer to the next element
• The “next” pointer is set to null(None in python) if i is the last element in the list
• The pointer“First” points to the first element in the list
• By starting from First, the traversal of the entire list can be done in time proportional to its length
• To implement such a list:
  • We would allocate a record e for each element we want to put in the list
  • For each record e:
    • e.val: contains the value of the record
    • e.next: contains a pointer to the next element
  • If we want to implement a doubly linked list, which is traversable in both directions:
    • In addition of what the singly linked list contained, we add e.Prev which points to the previous element in the list(e.Prev = null if e is the first element.
    • The pointer “Last” that points to the last element in the list
  • Thus, with a doubly linked list:
    • deletion: To delete e: Have the e.Prev and e.next point directly to each other
    • insertion: To insert e between d and f: update d.next and f.Prev to point to e, e.Prev point to d and e.next point to f.

Disadvantage of linked lists: To find the i^th element we have to follow the “next” pointers starting from “First” until we get the element, which takes O(i), whereas it takes us O(1) time with arrays.