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.

@inproceedings{BKM2006A,
  author = {Herv\'{e} Br\"{o}nnimann and Jyrki Katajainen and Pat Morin},
  title = {Putting your data structure on a diet},
  booktitle = {Proceedings of the 6th STL Workshop},
  series = {CPH STL Report},
  volume = {2006-8},
  publisher = {Department of Computer Science, University of Copenhagen},
  year = {2006},
  pages = {3},
}