The Set

This chapter covers the Set ADT, a collection of distinct items with no order. We implement it with a linked list, an unsorted array, and a sorted array, and speed up search in the unsorted versions with the move-to-front and transpose heuristics.

After reading this chapter, you should be able to:

  • Describe the Set ADT: the add, remove, contains, and size operations, the boolean that add and remove return to report whether the call changed the set, the rejection of null, and the absence of any positional operation
  • Implement and trace LinkedSet, a singly linked list with a size field, and ArraySet, a backing array that removes with swap-with-last because a set promises no order
  • Explain why both unsorted implementations leave contains, add, and remove at , and compare them in time and memory
  • Implement the move-to-front and transpose heuristics to speed up search under skewed access, and explain why reordering a set on a read is safe
  • Design a sorted-array set whose contains is , and explain why sorting helps an array but not a linked list

You can download the accompanying code for this chapter: starter and solution.

Sections

  1. Choosing a Username
  2. The Set ADT
  3. Set ADT Specification
  4. Using a Linked List to Implement a Set
  5. The LinkedSet Class
  6. Implementing contains, add, and remove
  7. Tracing the LinkedSet
  8. Using an Array to Implement a Set
  9. The ArraySet Class
  10. Implementing contains, add, and remove
  11. Tracing the ArraySet
  12. The Move-to-Front Heuristic
  13. The Transpose Heuristic
  14. Using a Sorted Array to Implement a Set