Advanced Data Structures

A Succinct Overview of Advanced Data Structures

Skiena Chapter 3 devotes a single chapter to data structures, and it is extremely revealing to see where he spends his time.

Chapter 3 covers the following topics:

• Linked Lists
• StacksQueues
• Priority Queues
• Binary Trees
• Hash Tables

Other specialized data structures:

• Points in space, strings, and graphs
• String data structures: arrays of characters
• Geometric data structures - data points and regions; polygons, segments, arrays of points, spatial arrangements, organization of points by geometric location to support fast search.
• Graph data structures - represented using adjacency matrices or adjacency lists
• Choice of graph representation has substantial impact on design of resulting algorithms.
• Set data structures - dictionaries to support fast membership queries; bit vectors are boolean arrays such that the ith bit represents true if i is in the subset.
• Union find data structure for maintaining set partitions