Putting your data structure on a diet
Authors:Hervé Brönnimann, Jyrki Katajainen, and Pat Morin
Publication:CPH STL Report 2007-1, Department of Computer Science, University of Copenhagen (2007), 22 pp.
Full text:<pdf.gif>PDF (230 kB)  <ps.gif>PS (426 kB)  

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.

Related:<html.gif>HTML (Early announcement)  <html.gif>HTML (Slides)  
  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},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.