Learning Algorithms

Chapter 8. Wrapping It Up

My goal in this book was to introduce you to the fundamental algorithms and the essential data types used in computer science. You need to know how to efficiently implement the following data types to maximize the performance of your code:

Bag

A linked list ensures O(1) performance when adding a value. If you choose to use an array, then you need to employ geometric resizing to extend the size of the array so you can guarantee amortized O(1) performance over its average use (though you will still incur an O(N) runtime performance on the infrequent resize events). Note that a bag does not typically allow values to be removed, nor does it prevent duplicate values from being added.

Stack

A linked list can store the values in a stack so push() and pop() have O(1) runtime performance. The stack records the top of the stack to push and pop values.

Queue

A linked list can efficiently store a queue so enqueue() and dequeue() have O(1) runtime performance. The queue records the first and the last node in the linked list to efficiently add and remove values from the queue.

Symbol table

The open addressing approach for symbol tables is surprisingly efficient, with suitable hash functions to distribute the (key, value) pairs. You still need geometric resizing to double the size of the storage, thus effectively making these resize events less frequent.

Priority queue

The heap data structure can store (value, priority) pairs to support enqueue() and dequeue() ...