From charlesreid1

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:

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

Links

Answers to end-of-chapter stacks/queues questions: StacksQueues#Skiena_Chapter_3

Answers to end-of-chapter linked list questions: Linked_Lists#Skiena_chapter_3_questions


Flags