Consider a data structure D that stores a dynamic collection of elements. Assume that D uses a linear number of words in addition to the elements stored. In this paper several data-structural transformations are described that can be used to transform D into another data structure D′ that supports the same operations as D, has considerably smaller memory overhead than D, and performs the supported operations by a small constant factor or a small additive term slower than D, depending on the data structure and operation in question. The compaction technique has been successfully applied for linked lists, dictionaries, and priority queues.

@report{BKM2007R,
  author = {Herv\'{e} Br\"{o}nnimann and Jyrki Katajainen and Pat Morin},
  title = {Putting your data structure on a diet},
  type = {CPH STL Report},
  number = {2007-1},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2007},
  pagetotal = {22},
}